Retour en arrière - Backtracking

Le backtracking est un algorithme général pour trouver des solutions à certains problèmes de calcul , notamment les problèmes de satisfaction de contraintes , qui construit progressivement des candidats aux solutions et abandonne un candidat ("backtracks") dès qu'il détermine que le candidat ne peut pas être complété jusqu'à un solution.

L'exemple classique de l'utilisation du retour en arrière est le puzzle des huit reines , qui demande tous les arrangements de huit reines d' échecs sur un échiquier standard afin qu'aucune reine n'attaque une autre. Dans l'approche de retour en arrière commune, les candidats partiels sont des arrangements de k reines dans les k premières rangées du tableau, toutes dans des rangées et des colonnes différentes. Toute solution partielle contenant deux reines s'attaquant mutuellement peut être abandonnée.

Le retour en arrière ne peut être appliqué que pour les problèmes qui admettent le concept d'une "solution candidate partielle" et un test relativement rapide pour déterminer s'il peut éventuellement être complété par une solution valide. Elle est inutile, par exemple, pour localiser une valeur donnée dans une table non ordonnée. Lorsqu'il est applicable, cependant, le retour en arrière est souvent beaucoup plus rapide que l' énumération par force brute de tous les candidats complets, car il peut éliminer de nombreux candidats avec un seul test.

Le backtracking est un outil important pour résoudre les problèmes de satisfaction de contraintes , tels que les mots croisés , l' arithmétique verbale , le Sudoku et bien d'autres énigmes. C'est souvent la technique la plus pratique pour l' analyse syntaxique , pour le problème du sac à dos et d'autres problèmes d' optimisation combinatoire . C'est aussi la base des langages de programmation dits logiques tels que Icon , Planner et Prolog .

Le retour en arrière dépend des « procédures de boîte noire » données par l'utilisateur qui définissent le problème à résoudre, la nature des candidats partiels et la manière dont ils sont étendus aux candidats complets. Il s'agit donc d'une métaheuristique plutôt que d'un algorithme spécifique – bien que, contrairement à de nombreuses autres métaheuristiques , il soit garanti de trouver toutes les solutions à un problème fini dans un laps de temps limité.

Le terme « backtrack » 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 intégrée de retour en arrière général.

Description de la méthode

L'algorithme de retour en arrière énumère un ensemble de candidats partiels qui, en principe, pourraient être complétés de diverses manières pour donner toutes les solutions possibles au problème donné. L'achèvement se fait de manière incrémentale, par une séquence d' étapes d'extension candidates.

Conceptuellement, les candidats partiels sont représentés comme les nœuds d'une structure arborescente , l' arbre de recherche potentiel. Chaque candidat partiel est le parent des candidats qui s'en distinguent 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 en arrière parcourt cet arbre de recherche de manière récursive , de la racine vers le bas, dans le premier ordre de profondeur . A 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, tout le sous-arbre enraciné en c est ignoré ( élagué ). Sinon, l'algorithme (1) vérifie si c est lui-même une solution valide, et si c'est le cas le rapporte à 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 données par l'utilisateur.

Par conséquent, l' arbre de recherche réel qui est traversé par l'algorithme n'est qu'une partie de l'arbre potentiel. Le coût total de l'algorithme est le nombre de nœuds de l'arbre réel multiplié par le coût d'obtention et de traitement de chaque nœud. Ce fait doit être pris en compte lors du choix de l'arbre de recherche potentiel et de la mise en œuvre du test d'élagage.

Pseudocode

Afin d'appliquer le retour en arrière à une classe spécifique de problèmes, il faut fournir les données P pour l'instance particulière du problème à résoudre, et six paramètres procéduraux , racine , rejet , accept , premier , suivant et sortie . Ces procédures doivent prendre les données d'instance P comme paramètre et effectuer les opérations suivantes :

  1. root ( P ) : retourne le candidat partiel à la racine de l'arbre de recherche.
  2. rejeter ( P , c ) : ne renvoie vrai que si le candidat partiel c ne vaut pas la peine d'être complété.
  3. accept ( P , c ): retourne vrai si c est une solution de P , et faux sinon.
  4. first ( P , c ) : générer la première extension du candidat c .
  5. next ( P , s ) : génère la prochaine extension alternative d'un candidat, après l'extension s .
  6. sortie ( P , c ) : utiliser la solution c de P , selon l'application.

L'algorithme de backtracking réduit le problème au backtrack d' appel ( root ( P )), où backtrack est la procédure récursive suivante :

procedure backtrack(c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(s)
        s ← next(P, s)

Considérations d'utilisation

La procédure de rejet doit être une fonction booléenne qui ne renvoie vrai que s'il est certain qu'aucune extension possible de c n'est une solution valide pour P . Si la procédure ne parvient pas à une conclusion définitive, elle doit renvoyer false . Un résultat vrai incorrect peut faire en sorte que la procédure bt manque certaines solutions valides. La procédure peut supposer que rejet ( P , t ) a renvoyé faux pour chaque ancêtre t de c dans l'arbre de recherche.

D'autre part, l'efficacité de l'algorithme de backtracking dépend du rejet retournant vrai pour les candidats qui sont aussi proches que possible de la racine. Si rejet renvoie toujours false , l'algorithme trouvera toujours toutes les solutions, mais cela équivaudra à une recherche par force brute.

La procédure d' acceptation doit retourner true si c est une solution complète et valide pour l'instance de problème P , et false dans le cas contraire. Il peut supposer que le candidat partiel c et tous ses ancêtres dans l'arbre ont réussi le test de rejet .

Le pseudo-code général ci-dessus ne suppose pas que les solutions valides sont toujours des feuilles de l'arbre de recherche potentiel. En d'autres termes, il admet la possibilité qu'une solution valide pour P puisse être étendue davantage pour produire d'autres solutions valides.

La première et la suivante procédures sont utilisées par l'algorithme de backtracking 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 ) devrait donner le premier enfant de c , dans un certain ordre ; et l'appel next ( P , s ) doit renvoyer le prochain frère du nœud s , dans cet ordre. Les deux fonctions doivent retourner un candidat "NULL" distinctif, si l'enfant demandé n'existe pas.

Ensemble, les fonctions root , first et next définissent l'ensemble des candidats partiels et l'arbre de recherche potentiel. Ils doivent être choisis de telle sorte que chaque solution de P apparaisse quelque part dans l'arbre et qu'aucun candidat partiel ne se produise plus d'une fois. De plus, ils devraient admettre un prédicat de rejet efficient et efficace .

Variantes d'arrêt précoce

Le pseudo-code ci-dessus appellera la sortie pour tous les candidats qui sont une solution à l'instance donnée P . 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 passé un certain temps CPU .

Exemples

Un Sudoku résolu par retour en arrière.

Exemples où le retour en arrière peut être utilisé pour résoudre des énigmes ou des problèmes :

Voici un exemple où le backtracking est utilisé 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 x = ( x [1], x [2], …, x [ n ]) , chacun dans un intervalle {1, 2, …, m }, qui satisfait contrainte arbitraire (fonction booléenne) F .

Pour cette classe de problèmes, les données d'instance P seraient les entiers m et n , et le prédicat F . Dans une solution typique de retour en arrière à ce problème, on pourrait définir un candidat partiel comme une liste d'entiers c = ( c [1], c [2], …, c [k]) , pour tout k entre 0 et n , que sont à affecter aux k premières variables x [1], x [2], …, x [ k ] . Le candidat racine serait alors la liste vide (). La première et la suivante procédures seraient alors

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], …, c[k], 1)
function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], …, s[k − 1], 1 + s[k])

Ici longueur ( c ) est le nombre d' éléments dans la liste c .

Le rejet d' appel ( P , c ) doit retourner vrai si la contrainte F ne peut être satisfaite par aucune liste de n entiers commençant par les k éléments de c . Pour que le backtracking soit efficace, il doit y avoir un moyen de détecter cette situation, au moins pour certains candidats c , sans énumérer tous ces m nk n -uplets.

Par exemple, si F est la conjonction de plusieurs prédicats booléens, F = F [1] ∧ F [2] ∧ … ∧ F [ p ] , et chaque F [ i ] ne dépend que d'un petit sous-ensemble des variables x [1 ], …, x [ n ] , alors la procédure de rejet pourrait simplement vérifier les termes F [ i ] qui ne dépendent que des variables x [1], …, x [ k ] , et renvoyer true si l'un de ces termes renvoie false . En fait, le rejet n'a besoin de vérifier que les termes qui dépendent de x [ k ], puisque les termes qui ne dépendent que de x [1], …, x [ k − 1] auront été testés plus haut dans l'arbre de recherche.

En supposant que le rejet soit implémenté comme ci-dessus, alors accept ( P , c ) n'a qu'à vérifier si c est complet, c'est-à-dire s'il a n éléments.

Il est généralement préférable d'ordonner la liste des variables de manière à ce qu'elle commence par les plus critiques (c'est-à-dire celles avec le moins d'options de valeur, ou qui ont un plus grand impact sur les choix ultérieurs).

On pourrait également permettre à la fonction suivante de choisir quelle variable doit être affectée lors de l'extension d'un candidat partiel, en fonction des valeurs des variables déjà affectées par elle. D'autres améliorations peuvent être obtenues par la technique de propagation de contraintes .

En plus de conserver les valeurs de récupération minimales utilisées lors de la sauvegarde, les implémentations de backtracking conservent généralement une piste variable pour enregistrer l'historique des modifications de valeur. Une implémentation efficace évitera de créer une entrée de piste variable entre deux changements successifs lorsqu'il n'y a pas de point de choix, car le retour en arrière effacera tous les changements en une seule opération.

Une alternative à la piste de variable consiste à conserver un horodatage du moment où la dernière modification a été apportée à la variable. L'horodatage est comparé à l'horodatage d'un point de choix. Si le point de choix a une heure associée postérieure à celle de la variable, il n'est pas nécessaire d'inverser la variable lorsque le point de choix est reculé, car elle a été modifiée avant que le point de choix ne se produise.

Voir également

Remarques

Les références

Lectures complémentaires

Liens externes