Backtracking

Backtracking

Copyright © Shutterstock / OpturaDesign

Was ist Backtracking?

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