Worldlex Wiki L'exemple classique d'utilisation du retour arrière est le problème des huit reines , qui consiste à trouver tous les arrangements possibles de huit reines sur un échiquier standard , de sorte qu'aucune reine n'en attaque une autre. Dans l'approche classique du retour arrière, les solutions partielles sont des arrangements de k reines sur les k premières lignes de l'échiquier, toutes sur des lignes et des colonnes différentes. Toute solution partielle contenant deux reines s'attaquant mutuellement peut être rejetée.
Le retour arrière ne s'applique qu'aux problèmes admettant la notion de « solution candidate partielle » et un test relativement rapide permettant de déterminer si elle peut être complétée en une solution valide. Il est inutile, par exemple, pour localiser une valeur donnée dans un tableau non ordonné. Lorsqu'il est applicable, le retour arrière est souvent beaucoup plus rapide que l'énumération exhaustive de toutes les solutions candidates complètes, car il permet d'en éliminer un grand nombre en un seul test.
Le retour arrière est un outil important pour la résolution des problèmes de satisfaction de contraintes , tels que les mots croisés , l'arithmétique verbale , le Sudoku et de nombreux autres jeux de logique. C'est souvent la technique la plus pratique pour l'analyse syntaxique , notamment pour le problème du sac à dos et d'autres problèmes d'optimisation combinatoire . C'est également la stratégie d'exécution de programme utilisée dans les langages de programmation Icon , Planner et Prolog .
Le backtracking repose sur des « procédures boîte noire » définies par l'utilisateur, qui caractérisent le problème à résoudre, la nature des solutions partielles et leur extension en solutions complètes. Il s'agit donc d'une métaheuristique plutôt que d'un algorithme spécifique ; toutefois, contrairement à de nombreuses autres métaheuristiques, elle garantit la résolution de tous les problèmes finis en un temps limité.
Le terme « retour arrière » a été inventé par le mathématicien américain DH Lehmer dans les années 1950. Le langage pionnier de traitement de chaînes SNOBOL (1962) a peut-être été le premier à fournir une fonction de retour arrière générale intégrée.
structure arborescente , l' arbre de recherche potentiel. Chaque candidat partiel est le parent des candidats qui le différencient par une seule étape d'extension ; les feuilles de l'arbre sont les candidats partiels qui ne peuvent plus être étendus.L'algorithme de retour arrière parcourt cet arbre de recherche récursivement , de la racine vers les sous-arbres , en profondeur d'abord . À chaque nœud c , l'algorithme vérifie si c peut être complété en une solution valide. Si ce n'est pas le cas, le sous-arbre entier enraciné en c est ignoré ( élagué ). Sinon, l'algorithme (1) vérifie si c est lui-même une solution valide et, le cas échéant, le signale à l'utilisateur ; et (2) énumère récursivement tous les sous-arbres de c . Les deux tests et les enfants de chaque nœud sont définis par des procédures fournies par l'utilisateur.
Par conséquent, l' arbre de recherche effectivement parcouru par l'algorithme ne représente qu'une partie de l'arbre potentiel. Le coût total de l'algorithme correspond au nombre de nœuds de l'arbre réel multiplié par le coût d'obtention et de traitement de chaque nœud. Il convient d'en tenir compte lors du choix de l'arbre de recherche potentiel et de la mise en œuvre du test d'élagage.
Pseudocode
Pour appliquer le backtracking à une classe spécifique de problèmes, il faut fournir les données P de l'instance particulière du problème à résoudre, ainsi que six paramètres procéduraux : root , reject , accept , first , next et output . Ces procédures doivent prendre les données de l'instance P comme paramètre et effectuer les opérations suivantes :
- racine ( P ): renvoie le candidat partiel à la racine de l'arbre de recherche.
- rejeter ( P , c ): renvoie vrai uniquement si le candidat partiel c ne vaut pas la peine d'être complété.
- accept ( P , c ): renvoie vrai si c est une solution de P , et faux sinon.
- premier ( P , c ): générer la première extension du candidat c .
- suivant ( P , s ): générer la prochaine extension alternative d'un candidat, après l'extension s .
- sortie ( P , c ): utiliser la solution c de P , selon ce qui convient à l'application.
L'algorithme de retour arrière réduit le problème à l'appel backtrack ( P , root ( P )), où backtrack est la procédure récursive suivante :
La procédure backtrack(P, c) est : si reject(P, c) alors retourner ; si accept(P, c) alors afficher(P, c). s ← premier(P, c) tant que s ≠ NULL faire retour arrière(P, s) s ← suivant(P, s)
Considérations relatives à l'utilisation
La procédure de rejet doit être une fonction booléenne qui renvoie vrai uniquement s'il est certain qu'aucune extension possible de c n'est une solution valide pour P. Si la procédure ne peut aboutir à une conclusion définitive, elle doit renvoyer faux . Un résultat vrai erroné peut amener la procédure de retour arrière à manquer certaines solutions valides. La procédure peut supposer que rejeter ( P , t ) a renvoyé faux pour chaque ancêtre t de c dans l'arbre de recherche.
En revanche, l'efficacité de l'algorithme de retour arrière dépend du fait que la fonction `reject` renvoie `true` pour les candidats les plus proches de la racine. Si `reject` renvoie toujours `false` , l'algorithme trouvera certes toutes les solutions, mais son résultat sera équivalent à une recherche exhaustive.
La procédure d'acceptation doit renvoyer vrai si c est une solution complète et valide pour l'instance de problème P , et faux sinon. Elle peut supposer que le candidat partiel c et tous ses ancêtres dans l'arbre ont passé le test de rejet .
Le pseudo-code général ci-dessus ne suppose pas que les solutions valides soient toujours des feuilles de l'arbre de recherche potentiel. Autrement dit, il admet la possibilité qu'une solution valide pour P puisse être étendue pour donner d'autres solutions valides.
Les procédures `first` et `next` sont utilisées par l'algorithme de retour arrière pour énumérer les enfants d'un nœud `c` de l'arbre, c'est-à-dire les candidats qui diffèrent de `c` par une seule étape d'extension. L'appel ` first ( P , c )` doit renvoyer le premier enfant de `c` , dans un ordre donné ; et l'appel ` next ( P , s )` doit renvoyer le frère suivant du nœud `s` , dans le même ordre. Les deux fonctions doivent renvoyer un candidat distinctif « NULL » si l'enfant demandé n'existe pas.
Ensemble, les fonctions racine , premier et suivant définissent l'ensemble des candidats partiels et l'arbre de recherche potentiel. Elles doivent être choisies de sorte que chaque solution de P figure au moins une fois dans l'arbre, et qu'aucun candidat partiel n'y apparaisse plus d'une fois. De plus, elles doivent admettre un prédicat de rejet efficace .
variantes d'arrêt précoce
Le pseudo-code ci-dessus affichera la sortie pour tous les candidats qui constituent une solution à l'instance P donnée . L'algorithme peut être modifié pour s'arrêter après avoir trouvé la première solution, ou un nombre spécifié de solutions ; ou après avoir testé un nombre spécifié de candidats partiels, ou après avoir consommé une quantité donnée de temps CPU .
Exemples
Voici quelques exemples d'utilisation du retour en arrière pour résoudre des énigmes ou des problèmes :
- Des puzzles tels que le puzzle des huit reines , les mots croisés , l'arithmétique verbale , le Sudoku et le solitaire Peg .
- Problèmes d'optimisation combinatoire tels que l'analyse syntaxique et le problème du sac à dos .
- Les langages de programmation orientés objectifs tels qu'Icon , Planner et Prolog , qui utilisent le retour arrière en interne pour générer des réponses.
- L' algorithme DPLL pour résoudre le problème de satisfaisabilité booléenne .
Voici un exemple d'utilisation du retour arrière pour le problème de satisfaction de contraintes :
Satisfaction des contraintes
Le problème général de satisfaction de contraintes consiste à trouver une liste d'entiers conjonction de plusieurs prédicats booléens, propagation des contraintes .
Outre la conservation des valeurs minimales de récupération utilisées lors de la sauvegarde, les implémentations de backtracking conservent généralement un historique des modifications de valeurs dans ce journal. Une implémentation efficace évite la création d'une entrée dans ce journal entre deux modifications successives lorsqu'il n'existe aucun point de choix, car le backtracking efface toutes les modifications en une seule opération.
Une alternative à l'historique des variables consiste à conserver un horodatage de la dernière modification apportée à la variable. Cet horodatage est comparé à celui d'un point de choix. Si ce point de choix est postérieur à l'horodatage de la variable, il est inutile de rétablir la valeur initiale de la variable lors du retour en arrière, car elle a été modifiée avant ce point de choix.