Rückverfolgung - Backtracking

Informationen zum Liniensuchalgorithmus , der bei der uneingeschränkten Optimierung verwendet wird , finden Sie unter Zurückverfolgen der Liniensuche .
Graph und Baumsuchalgorithmen
Einträge
verwandte Themen

Backtracking ist ein allgemeiner Algorithmus zum Finden von Lösungen für einige Rechenprobleme , insbesondere Constraint-Zufriedenheitsprobleme , der inkrementell Kandidaten für die Lösungen erstellt und einen Kandidaten aufgibt ("Backtracks"), sobald er feststellt, dass der Kandidat unmöglich zu einem gültigen Ergebnis abgeschlossen werden kann Lösung.

Das klassische Lehrbuchbeispiel für den Einsatz von Backtracking ist das acht Damen Puzzle , das für alle Arrangements von acht fragt Schachköniginnen auf einem Standard - Schachbrett , so dass keine Königin Angriffe andere. Beim üblichen Backtracking-Ansatz sind die Teilkandidaten Anordnungen von k Damen in den ersten k Reihen des Bretts, alle in verschiedenen Reihen und Spalten. Jede Teillösung, die zwei sich gegenseitig angreifende Damen enthält, kann aufgegeben werden.

Backtracking kann nur für Probleme angewendet werden, die das Konzept einer "Teillösungskandidatenlösung" und einen relativ schnellen Test, ob es möglicherweise zu einer gültigen Lösung vervollständigt werden kann, zulassen. Es ist beispielsweise nutzlos, um einen bestimmten Wert in einer ungeordneten Tabelle zu finden. Wenn es anwendbar ist, ist Backtracking jedoch oft viel schneller als die Brute-Force-Aufzählung aller vollständigen Kandidaten, da es viele Kandidaten mit einem einzigen Test eliminieren kann.

Backtracking ist ein wichtiges Werkzeug zum Lösen von Constraint-Erfüllungsproblemen , wie Kreuzworträtseln , verbalen Arithmetik , Sudoku und vielen anderen Rätseln. Es ist oft die bequemste Technik zum Parsen , für das Rucksackproblem und andere kombinatorische Optimierungsprobleme . Es ist auch die Grundlage der sogenannten logischen Programmiersprachen wie Icon , Planner und Prolog .

Das Backtracking hängt von benutzerspezifischen " Black-Box-Verfahren " ab, die das zu lösende Problem, die Art der Teilkandidaten und ihre Erweiterung zu vollständigen Kandidaten definieren. Es handelt sich also eher um eine Metaheuristik als um einen bestimmten Algorithmus – obwohl sie im Gegensatz zu vielen anderen Meta-Heuristiken garantiert alle Lösungen für ein endliches Problem in einer begrenzten Zeit findet.

Der Begriff „Backtrack“ wurde in den 1950er Jahren vom amerikanischen Mathematiker DH Lehmer geprägt . Die bahnbrechende Zeichenfolgenverarbeitungssprache SNOBOL (1962) war möglicherweise die erste, die eine eingebaute allgemeine Backtracking-Funktion bereitstellte.

Beschreibung der Methode

Der Backtracking-Algorithmus zählt eine Menge von Teilkandidaten auf , die im Prinzip auf verschiedene Weise vervollständigt werden könnten , um alle möglichen Lösungen für das gegebene Problem zu liefern. Die Vervollständigung erfolgt inkrementell durch eine Folge von Kandidatenerweiterungsschritten.

Konzeptionell werden die Teilkandidaten als Knoten einer Baumstruktur dargestellt , dem potentiellen Suchbaum. Jeder Teilkandidat ist der Elternteil der Kandidaten, die sich durch einen einzelnen Erweiterungsschritt von ihm unterscheiden; die Blätter des Baumes sind die Teilkandidaten, die nicht weiter ausgedehnt werden können.

Der Backtracking-Algorithmus durchläuft diesen Suchbaum rekursiv von der Wurzel abwärts in der Tiefe erster Ordnung . An jedem Knoten c prüft der Algorithmus, ob c zu einer gültigen Lösung vervollständigt werden kann. Wenn dies nicht möglich ist, wird der gesamte bei c verwurzelte Unterbaum übersprungen ( beschnitten ). Andernfalls prüft der Algorithmus (1), ob c selbst eine gültige Lösung ist, und wenn ja, teilt er dies dem Benutzer mit; und (2) zählt alle Unterbäume von c rekursiv auf . Die beiden Tests und die Kinder jedes Knotens werden durch benutzerdefinierte Prozeduren definiert.

Daher ist der eigentliche Suchbaum , den der Algorithmus durchläuft, nur ein Teil des Potenzialbaums. Die Gesamtkosten des Algorithmus sind die Anzahl der Knoten des tatsächlichen Baums multipliziert mit den Kosten für das Erhalten und Verarbeiten jedes Knotens. Diese Tatsache sollte bei der Auswahl des potentiellen Suchbaums und der Durchführung des Pruning-Tests berücksichtigt werden.

Pseudocode

Um Backtracking auf eine bestimmte Klasse von Problemen anzuwenden, muss man die Daten P für die spezielle Instanz des zu lösenden Problems und sechs Verfahrensparameter , root , Reject , Accept , first , next und output , bereitstellen . Diese Prozeduren sollten die Instanzdaten P als Parameter verwenden und Folgendes tun:

  1. root ( P ): Gibt den partiellen Kandidaten an der Wurzel des Suchbaums zurück.
  2. ablehnen ( P , c ): nur wahr zurückgeben , wenn der Teilkandidat c nicht vervollständigt werden kann.
  3. akzeptieren ( P , c ): true zurückgeben, wenn c eine Lösung von P ist , andernfalls false .
  4. first ( P , c ): erzeuge die erste Erweiterung des Kandidaten c .
  5. next ( P , s ): Erzeuge die nächste alternative Erweiterung eines Kandidaten nach der Erweiterung s .
  6. Ausgabe ( P , c ): Verwenden Sie die Lösung c von P , je nach Anwendung.

Der Backtracking-Algorithmus reduziert das Problem auf den Call Backtrack ( root ( P )), wobei Backtrack das folgende rekursive Verfahren ist: 

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)

Nutzungsüberlegungen

Die Zurückweisungsprozedur sollte eine boolesche Funktion sein , die nur dann wahr zurückgibt , wenn sicher ist, dass keine mögliche Erweiterung von c eine gültige Lösung für P ist . Wenn die Prozedur keine eindeutige Schlussfolgerung ziehen kann, sollte sie false zurückgeben . Ein falsches wahres Ergebnis kann dazu führen, dass das bt- Verfahren einige gültige Lösungen übersieht . Die Prozedur kann annehmen, dass die Zurückweisung ( P , t ) für jeden Vorfahren t von c im Suchbaum falsch zurückgegeben hat .

Andererseits hängt die Effizienz des Backtracking-Algorithmus davon ab , dass die Zurückweisung für Kandidaten, die so nah wie möglich an der Wurzel liegen, wahr zurückgibt. Wenn Reject immer false zurückgibt , findet der Algorithmus immer noch alle Lösungen, entspricht aber einer Brute-Force-Suche.

Die Annahmeprozedur sollte wahr zurückgeben, wenn c eine vollständige und gültige Lösung für die Probleminstanz P ist , andernfalls sollte sie falsch sein . Es kann davon ausgegangen werden, dass der Teilkandidat c und alle seine Vorfahren im Baum den Zurückweisungstest bestanden haben.

Der obige allgemeine Pseudocode geht nicht davon aus, dass die gültigen Lösungen immer Blätter des potentiellen Suchbaums sind. Mit anderen Worten, es lässt die Möglichkeit zu, dass eine gültige Lösung für P weiter erweitert werden kann, um andere gültige Lösungen zu erhalten.

Die erste und die nächste Prozedur werden vom Rückverfolgungsalgorithmus verwendet, um die Kinder eines Knotens c des Baums aufzuzählen, dh die Kandidaten, die sich von c um einen einzelnen Erweiterungsschritt unterscheiden. Der Aufruf zuerst ( P , c ) sollte das erste Kind von c in einer bestimmten Reihenfolge ergeben; und der Aufruf next ( P , s ) sollte das nächste Geschwister des Knotens s in dieser Reihenfolge zurückgeben. Beide Funktionen sollten einen eindeutigen "NULL"-Kandidaten zurückgeben, wenn das angeforderte Kind nicht existiert.

Zusammen definieren die Funktionen root , first und next die Menge der Teilkandidaten und den potentiellen Suchbaum. Sie sollten so gewählt werden, dass jede Lösung von P irgendwo im Baum vorkommt und kein Teilkandidat mehr als einmal vorkommt. Darüber hinaus sollten sie ein effizientes und effektives Ablehnungsprädikat zulassen .

Frühstopp-Varianten

Der obige Pseudocode ruft die Ausgabe für alle Kandidaten auf, die eine Lösung für die gegebene Instanz P sind . Der Algorithmus kann so modifiziert werden, dass er stoppt, nachdem die erste Lösung oder eine bestimmte Anzahl von Lösungen gefunden wurde; oder nach dem Testen einer bestimmten Anzahl von Teilkandidaten oder nachdem eine bestimmte Menge an CPU- Zeit verbraucht wurde.

Beispiele

Ein durch Backtracking gelöstes Sudoku .

Beispiele, bei denen Backtracking verwendet werden kann, um Rätsel oder Probleme zu lösen, sind:

Im Folgenden sehen Sie ein Beispiel, bei dem Backtracking für das Problem der Einschränkungszufriedenheit verwendet wird :

Zufriedenheit mit Einschränkungen

Das allgemeine Problem der Einschränkungserfüllung besteht darin, eine Liste von ganzen Zahlen x = ( x [1], x [2], …, x [ n ]) zu finden , jede in einem bestimmten Bereich {1, 2, …, m }, die einige willkürliche Einschränkung (boolesche Funktion) F .

Für diese Klasse von Problemen, die Instanzdaten P wäre die ganzen Zahlen m und n , und das Prädikat F . In einer typischen Backtracking-Lösung für dieses Problem könnte man einen partiellen Kandidaten als eine Liste von ganzen Zahlen c = ( c [1], c [2], …, c [k]) für jedes k zwischen 0 und n definieren , das sind den ersten k Variablen x [1], x [2], …, x [ k ] zuzuordnen . Der Wurzelkandidat wäre dann die leere Liste (). Die erste und nächste Prozedur wäre dann 

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])

Hier ist Länge ( c ) die Anzahl der Elemente in der Liste c .

Die Anrufabweisung ( P , c ) sollte wahr zurückgeben, wenn die Einschränkung F nicht von einer Liste von n ganzen Zahlen erfüllt werden kann , die mit den k Elementen von c beginnt . Damit Backtracking effektiv ist, muss es zumindest für einige Kandidaten c eine Möglichkeit geben, diese Situation zu erkennen , ohne all diese m n − k n -Tupel aufzuzählen.

Wenn beispielsweise F die Konjunktion mehrerer boolescher Prädikate ist, ist F = F [1] ∧ F [2] ∧ … ∧ F [ p ] , und jedes F [ i ] hängt nur von einer kleinen Teilmenge der Variablen x [1 ], …, x [ n ] , dann könnte die Zurückweisungsprozedur einfach die Terme F [ i ] prüfen , die nur von den Variablen x [1], …, x [ k ] abhängen , und true zurückgeben, wenn einer dieser Terme false zurückgibt . Tatsächlich braucht die Zurückweisung nur diejenigen Terme zu prüfen, die von x [ k ] abhängen , da die Terme, die nur von x [1], …, x [ k − 1] abhängen , weiter oben im Suchbaum getestet wurden.

Angenommen, die Zurückweisung ist wie oben implementiert, dann braucht akzeptieren ( P , c ) nur zu prüfen, ob c vollständig ist, dh ob es n Elemente hat.

Im Allgemeinen ist es besser, die Liste der Variablen so zu ordnen, dass sie mit den kritischsten beginnt (dh denjenigen mit den wenigsten Wertoptionen oder die einen größeren Einfluss auf nachfolgende Entscheidungen haben).

Man könnte der nächsten Funktion auch überlassen, welche Variable beim Erweitern eines Teilkandidaten zugewiesen werden soll, basierend auf den Werten der von ihr bereits zugewiesenen Variablen. Weitere Verbesserungen können durch die Technik der Beschränkungsausbreitung erzielt werden .

Zusätzlich zur Beibehaltung der minimalen Wiederherstellungswerte, die beim Sichern verwendet werden, führen Backtracking-Implementierungen üblicherweise eine variable Spur, um die Werteänderungshistorie aufzuzeichnen. Eine effiziente Implementierung vermeidet das Erstellen eines variablen Trail-Eintrags zwischen zwei aufeinanderfolgenden Änderungen, wenn es keinen Auswahlpunkt gibt, da das Zurückverfolgen alle Änderungen als eine einzige Operation löscht.

Eine Alternative zum Variablen-Trail besteht darin, einen Zeitstempel zu führen, wann die letzte Änderung an der Variablen vorgenommen wurde. Der Zeitstempel wird mit dem Zeitstempel eines Auswahlpunkts verglichen. Wenn der Auswahlpunkt eine spätere zugeordnete Zeit als die Variable hat, ist es nicht erforderlich, die Variable zurückzusetzen, wenn der Auswahlpunkt zurückverfolgt wird, da sie geändert wurde, bevor der Auswahlpunkt aufgetreten ist.

Siehe auch

Anmerkungen

Verweise

Weiterlesen

Externe Links