L’algorithme de retour en arrière énumère un ensemble de candidats partiels qui, en principe, pourraient être complétés de différentes manières pour donner toutes les solutions possibles au problème donné. L’achèvement se fait progressivement, par une séquence d’étapes d’extension candidate.
Conceptuellement, les candidats partiels sont représentés comme les nœuds d’une arborescence, l’arbre de recherche potentiel. Chaque candidat partiel est le parent des candidats qui en diffèrent par une seule étape d’extension; les feuilles de l’arbre sont les candidats partiels qui ne peuvent plus être prolongés.
L’algorithme de retour en arrière parcourt cet arbre de recherche de manière récursive, de la racine vers le bas, en profondeur – premier ordre. À chaque noeud c, l’algorithme vérifie si c peut être complété par une solution valide. S’il ne le peut pas, tout le sous-arbre enraciné en c est ignoré (élagué). Sinon, l’algorithme (1) vérifie si c lui-même est 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 données par l’utilisateur.
Par conséquent, l’arbre de recherche réel parcouru 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.
PseudocodeEdit
Pour 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, root, reject, accept, first, next et output. Ces procédures doivent prendre les données d’instance P comme paramètre et effectuer les opérations suivantes:
- root(P) : renvoie le candidat partiel à la racine de l’arbre de recherche.
- reject(P, c): renvoie true uniquement si le candidat partiel c ne vaut pas la peine d’être complété.
- accepter (P, c): renvoie true si c est une solution de P, et false sinon.
- first(P, c) : génère la première extension du candidat c.
- next(P, s) : génère la prochaine extension alternative d’un candidat, après l’extension s.
- output(P, c) : utilise la solution c de P, en fonction de l’application.
L’algorithme de retour en arrière réduit le problème à l’appel backtrack(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’utilisationsedit
La procédure de rejet doit être une fonction à valeur booléenne qui ne renvoie true que s’il est certain qu’aucune extension possible de c n’est une solution valide pour P. Si la procédure ne peut pas parvenir à une conclusion définitive, elle doit renvoyer false. Un résultat vrai incorrect peut faire manquer à la procédure bt certaines solutions valides. La procédure peut supposer que reject(P, t) renvoie false pour chaque ancêtre t de c dans l’arbre de recherche.
D’autre part, l’efficacité de l’algorithme de retour en arrière dépend du rejet renvoyant true pour les candidats aussi proches que possible de la racine. Si reject renvoie toujours false, l’algorithme trouvera toujours toutes les solutions, mais ce sera équivalent à une recherche par force brute.
La procédure d’acceptation doit renvoyer true si c est une solution complète et valide pour l’instance de problème P, et false sinon. On 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 encore étendue pour donner d’autres solutions valides.
La première et la suivante procédures sont utilisées par l’algorithme de retour en 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 en premier (P, c) devrait donner le premier enfant de c, dans un certain ordre; et l’appel next (P, s) devrait renvoyer le prochain frère du nœud s, dans cet ordre. Les deux fonctions doivent renvoyer un candidat « NUL » 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 sorte que chaque solution de P se produise 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 efficace et efficace.
Early stopping variantsEdit
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é une quantité donnée de temps CPU.