Backtracking

Backtracking

Copyright © Shutterstock / OpturaDesign

Was ist Backtracking?

Definition

Backtracking (Rückverfolgung) ist eine allgemeine algorithmische Technik, die die Suche nach jeder möglichen Kombination berücksichtigt, um ein Optimierungsproblem zu lösen. Backtracking wird auch als Tiefensuche oder Verzweigen und Binden bezeichnet.

Durch das Einfügen von mehr Wissen über das vorhandene Problem, kann der Suchbaum beschnitten werden, um Fälle zu vermeiden, die nicht vielversprechend aussehen. Backtracking eignet sich insbesondere für komplexe Probleme.
Eine dynamische Programmierung und Greedy-Algorithmen können als Optimierung des Backtrackings betrachtet werden, weshalb diese Technik nützlich ist, um fortgeschrittene Konzepte zu verstehen.

Ziel

Backtracking hilft bei der Lösung eines allgemeinen Problems, indem es eine Lösung für das erste Teilproblem findet und dann rekursiv versucht, andere Teilprobleme basierend auf der Lösung des ersten Problems zu lösen. Wenn das aktuelle Problem nicht gelöst werden kann, wird der Schritt rückgängig gemacht und die nächste mögliche Lösung wird auf die vorherigen Schritte angewendet und geht dann weiter. Die Rekursion ist beim Zurückverfolgen ein wichtiger Teil. Ein Backtracking Algorithmus endet, wenn für das erste Teilproblem kein Lösung mehr erzielt werden kann.

Der Backtracking Algorithmus zählt eine Reihe von Teilkandidaten auf, die im Prinzip auf verschiedene Arten vervollständigt werden könnten, um dem gegebenen Problem alle möglichen Lösungen zu geben. Die Vervollständigung erfolgt inkrementell durch eine Folge von sogenannten Kandidaten-Erweiterungsschritten.

Konzeptionell werden die Teilkandidaten als Knoten einer Baumstruktur, dem potentiellen Suchbaum, dargestellt. Jeder Teilkandidat ist der “Elternteil” der Kandidaten, der sich von ihm durch einen einzigen Erweiterungsschritt unterscheidet: 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 Reihenfolge 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 unter “c” verwurzelte Unterbaum übersprungen (beschnitten). Andernfalls prüft der Algorithmus, ob “c” selbst eine gültige Lösung ist und meldet dies dem Benutzer; er zählt rekursiv alle Unterbäume von “c” auf. Die zwei Tests und die untergeordneten Knoten jedes Knotens werden durch vom Benutzer gegebene Prozeduren definiert.

Daher ist der tatsächliche Suchbaum, der vom Algorithmus durchlaufen wird, nur ein Teil des Potentialbaums. Die Gesamtkosten des Algorithmus sind die Anzahl der Knoten des tatsächlichen Baums, multipliziert mit den Kosten des Erhaltens und Verarbeitens jeden Knotens. Diese Tatsache sollte berücksichtigt werden, wenn der potenzielle Suchbaum ausgewählt und der Beschneidungstest implementiert ist.

Um das Backtracking auf eine bestimmte Klasse von Problemen anzuwenden, müssen die Daten “P” für die bestimmte Instanz des zu lösenden Problems und die sechs Prozedurparameter root, reject, accept, first, next und output, bereitgestellt werden. Diese Prozeduren sollten die Instanzdaten “P” als Parameter verwenden und Folgendes tun:

  • root (P):
    Den Teilkandidaten an der Wurzel des Suchbaums zurückgeben.
  • reject (P, c): Gibt nur dann “wahr/true” zurück, wenn der Teilkandidat “c” nicht vollständig ist.
  • accept (P, c): Gibt “wahr/true” zurück, wenn “c” eine Lösung von “P” ist, ansonsten “falsch/false”.
  • first (P, c): Erzeugt die erste Erweiterung des Kandidaten “c”.
  • next (P, s): Erzeugt die nächste alternative Erweiterung eines Kandidaten nach der Erweiterung “s”.
  • output (P, c): Verwendet je nach Anwendung die Lösung “c” von “P”..
Die Backtracking Prozedur sollte eine boolesche Funktion sein, die nur dann “wahr/true” 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 definitive Schlussfolgerung erzielen kann, sollte sie “falsch/false” zurückgeben. Ein falsches richtiges Ergebnis kann dazu führen, dass die bt-Prozedur einige gültige Lösungen verpasst. Die Prozedur kann annehmen, dass reject (P, t) für jeden Vorfahren “t” von “c” im Suchbaum den Wert “falsch/false” zurückgegeben hat.

Auf der anderen Seite hängt die Effizienz des Backtracking Algorithmus von der Zurückweisung ab, die für Kandidaten, die der Wurzel so nahe wie möglich sind, auf “wahr/true” zurückgeht. Wenn reject immer “falsch/false” zurückgibt, findet der Algorithmus immer noch alle Lösungen, aber es entspricht einer sogenannten Brute-Force-Suche.

Die accept-Prozedur sollte “wahr/true” zurückgeben, wenn “c” eine vollständige und gültige Lösung für die Probleminstanz “P” ist, andernfalls “falsch/true”. Es kann angenommen werden, dass der Teilkandidat “c” und alle seine Vorfahren in dem Baum den Abweisungstest bestanden haben.
Der obige allgemeine Psuedocode geht nicht davon aus, dass die gültigen Lösungen immer Blätter des potenziellen Suchbaums sind. Mit anderen Worten: Es gibt die Möglichkeit, dass eine gültige Lösung für “P” weiter ausgedehnt werden kann, um andere gültige Lösungen zu erhalten.

Die ersten und nächsten (first und next) Prozeduren werden vom Backtracking Algorithmus verwendet, um die untergeordneten Elemente eines Knotens “c” des Baums, aufzulisten. Das heißt, es sind die Kandidaten, die sich von “c” durch einen einzelnen Erweiterungsschritt unterscheiden. Der Aufruf “first” (P, c) sollte das erste Kind von “c” in einer bestimmten Reihenfolge ergeben. Der Aufruf “next” (P, s) sollte das nächste Geschwisterteil von Knoten “s” in dieser Reihenfolge zurückgeben. Beide Funktionen sollten einen eindeutigen “Null” -Kandidaten zurückgeben, der mit “^” bezeichnet wird, wenn das angeforderte Kind nicht existiert.

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

Der soeben beschriebene Pseudocode wird die Ausgabe für alle Kandidaten aufrufen, die eine Lösung für die gegebene Instanz “P” sind. Der Algorithmus kann modifiziert werden, um nach dem Finden der ersten Lösung oder einer spezifizierten Anzahl von Lösungen zu stoppen; oder nach dem Testen einer bestimmten Anzahl von Teilkandidaten oder nach dem Verbringen einer gegebenen Menge an CPU-Zeit.

Fazit

Das Backtracking stellt eine Problemlösungsmethode dar. Hierfür wird das Versuch-und-Irrtum-Prinzip verwendet. Es werden Möglichkeiten einer Lösung so lange versucht, bis die gesuchte Lösung erzielt wurde.


Sie haben noch Fragen?

Kontaktieren Sie uns

Kostenloser SEO-Check der OSG


Weitere Inhalte