Rückspringen - Backjumping

Bei Backtracking- Algorithmen ist das Backjumping eine Technik, die den Suchraum reduziert und somit die Effizienz erhöht. Während das Backtracking im Suchbaum immer um eine Ebene nach oben geht, wenn alle Werte für eine Variable getestet wurden, kann das Backjumping um mehrere Ebenen nach oben gehen. In diesem Artikel wird eine feste Reihenfolge der Bewertung von Variablen verwendet, aber die gleichen Überlegungen gelten für eine dynamische Reihenfolge der Bewertung. ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$

• 

  Ein Suchbaum, der durch regelmäßiges Backtracking besucht wird

• 

  Ein Rücksprung: Der graue Knoten wird nicht besucht

Definition

Wenn beim Zurückverfolgen alle Werte für eine Variable versucht wurden, ohne eine Lösung zu finden, wird die letzte der zuvor zugewiesenen Variablen erneut überprüft, der Wert geändert oder das Zurückverfolgen fortgesetzt, wenn keine anderen Werte versucht werden sollen. Wenn es sich um die aktuelle Teilzuordnung handelt und alle Werte für versucht wurden, ohne eine Lösung zu finden, kommt das Backtracking zu dem Schluss, dass keine Lösungserweiterung vorhanden ist. Der Algorithmus "geht" dann auf , ändert den Wert, wenn möglich, und geht ansonsten erneut zurück. ${\ displaystyle x_ {1} = a_ {1}, \ ldots, x_ {k} = a_ {k}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {1} = a_ {1}, \ ldots, x_ {k} = a_ {k}}$${\ displaystyle x_ {k}}$${\ displaystyle x_ {k}}$

Die teilweise Zuordnung ist nicht immer vollständig erforderlich, um nachzuweisen, dass kein Wert von zu einer Lösung führt. Insbesondere kann ein Präfix der Teilzuweisung dieselbe Eigenschaft haben, dh es gibt einen Index , der nicht erweitert werden kann, um eine Lösung mit einem beliebigen Wert für zu bilden . Wenn der Algorithmus diese Tatsache beweisen kann, kann er direkt einen anderen Wert für berücksichtigen, anstatt ihn wie üblich zu überdenken . ${\ displaystyle x_ {k + 1}}$${\ displaystyle j <k}$${\ displaystyle x_ {1}, \ ldots, x_ {j} = a_ {1}, \ ldots, a_ {j}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {k}}$

Ein Beispiel, in dem die aktuelle Zuordnung zu mit jedem möglichen Wert von erfolglos versucht wurde . Das Zurückverfolgen geht zurück zu und versucht, ihm einen neuen Wert zuzuweisen. ${\ displaystyle x_ {1} x_ {2} x_ {3} x_ {4}}$${\ displaystyle x_ {5}}$${\ displaystyle x_ {4}}$	Statt Rückzieher macht der Algorithmus eine weitere Ausarbeitung beweisen, dass die Bewertungen , und sind nicht Teil einer Lösung. ${\ displaystyle x_ {1} x_ {2} x_ {5} = 211}$${\ displaystyle x_ {1} x_ {2} x_ {5} = 212}$${\ displaystyle x_ {1} x_ {2} x_ {5} = 213}$	Infolgedessen ist die aktuelle Auswertung von nicht Teil einer Lösung, und der Algorithmus kann direkt zurückspringen und einen neuen Wert dafür versuchen. ${\ displaystyle x_ {1} x_ {2}}$${\ displaystyle x_ {2}}$

Die Effizienz eines Rücksprungalgorithmus hängt davon ab, wie hoch er zurückspringen kann. Im Idealfall kann der Algorithmus von einer beliebigen Variablen springen , sodass die aktuelle Zuweisung nicht erweitert werden kann, um eine Lösung mit einem Wert von zu bilden . Wenn dies der Fall ist, spricht man von einem sicheren Sprung . ${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {1}, \ ldots, x_ {j}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle j}$

Es ist nicht immer möglich festzustellen, ob ein Sprung sicher ist, da sichere Sprünge anhand der Menge von Lösungen definiert werden, die der Algorithmus zu finden versucht. In der Praxis verwenden Backjumping-Algorithmen den niedrigsten Index, den sie effizient als sicheren Sprung erweisen können. Unterschiedliche Algorithmen verwenden unterschiedliche Methoden, um festzustellen, ob ein Sprung sicher ist. Diese Methoden haben unterschiedliche Kosten, aber höhere Kosten für das Finden eines höheren sicheren Sprungs können aufgrund des Überspringens von Teilen des Suchbaums gegen eine geringere Suchmenge eingetauscht werden.

Rückspringen an Blattknoten

Die einfachste Bedingung, unter der ein Rücksprung möglich ist, besteht darin, dass alle Werte einer Variablen ohne weitere Verzweigung als inkonsistent erwiesen wurden. Bei der Erfüllung von Einschränkungen ist eine Teilbewertung genau dann konsistent, wenn sie alle Einschränkungen erfüllt, an denen die zugewiesenen Variablen beteiligt sind, und ansonsten inkonsistent . Es kann vorkommen, dass eine konsistente Teillösung nicht zu einer konsistenten vollständigen Lösung erweitert werden kann, da einige der nicht zugewiesenen Variablen möglicherweise nicht zugewiesen werden können, ohne andere Einschränkungen zu verletzen.

Der Zustand, in dem alle Werte einer bestimmten Variablen nicht mit der aktuellen Teillösung übereinstimmen, wird als Blatt-Sackgasse bezeichnet . Dies geschieht genau dann, wenn die Variable ein Blatt des Suchbaums ist (was Knoten entspricht, die in den Abbildungen dieses Artikels nur Blätter als Kinder haben). ${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {1}, \ ldots, x_ {k} = a_ {1}, \ ldots, a_ {k}}$${\ displaystyle x_ {k + 1}}$

Der Backjumping-Algorithmus von Gaschnig führt einen Backjump nur in Blatt-Sackgassen durch. Mit anderen Worten, es funktioniert anders als das Backtracking nur, wenn jeder mögliche Wert von getestet wurde und inkonsistent ist, ohne dass über eine andere Variable verzweigt werden muss. ${\ displaystyle x_ {k + 1}}$

Ein sicherer Sprung kann gefunden werden, indem einfach für jeden Wert das kürzeste Präfix von inkonsistent mit bewertet wird . Mit anderen Worten, wenn ein möglicher Wert für ist , überprüft der Algorithmus die Konsistenz der folgenden Bewertungen: ${\ displaystyle a_ {k + 1}}$${\ displaystyle x_ {1}, \ ldots, x_ {k} = a_ {1}, \ ldots, a_ {k}}$${\ displaystyle x_ {k + 1} = a_ {k + 1}}$${\ displaystyle a_ {k + 1}}$${\ displaystyle x_ {k + 1}}$

${\ displaystyle x_ {1} = a_ {1}}$	...	${\ displaystyle x_ {k-1} = a_ {k-1}}$	${\ displaystyle x_ {k} = a_ {k}}$	${\ displaystyle x_ {k + 1} = a_ {k + 1}}$
${\ displaystyle x_ {1} = a_ {1}}$	...	${\ displaystyle x_ {k-1} = a_ {k-1}}$		${\ displaystyle x_ {k + 1} = a_ {k + 1}}$
...
${\ displaystyle x_ {1} = a_ {1}}$				${\ displaystyle x_ {k + 1} = a_ {k + 1}}$

Der kleinste Index (niedrigster Wert der Auflistung), für den die Bewertungen inkonsistent sind, wäre ein sicherer Sprung, wenn der einzig mögliche Wert für wäre . Da jede Variable normalerweise mehr als einen Wert annehmen kann, ist der maximale Index, der aus der Prüfung für jeden Wert hervorgeht, ein sicherer Sprung und der Punkt, an dem der Gaschnig-Algorithmus springt. ${\ displaystyle x_ {k + 1} = a_ {k + 1}}$${\ displaystyle x_ {k + 1}}$

In der Praxis kann der Algorithmus die obigen Bewertungen überprüfen, während er gleichzeitig die Konsistenz von überprüft . ${\ displaystyle x_ {k + 1} = a_ {k + 1}}$

Rückspringen an internen Knoten

Der vorherige Algorithmus springt nur zurück, wenn die Werte einer Variablen ohne weitere Verzweigung inkonsistent mit der aktuellen Teillösung angezeigt werden können. Mit anderen Worten, es ermöglicht einen Rücksprung nur an Blattknoten im Suchbaum.

Ein interner Knoten des Suchbaums repräsentiert eine Zuordnung einer Variablen, die mit den vorherigen übereinstimmt. Wenn keine Lösung diese Zuweisung erweitert, wird der vorherige Algorithmus immer zurückverfolgt: In diesem Fall wird kein Rücksprung durchgeführt.

Das Zurückspringen an internen Knoten kann nicht wie bei Blattknoten durchgeführt werden. In der Tat liegt es bei einigen Bewertungen der erforderlichen Verzweigung daran, dass sie mit der aktuellen Zuordnung übereinstimmen. Infolgedessen ist die Suche nach einem Präfix, das mit diesen Werten der letzten Variablen nicht übereinstimmt, nicht erfolgreich. ${\ displaystyle x_ {k + 1}}$

In solchen Fällen hat sich herausgestellt, dass eine Bewertung nicht Teil einer Lösung mit der aktuellen Teilbewertung ist, und zwar die rekursive Suche. Insbesondere "weiß" der Algorithmus, dass von diesem Punkt an keine Lösung existiert, da er zu diesem Knoten zurückkehrt, anstatt anzuhalten, nachdem er eine Lösung gefunden hat. ${\ displaystyle x_ {k + 1} = a_ {k + 1}}$${\ displaystyle x_ {1}, \ ldots, x_ {k}}$

Diese Rückkehr ist auf eine Reihe von Sackgassen zurückzuführen , an denen sich der Algorithmus als inkonsistente Teillösung erwiesen hat. Um weiter zurückzuspringen, muss der Algorithmus berücksichtigen, dass die Unmöglichkeit, Lösungen zu finden, auf diese Sackgassen zurückzuführen ist. Insbesondere sind die sicheren Sprünge Indizes von Präfixen, die diese Sackgassen immer noch zu inkonsistenten Teillösungen machen.

In diesem Beispiel kehrt der Algorithmus aufgrund der drei gekreuzten Inkonsistenzpunkte zu allen möglichen Werten zurück. ${\ displaystyle x_ {k + 1}}$	Der zweite Punkt bleibt inkonsistent, auch wenn die Werte von und aus der Teilbewertung entfernt werden (beachten Sie, dass sich die Werte einer Variablen in ihren untergeordneten Elementen befinden). ${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {k}}$	Die anderen inkonsistent Auswertungen bleibt so auch ohne , und${\ displaystyle x_ {k-2}}$${\ displaystyle x_ {k-1}}$${\ displaystyle x_ {k}}$	Der Algorithmus kann zurückspringen, da dies die niedrigste Variable ist, die alle Inkonsistenzen beibehält. Ein neuer Wert für wird versucht. ${\ displaystyle x_ {k-2}}$${\ displaystyle x_ {k-2}}$

Mit anderen Worten, wenn alle Werte von ausprobiert wurden, kann der Algorithmus zu einer vorherigen Variablen zurückspringen, vorausgesetzt, die aktuelle Wahrheitsbewertung von stimmt nicht mit allen Wahrheitsbewertungen von in den Blattknoten überein, die Nachkommen des Knotens sind . ${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {1}, \ ldots, x_ {i}}$${\ displaystyle x_ {k + 1}, x_ {k + 2}, ...}$${\ displaystyle x_ {k + 1}}$

Vereinfachungen

Bei der Suche nach einem möglichen Rücksprung für oder einen seiner Vorfahren können alle Knoten im schattierten Bereich ignoriert werden.${\ displaystyle x_ {k + 1}}$

Aufgrund der potenziell hohen Anzahl von Knoten, die sich im Teilbaum von befinden , werden die Informationen, die zum sicheren Zurückspringen erforderlich sind, während des Besuchs des Teilbaums gesammelt. Das Finden eines sicheren Sprungs kann durch zwei Überlegungen vereinfacht werden. Der erste ist, dass der Algorithmus einen sicheren Sprung benötigt, aber dennoch mit einem Sprung arbeitet, der nicht der höchstmögliche sichere Sprung ist. ${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {k + 1}}$

Die zweite Vereinfachung besteht darin, dass Knoten im Teilbaum , die von einem Rücksprung übersprungen wurden, bei der Suche nach einem Rücksprung ignoriert werden können . Genauer gesagt sind alle Knoten, die durch einen Rücksprung von Knoten zu Knoten übersprungen werden, für den Teilbaum, auf dem verwurzelt ist , irrelevant, und auch ihre anderen Teilbäume sind irrelevant. ${\ displaystyle x_ {l}}$${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$

Wenn ein Algorithmus über einen Pfad von Knoten zu übergegangen wäre, aber auf seinem Rückweg zurückspringt, hätte er stattdessen direkt von zu gehen können . In der Tat zeigt der Rücksprung an, dass die Knoten zwischen und für den Teilbaum, auf dem verwurzelt ist, irrelevant sind . Mit anderen Worten, ein Rücksprung zeigt an, dass der Besuch einer Region des Suchbaums ein Fehler war. Dieser Teil des Suchbaums kann daher ignoriert werden, wenn ein möglicher Rücksprung von oder von einem seiner Vorfahren in Betracht gezogen wird . ${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {l}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {m}}$${\ displaystyle x_ {l}}$

Variablen, deren Werte ausreichen, um die Unzufriedenheit in dem auf einem Knoten verwurzelten Teilbaum nachzuweisen, werden im Knoten gesammelt und beim Zurückziehen (nach Entfernen der Variablen des Knotens) an den obigen Knoten gesendet.

Diese Tatsache kann ausgenutzt werden, indem in jedem Knoten ein Satz zuvor zugewiesener Variablen gesammelt wird, deren Auswertung ausreicht, um zu beweisen, dass in dem auf dem Knoten verwurzelten Teilbaum keine Lösung vorhanden ist. Dieser Satz wird während der Ausführung des Algorithmus erstellt. Beim Zurückziehen von einem Knoten wird diese Menge die Variable des Knotens entfernt und in der Menge des Ziels des Zurückverfolgens oder Zurückspringens gesammelt. Da Knoten, die vom Rückspringen übersprungen werden, niemals zurückgezogen werden, werden ihre Sätze automatisch ignoriert.

Graphbasiertes Backjumping

Das Grundprinzip des graphbasierten Backjumping besteht darin, dass ein sicherer Sprung gefunden werden kann, indem überprüft wird, welche der Variablen in einer Einschränkung mit den Variablen stehen , die in Blattknoten instanziiert werden. Für jeden Blattknoten und jede Variable des Index , die dort instanziert wird, weniger die Indizes als oder gleich dessen Variable in einer Einschränkung ist , mit verwendet werden kann Sprünge sicher zu finden. Insbesondere wenn alle Werte für ausprobiert wurden, enthält dieser Satz die Indizes der Variablen, deren Auswertungen den Nachweis ermöglichen, dass durch Aufrufen des unter verwurzelten Teilbaums keine Lösung gefunden werden kann . Infolgedessen kann der Algorithmus zum höchsten Index in diesem Satz zurückspringen. ${\ displaystyle x_ {1}, \ ldots, x_ {k}}$${\ displaystyle x_ {k + 1}, x_ {k + 2}, ...}$${\ displaystyle x_ {i}}$${\ displaystyle i> k}$${\ displaystyle k}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {k + 1}}$${\ displaystyle x_ {k + 1}}$

Die Tatsache, dass durch Rückspringen übersprungene Knoten ignoriert werden können, wenn ein weiterer Rücksprung in Betracht gezogen wird, kann durch den folgenden Algorithmus ausgenutzt werden. Beim Zurückziehen von einem Blattknoten wird der Satz von Variablen, die mit ihm verknüpft sind, erstellt und im Falle eines Rücksprungs an sein übergeordnetes Element oder seinen Vorfahren "zurückgesendet". An jedem internen Knoten wird eine Reihe von Variablen verwaltet. Jedes Mal, wenn eine Gruppe von Variablen von einem ihrer untergeordneten Elemente oder Nachkommen empfangen wird, werden ihre Variablen der verwalteten Gruppe hinzugefügt. Beim weiteren Zurückverfolgen oder Zurückspringen vom Knoten wird die Variable des Knotens aus diesem Satz entfernt und der Satz an den Knoten gesendet, der das Ziel des Zurückverfolgens oder Zurückspringens ist. Dieser Algorithmus funktioniert, weil die in einem Knoten verwaltete Menge alle Variablen sammelt, die relevant sind, um die Unzufriedenheit in den Blättern zu beweisen, die von diesem Knoten abstammen. Da Variablensätze nur beim Zurückverfolgen von Knoten gesendet werden, werden die Sätze, die an Knoten gesammelt wurden, die durch Rückspringen übersprungen wurden, automatisch ignoriert.

Konfliktbasiertes Backjumping (auch als konfliktgesteuertes Backjumping (cbj) bezeichnet)

Ein noch verfeinerter Backjumping-Algorithmus, der manchmal größere Backjumps erzielen kann, basiert auf der Überprüfung nicht nur des gemeinsamen Vorhandenseins von zwei Variablen in derselben Einschränkung, sondern auch darauf, ob die Einschränkung tatsächlich Inkonsistenz verursacht hat. Insbesondere sammelt dieser Algorithmus eine der verletzten Einschränkungen in jedem Blatt. An jedem Knoten ist der höchste Index einer Variablen, der sich in einer der an den Blättern gesammelten Einschränkungen befindet, ein sicherer Sprung.

Während die in jedem Blatt gewählte verletzte Einschränkung die Sicherheit des resultierenden Sprungs nicht beeinflusst, erhöht die Auswahl von Einschränkungen mit höchstmöglichen Indizes die Höhe des Sprungs. Aus diesem Grund werden konfliktbasierte Einschränkungen für Rücksprungreihenfolgen, so dass Einschränkungen gegenüber Variablen mit niedrigeren Indizes gegenüber Einschränkungen für Variablen mit höheren Indizes bevorzugt werden.

Formal wird eine Einschränkung einer anderen vorgezogen, wenn der höchste Index einer Variablen in, aber nicht in niedriger ist als der höchste Index einer Variablen in, aber nicht in . Mit anderen Worten, mit Ausnahme gemeinsamer Variablen wird die Einschränkung bevorzugt, die alle niedrigeren Indizes aufweist. ${\ displaystyle C}$${\ displaystyle D}$${\ displaystyle C}$${\ displaystyle D}$${\ displaystyle D}$${\ displaystyle C}$

In einem Blattknoten wählt der Algorithmus den niedrigsten Index so aus, dass er nicht mit der zuletzt im Blatt ausgewerteten Variablen übereinstimmt. Unter den Einschränkungen, gegen die in dieser Bewertung verstoßen wird, wählt es die am meisten bevorzugte aus und sammelt alle seine Indizes kleiner als . Auf diese Weise identifiziert der niedrigste gesammelte Index einen sicheren Sprung , wenn der Algorithmus zur Variablen zurückkehrt . ${\ displaystyle i}$${\ displaystyle x_ {1}, \ ldots, x_ {i}}$${\ displaystyle k + 1}$${\ displaystyle x_ {k + 1}}$

In der Praxis wird dieser Algorithmus vereinfacht, indem alle Indizes in einer einzigen Menge gesammelt werden, anstatt für jeden Wert von eine Menge zu erstellen . Insbesondere sammelt der Algorithmus in jedem Knoten alle Mengen, die von seinen Nachkommen stammen und nicht durch Rückspringen übersprungen wurden. Beim Zurückziehen von diesem Knoten wird dieser Satz die Variable des Knotens entfernt und am Ziel des Zurückverfolgens oder Zurückspringens gesammelt. ${\ displaystyle k}$

Konfliktorientiertes Backjumping wurde von Patrick Prosser in seiner wegweisenden Arbeit von 1993 für Constraint Satisfaction Problems vorgeschlagen .

Siehe auch

• Backtracking
• Constraint-Lernen

Verweise

• Dechter, Rina (2003). Constraint-Verarbeitung . Morgan Kaufmann. ISBN 1-55860-890-7.
• Prosser, Patrick (1993). "Hybride Algorithmen für das Problem der Constraint-Zufriedenheit" (PDF) . Computational Intelligence 9 (3). Zitierjournal benötigt |journal=( Hilfe )