Das Zurückverfolgen ist ein allgemeiner Algorithmus, um alle (oder einige) Lösungen eines rechenbetonten Problems zu finden, das zusätzlich Kandidaten zu den Lösungen baut, und jeden teilweisen Kandidaten c ("Rückzüge") verlässt, sobald es beschließt, dass c zu einer gültigen Lösung nicht vielleicht vollendet werden kann.

Das klassische Lehrbuch-Beispiel des Gebrauches des Zurückverfolgens ist das acht Königin-Rätsel, das um alle Maßnahmen von acht Königinnen auf einem Standardschachbrett bittet, so dass keine Königin irgendwelchen anderer angreift. In der allgemeinen denselben Weg zurückverfolgenden Annäherung sind die teilweisen Kandidaten Maßnahmen von k Königinnen in den ersten k Reihen des Ausschusses, aller in verschiedenen Reihen und Säulen. Jede teilweise Lösung, die zwei gegenseitig angreifende Königinnen enthält, kann aufgegeben werden, da sie zu einer gültigen Lösung nicht vielleicht vollendet werden kann.

Das Zurückverfolgen kann nur für Probleme angewandt werden, die das Konzept einer "teilweisen Kandidat-Lösung" und eines relativ schnellen Tests dessen zulassen, ob es vielleicht zu einer gültigen Lösung vollendet werden kann. Es ist zum Beispiel nutzlos, für einen gegebenen Wert in einem nicht eingeordneten Tisch ausfindig zu machen. Wenn es jedoch anwendbar ist, ist das Zurückverfolgen häufig viel schneller als Enumeration der rohen Gewalt aller ganzen Kandidaten, da es eine Vielzahl von Kandidaten mit einem einzelnen Test beseitigen kann.

Das Zurückverfolgen ist ein wichtiges Werkzeug, um Einschränkungsbefriedigungsprobleme, wie Kreuzworträtsel, wörtliche Arithmetik, Sudoku und viele andere Rätsel zu beheben. Es ist häufig am günstigsten (wenn nicht am effizientesten) die Technik für die Syntaxanalyse, für das Rucksack-Problem und die anderen kombinatorischen Optimierungsprobleme. Es ist auch die Basis der so genannten Logikprogrammiersprachen wie Ikone, Planer und Einleitung. Das Zurückverfolgen wird auch im (diff) Unterschied-Motor für die Software von MediaWiki verwertet.

Das Zurückverfolgen hängt von benutzergegebenen "schwarzen Kasten-Verfahren" ab, die das Problem definieren, die Natur der teilweisen Kandidaten gelöst zu werden, und wie sie in ganze Kandidaten erweitert werden. Es ist deshalb ein metaheuristic aber nicht ein spezifischer Algorithmus - obwohl, verschieden von vielen andere Meta-Heuristik, wie man versichert, es alle Lösungen eines begrenzten Problems in einer begrenzten Zeitdauer findet.

Der Begriff "Rückzug" wurde vom amerikanischen Mathematiker D. H. Lehmer in den 1950er Jahren ins Leben gerufen. Die Pioniersprache der Schnur-Verarbeitung SNOBOL (1962) kann erst gewesen sein, um eine eingebaute allgemeine denselben Weg zurückverfolgende Möglichkeit zur Verfügung zu stellen.

Beschreibung der Methode

Der denselben Weg zurückverfolgende Algorithmus zählt eine Reihe teilweiser Kandidaten auf, die im Prinzip auf verschiedene Weisen vollendet werden konnten, alle möglichen Lösungen des gegebenen Problems zu geben. Die Vollziehung wird zusätzlich durch eine Folge von Kandidat-Erweiterungsschritten getan.

Begrifflich sind die teilweisen Kandidaten die Knoten einer Baumstruktur, des potenziellen Suchbaums. Jeder teilweise Kandidat ist der Elternteil der Kandidaten, die sich davon durch einen einzelnen Erweiterungsschritt unterscheiden; die Blätter des Baums sind die teilweisen Kandidaten, die noch weiter nicht erweitert werden können.

Der denselben Weg zurückverfolgende Algorithmus überquert diesen Suchbaum rekursiv von der Wurzel unten, in der Tiefe bestellen zuerst. An jedem Knoten c überprüft der Algorithmus, ob c zu einer gültigen Lösung vollendet werden kann. Wenn es nicht kann, wird der ganze an c eingewurzelte Subbaum (beschnitten) ausgelassen. Sonst, der Algorithmus (1) Kontrollen, ob c selbst eine gültige Lösung ist, und wenn es so beim Benutzer meldet; und (2) zählt rekursiv alle Subbäume von c auf. Die zwei Tests und die Kinder jedes Knotens werden durch benutzergegebene Verfahren definiert.

Deshalb ist der wirkliche Suchbaum, der durch den Algorithmus überquert wird, nur ein Teil des potenziellen Baums. Die Gesamtkosten des Algorithmus sind die Zahl von Knoten der wirklichen Baumzeiten die Kosten des Erreichens und der Verarbeitung jedes Knotens. Diese Tatsache sollte betrachtet werden, wenn man den potenziellen Suchbaum wählt und den Beschneidungstest durchführt.

Pseudocode

Um das Zurückverfolgen auf eine spezifische Klasse von Problemen anzuwenden, muss man die Daten P für das besondere Beispiel des Problems zur Verfügung stellen, das gelöst werden soll, und sechs Verfahrensrahmen, Wurzel, zurückweisen, erstens, als nächstes, und Produktion akzeptieren. Diese Verfahren sollten die Beispiel-Daten P als ein Parameter nehmen und sollten den folgenden tun:

1. Wurzel (P): Geben Sie den teilweisen Kandidaten an der Wurzel des Suchbaums zurück.
2. weisen Sie (P, c) zurück: Kehren Sie wahr nur zurück, wenn sich es nicht lohnt, den teilweisen Kandidaten c zu vollenden.
3. akzeptieren Sie (P, c): Kehren Sie wahr zurück, wenn c eine Lösung von P, und falsch sonst ist.
4. zuerst (P, c): Erzeugen Sie die erste Erweiterung des Kandidaten c.
5. als nächstes (P, s): Erzeugen Sie die folgende alternative Erweiterung eines Kandidaten, nach der Erweiterung s.
6. Produktion (P, c): Verwenden Sie die Lösung c von P, als passend zur Anwendung.

Der denselben Weg zurückverfolgende Algorithmus nimmt dann zum Anruf bt ab (Wurzel (P)), wo bt das folgende rekursive Verfahren ist:

Verfahren bt (c)

wenn zurückweisen (P, c) geben dann zurück

wenn (P, c) dann Produktion (P, c) akzeptieren

s  zuerst (P, c)

während s  Λ tun

bt (s)

s  als nächstes (P, s)

Gebrauch-Rücksichten

Das zurückweisen Verfahren sollte eine geboolean-schätzte Funktion sein, die wahr nur zurückkehrt, wenn es sicher ist, dass keine mögliche Erweiterung von c eine gültige Lösung für P ist. Wenn das Verfahren zu keinem bestimmten Schluss gelangen kann, sollte es falsch zurückkehren. Ein falsches wahres Ergebnis kann das bt Verfahren veranlassen, einige gültige Lösungen zu verpassen. Das Verfahren kann annehmen, dass zurückweisen (P, t) ist falsch für jeden Vorfahren t c im Suchbaum zurückgekehrt.

Andererseits hängt die Leistungsfähigkeit des denselben Weg zurückverfolgenden Algorithmus ab weisen das Zurückbringen zurück, das für Kandidaten wahr ist, die als der Wurzel als möglich nah sind. Wenn immer falschen Umsatz zurückweisen, wird der Algorithmus noch alle Lösungen finden, aber es wird zu einer Suche der rohen Gewalt gleichwertig sein.

Das akzeptieren Verfahren sollte wahr zurückkehren, wenn c eine ganze und gültige Lösung für das Problem-Beispiel P, und falsch sonst ist. Es kann annehmen, dass der teilweise Kandidat c und alle seine Vorfahren im Baum den zurückweisen Test bestanden haben.

Bemerken Sie, dass der allgemeine Pseudocode oben nicht annimmt, dass die gültigen Lösungen immer Blätter des potenziellen Suchbaums sind. Mit anderen Worten lässt es die Möglichkeit zu, dass eine gültige Lösung für P weiter erweitert werden kann, um andere gültige Lösungen nachzugeben.

Die ersten und folgenden Verfahren werden durch den denselben Weg zurückverfolgenden Algorithmus verwendet, um die Kinder eines Knotens c vom Baum, d. h. die Kandidaten aufzuzählen, die sich von c durch einen einzelnen Erweiterungsschritt unterscheiden. Der Anruf zuerst (P, c) sollte das erste Kind von c in einer Ordnung nachgeben; und der Anruf als nächstes (P, s) sollte die folgenden Geschwister des Knotens s in dieser Ordnung zurückgeben. Beide Funktionen sollten einen kennzeichnenden "ungültigen" Kandidaten, angezeigt hier durch 'Λ zurückgeben ', wenn das gebetene Kind nicht besteht.

Zusammen definieren die Wurzel, erstens, und folgenden Funktionen den Satz von teilweisen Kandidaten und dem potenziellen Suchbaum. Sie sollten gewählt werden, so dass jede Lösung von P irgendwo im Baum vorkommt, und kein teilweiser Kandidat mehr vorkommt als einmal. Außerdem sollten sie einen effizienten zulassen, und wirksame weisen Prädikat zurück.

Früh das Aufhören von Varianten

Der Pseudocode wird oben Produktion nach allen Kandidaten nennen, die eine Lösung des gegebenen Beispiels P sind. Der Algorithmus wird leicht modifiziert, um nach der Entdeckung der ersten Lösung oder einer bestimmten Anzahl von Lösungen anzuhalten; oder nach der Prüfung einer bestimmten Anzahl von teilweisen Kandidaten, oder nach Ausgaben eines gegebenen Betrags der Zentraleinheitszeit.

Beispiele

Typische Beispiele sind

• Rätsel wie acht Königinnen, sind Kreuzworträtsel, wörtliche Arithmetik, Sudoku, Haken-Solitär verwirrt
• kombinatorische Optimierungsprobleme wie Syntaxanalyse und das Rucksack-Problem
• Logikprogrammiersprachen wie Ikone, Planer und Einleitung, die das Zurückverfolgen innerlich verwenden, um Antworten zu erzeugen.
• Das Zurückverfolgen wird auch im "diff" (Version verwertet, die sich vergleicht) Motor für die Software von MediaWiki.

Unten ist ein Beispiel für das Einschränkungsbefriedigungsproblem:

Einschränkungsbefriedigung

Das allgemeine Einschränkungsbefriedigungsproblem besteht in der Entdeckung einer Liste von ganzen Zahlen x = (x [1], x [2], …, x [n]), jeder in einer Reihe {1, 2, …, M}, der etwas willkürliche Einschränkung (boolean Funktion) F befriedigt.

Für diese Klasse von Problemen würden die Beispiel-Daten P die ganzen Zahlen M und n und das Prädikat F sein. In einer typischen denselben Weg zurückverfolgenden Lösung dieses Problems konnte man einen teilweisen Kandidaten als eine Liste von ganzen Zahlen c = (c [1], c [2], … c [k]), für jeden k zwischen 0 und n definieren, die den ersten k Variablen x [1], x [2], …, x [k] zugeteilt werden sollen). Der Wurzelkandidat würde dann die leere Liste sein. Die ersten und folgenden Verfahren würden dann sein

fungieren Sie zuerst (P, c)

k  Länge (c)

wenn k = n

dann geben Sie Λ\zurück

kehren Sie sonst (c [1], c [2], …, c [k], 1) zurück

fungieren Sie als nächstes (P, s)

k  Länge (s)

wenn s [k] = M

dann geben Sie Λ\zurück

kehren Sie sonst (s [1], s [2], …, s [k-1], 1 + s [k]) zurück

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

Der Anruf weist zurück (P, c) sollte wahr zurückkehren, wenn die Einschränkung F durch keine Liste von n ganzen Zahlen zufrieden sein kann, die mit den k Elementen von c beginnt. Um denselben Weg zurückzuverfolgen, um wirksam zu sein, muss es eine Weise geben, diese Situation, mindestens für einige Kandidaten c zu entdecken, ohne ganz jene M N-Tupel aufzuzählen.

Zum Beispiel, wenn F die Verbindung von mehreren boolean Prädikaten, F = F [1] F [2] F [p] ist, und jeder F [ich] nur von einer kleinen Teilmenge der Variablen x [1], …, x [n] abhänge, dann konnte das zurückweisen Verfahren einfach die Begriffe F [ich] überprüfen, die nur von Variablen x [1], …, x [k], und wahre Rückkehr wenn einige jenes falschen Begriff-Umsatzes abhängen. Weisen Sie tatsächlich Bedürfnisse zurück nur überprüfen jene Begriffe, die wirklich von x [k] abhängen, seitdem die Begriffe, die nur von x [1], …, x [k-1] abhängen, weiter im Suchbaum geprüft worden sein werden.

Das Annehmen, die zurückweisen, wird als oben durchgeführt, dann akzeptieren Sie (P, c) muss nur überprüfen, ob c abgeschlossen ist, d. h. ob es n Elemente hat.

Es ist allgemein besser, die Liste von Variablen zu bestellen, so dass es mit den kritischsten beginnt (d. h. diejenigen mit wenigsten Wertoptionen, oder die einen größeren Einfluss auf nachfolgende Wahlen haben).

Man konnte auch der folgenden Funktion erlauben zu wählen, welche Variable zugeteilt werden sollte, wenn man einen teilweisen Kandidaten erweitert, der auf den Werten der dadurch bereits zugeteilten Variablen gestützt ist. Weitere Verbesserungen können durch die Technik der Einschränkungsfortpflanzung erhalten werden.

Zusätzlich zum Behalten von minimalen Wiederherstellungswerten ist darin gewöhnt gewesen zu unterstützen, denselben Weg zurückverfolgende Durchführungen behalten allgemein eine variable Spur, um Wertänderungsgeschichte zu registrieren. Eine effiziente Durchführung wird vermeiden, einen variablen Spur-Zugang zwischen zwei aufeinander folgenden Änderungen zu schaffen, wenn es keinen auserlesenen Punkt gibt, weil das Zurückverfolgen alle Änderungen als eine einzelne Operation löschen wird.

Eine Alternative zur variablen Spur soll einen Zeitstempel dessen behalten, als die letzte Änderung mit der Variable vorgenommen wurde. Der Zeitstempel ist im Vergleich zum Zeitstempel eines auserlesenen Punkts. Wenn der auserlesene Punkt eine verbundene Zeit später hat als diese der Variable, ist es unnötig, die Variable zurückzukehren, wenn der auserlesene Punkt denselben Weg zurückverfolgt wird, weil es geändert wurde, bevor der auserlesene Punkt vorgekommen ist.

Siehe auch

• Der Faden von Ariadne (Logik)
• Backjumping
• Recursion (Informatik)

Referenzen

Links

• HBmeyer.de, Interaktiver Zeichentrickfilm eines denselben Weg zurückverfolgenden Algorithmus
• Javanischer Beispielcode, Beispielcode, um von 8 Königin-Problem denselben Weg zurückzuverfolgen.