Publié · en amélioration
Algorithm
Le backtracking construit une solution pas à pas et annule les choix qui violent une contrainte, pour les permutations, les N reines ou le sudoku.
Le backtracking, ou retour sur trace, construit la réponse étape par étape en parcourant en profondeur un arbre d'états ; dès que les choix déjà faits violent une contrainte, il revient à l'étape précédente pour essayer une autre option. Le code répète trois gestes : choisir un candidat, explorer récursivement, puis annuler ce choix au retour.
Contrairement à la force brute, qui génère chaque candidat complet avant de le vérifier, le backtracking élague tôt les branches sans issue et résout souvent le même problème avec des ordres de grandeur d'étapes en moins. C'est la méthode de référence pour énumérer permutations et combinaisons et pour les problèmes de satisfaction de contraintes comme les N reines, le sudoku ou la coloration de graphes ; il est aussi au cœur des moteurs d'expressions régulières et des solveurs SAT, si bien qu'on le croise en entretien technique comme en production.
Commencez par des énumérations sans élagage, comme les sous-ensembles et les permutations, pour assimiler le schéma choisir, explorer, annuler. Entraînez-vous ensuite à la vérification des contraintes et à l'élagage avec les N reines et le sudoku. Enfin, comptez les nœuds visités pour mesurer l'effet de l'élagage et comparez les mêmes problèmes avec la programmation dynamique.
Avec l'état vide pour racine et chaque choix pour arête, chaque candidat devient un chemin, et le backtracking parcourt cet arbre en profondeur.
On ajoute un candidat à la solution partielle, on descend récursivement puis on le retire au retour, si bien que toutes les branches partagent une seule liste.
Quand une solution partielle ne peut plus mener à une réponse, tout le sous-arbre est ignoré, ce qui réduit fortement en pratique un espace de recherche exponentiel.
Garder les colonnes, diagonales, lignes ou blocs occupés dans des ensembles ou des tableaux permet de savoir en temps constant si un choix enfreint une règle.
permutations bloque les éléments déjà choisis avec un tableau used et produit toutes les permutations selon le schéma choisir, explorer, annuler, en stockant chaque chemin complet sous forme de copie avec path[:]. n_queens suit les colonnes et les deux diagonales (row - c, row + c) dans des ensembles, saute aussitôt les cases attaquées et compte les solutions. python backtracking.py affiche les 6 permutations de [1, 2, 3] et 92, le nombre de solutions pour 8 reines.
backtracking.py
def permutations(items):
result, path = [], []
used = [False] * len(items)
def backtrack():
if len(path) == len(items):
result.append(path[:]) # store a copy of the full path
return
for i, x in enumerate(items):
if used[i]:
continue
used[i] = True # choose
path.append(x)
backtrack() # explore
path.pop() # unchoose
used[i] = False
backtrack()
return result
def n_queens(n):
cols, diag, anti = set(), set(), set()
def place(row):
if row == n:
return 1
count = 0
for c in range(n):
if c in cols or row - c in diag or row + c in anti:
continue # prune: square is attacked
cols.add(c); diag.add(row - c); anti.add(row + c)
count += place(row + 1)
cols.remove(c); diag.remove(row - c); anti.remove(row + c)
return count
return place(0)
print(permutations([1, 2, 3]))
print(n_queens(8)) # 92
python backtracking.pySix chapitres pour aller de l'installation aux notions essentielles de Backtracking (retour sur trace).
Posez vos questions, partagez votre expérience et échangez vos avis sur Backtracking (retour sur trace).
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.