Recherche par retour sur trace
Le retour sur trace effectue une recherche en profondeur dans un arbre de décisions. Il fait un choix, met l'état à jour, explore, puis rétablit exactement l'état précédent avant d'essayer le choix suivant.
def search(state):
if is_solution(state):
record(state.copy())
return
for choice in candidates(state):
if not feasible(state, choice):
continue
apply(state, choice)
search(state)
undo(state, choice)
Liste de contrôle pour la conception
- Définissez ce que représente un niveau de l'arbre de recherche.
- Déterminez si les choix portent sur des positions, des valeurs, des arêtes ou des affectations.
- Rendez explicites la condition de solution et la manière dont le résultat est conservé ou copié.
- Associez à chaque mutation une annulation exacte, y compris sur les chemins qui retournent plus tôt.
- N'ajoutez que des règles d'élagage dont il est prouvé qu'elles ne peuvent supprimer aucune solution valide requise.
Types d'élagage
- Faisabilité : une contrainte est déjà violée.
- Symétrie : des choix équivalents produiraient des états en double.
- Bornes : même la meilleure continuation possible ne peut améliorer la meilleure solution courante.
- Mémoïsation : le même état résiduel a déjà été résolu ; la méthode commence alors à recouper la programmation dynamique.
Complexité
Le temps dans le pire cas est souvent exponentiel ou factoriel, car la sortie ou l'espace de recherche possède lui-même cette taille. L'élagage réduit l'exploration de certaines instances sans nécessairement changer la classe du pire cas. Hors stockage des résultats, la profondeur de pile est généralement proportionnelle au nombre de décisions.
Utilisez le retour sur trace lorsqu'une solution concrète ou une énumération complète est requise et que les contraintes permettent de rejeter tôt des affectations partielles.
Terminaison et énumération complète
Une entrée finie ne garantit pas à elle seule la terminaison : chaque appel doit diminuer une mesure bien fondée, comme le nombre de positions non affectées. Explorer un graphe plutôt qu'un arbre de décisions peut demander un ensemble de sommets visités propre au chemin pour éviter les cycles. Un ensemble global peut supprimer à tort des solutions différentes atteignant le même sommet avec des historiques distincts.
Le modèle ci-dessus s'arrête dès qu'il trouve une solution : il suppose donc qu'elles sont des feuilles ou que leurs extensions ne doivent pas être rapportées. Pour une somme de sous-ensemble à valeurs positives, atteindre la cible permet de retourner ; avec des zéros, prolonger une solution peut en produire d'autres. De même, une copie superficielle suffit pour une liste d'entiers immuables, mais pas forcément pour un état mutable imbriqué.
Pour deux choix binaires, les chemins sont 00,01,10,11 : ajoutez 0, explorez les deux seconds choix, retirez 0, puis recommencez avec 1. Après chaque retour, le chemin doit retrouver exactement sa valeur d'entrée. L'exhaustivité vient de ce que chaque solution valide possède une suite de choix, et qu'un élagage sûr n'en retire aucune qui doive être produite. Une énumération exhaustive de petits cas aide à contrôler une nouvelle règle d'élagage.
Deux arbres de décision concrets
Les permutations illustrent le choix d’un élément inutilisé, la restauration de l’état et l’élimination des doublons. La somme de sous-ensemble distingue inclusion et exclusion, puis explique pourquoi zéros et valeurs négatives changent les élagages valides. Le parcours sous-jacent est la recherche en profondeur, mais chaque chemin porte ses décisions, pas seulement un ensemble de sommets visités.