Algorithmus
Backtracking baut eine Lösung schrittweise auf und nimmt Entscheidungen zurück, die eine Bedingung verletzen, etwa bei Permutationen, N-Damen oder Sudoku.
Backtracking füllt eine Lösung Schritt für Schritt, durchsucht dabei einen Zustandsbaum in Tiefensuche und kehrt zum vorherigen Schritt zurück, sobald die bisherigen Entscheidungen eine Bedingung verletzen. Der Code besteht aus drei wiederkehrenden Schritten: einen Kandidaten wählen, rekursiv weitersuchen und die Wahl beim Rückweg wieder aufheben.
Anders als die Brute-Force-Suche, die jeden vollständigen Kandidaten erst erzeugt und dann prüft, schneidet Backtracking aussichtslose Zweige früh ab und kommt oft mit um Größenordnungen weniger Schritten aus. Es ist der Standardansatz zum Aufzählen von Permutationen und Kombinationen sowie für Constraint-Probleme wie das N-Damen-Problem, Sudoku oder Graphfärbung und steckt in Regex-Engines und SAT-Solvern. Deshalb begegnet es einem in Programmierinterviews ebenso wie im Produktivcode.
Beginnen Sie mit Aufzählungen ohne Beschneidung, etwa Teilmengen und Permutationen, um das Muster Wählen, Erkunden, Zurücknehmen zu verinnerlichen. Üben Sie danach Bedingungsprüfung und Pruning am N-Damen-Problem und an Sudoku. Zählen Sie schließlich die besuchten Knoten, um den Effekt des Prunings zu sehen, und vergleichen Sie dieselben Aufgaben mit dynamischer Programmierung.
Mit dem leeren Zustand als Wurzel und jeder Entscheidung als Kante wird jeder Kandidat zu einem Pfad, den Backtracking in Tiefensuche durchläuft.
Ein Kandidat wird zur Teillösung hinzugefügt, rekursiv weitergesucht und beim Rücksprung wieder entfernt, sodass alle Zweige eine Liste teilen.
Kann eine Teillösung zu keiner Lösung mehr führen, wird der gesamte Teilbaum übersprungen, was den exponentiellen Suchraum in der Praxis stark verkleinert.
Werden belegte Spalten, Diagonalen, Zeilen oder Blöcke in Mengen oder Arrays geführt, lässt sich ein Regelverstoß in konstanter Zeit erkennen.
permutations sperrt bereits gewählte Elemente mit einem used-Array und erzeugt alle Permutationen nach dem Muster Wählen, Erkunden, Zurücknehmen; jeder fertige Pfad wird mit path[:] als Kopie gespeichert. n_queens verwaltet Spalten und beide Diagonalen (row - c, row + c) in Mengen, überspringt bedrohte Felder sofort und zählt die Lösungen. python backtracking.py gibt die 6 Permutationen von [1, 2, 3] und 92 Lösungen für 8 Damen aus.
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.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Backtracking.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Backtracking aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.