Backtracking

Schrittweises Backtracking

Der Algorithmus, auf dem das Backtracking basiert, sorgt für ein systematisches Ausprobieren aller möglichen Lösungen, bis eine dieser gefunden wurde, oder festzustellen ist, dass eine solche für das spezifische Problem nicht existiert.

Dadruch, dass die Möglichkeiten in einzelnen Schritten durchlaufen werden, spricht man auch von schrittweisem Backtracking.²

Backtracking Algorithmus

Wie schon erwähnt, liegt die Methodik des Backtracking darin, alle Möglichkeiten rekursiv auszuprobieren und so an einem gewissen Punkt auf die richtige Lösung zu stoßen.

Um das einmal zu verdeutlichen, kannst Du ein bekanntes Anwendungsbeispiel für das Backtracking zur Hilfe nehmen: das N-Damen-Problem.

N-Damen-Problem

Kurz zusammengefasst geht es bei diesem schachmathematischen Problem darum, eine bestimmte Anzahl (n) von Damen auf ein Schachbrett mit einer gewissen Größe (n mal n) zu platzieren. Dabei dürfen keine Damen auf der gleichen senkrechten oder waagerechten Reihe sowie auf der gleichen Diagonale stehen.

In der Regel wird dieses Problem auf einem 8x8 Schachbrett mit 8 Damen veranschaulicht. Der Einfachheit halber lernst Du das Problem hier auf einem 4x4 Schachbrett mit 4 Damen kennen.

Die erste Dame kann konfliktfrei platziert werden. Da das Feld oben links die erste Möglichkeit der Platzierung darstellt, wird die erste Dame dort platziert.

Die zweite Dame kann nicht in der gleichen Spalte wie die erste platziert werden. Dadurch fallen die drei verbleibenden Felder der 1. Spalte durch den Algorithmus durch und werden nicht zum Teil der Lösung. Die Dame muss also mindestens in der 2. Spalte platziert werden.

In Feld 1 und 2 der zweiten Spalte kann die Dame auch nicht platziert werden, da sonst wieder 2 Damen in einer Reihe bzw. Diagonale stehen würden, was durch die Regeln verboten wird. Auch diese beiden Felder fallen also durch den Algorithmus und sind nicht Teil der Lösung.

Im 3. Feld der 2. Spalte kann die Dame erstmals stehen, ohne eine Regel zu verletzen. Dementsprechend wird sie dort platziert.

Bei der dritten Dame wird ebenso vorgegangen: In Spalte 2 kann sie aufgrund der Regeln nicht stehen. Im 1. Feld der 3. Spalte würde sie mit der ersten Dame in Konflikt geraten. Auf den anderen Feldern der 3. Spalte würde sie mit der 2. Dame kollidieren. Daher muss zur 2. Dame zurückgekehrt und ihre Position geändert werden. Sie kann nur noch um 1 Feld nach unten verschoben werden, also wird genau das getan. Danach kann die dritte Dame auf dem 2. Feld der 3. Spalte ohne Konflikte platziert werden.

Nur noch eine Dame übrig. Kann ja nicht so schwer sein, oder? Tatsächlich gibt es aktuell auf den verbleibenden Feldern keine Möglichkeit, die vierte Dame konfliktfrei zu platzieren. Das ist der Punkt, an dem das Backtracking über mehrere Schritte hinweg durchgeführt werden muss.

Da die 4. Dame keine sichere Platzierung erhalten kann, muss eine oder mehrere der bisherigen Lösungskomponenten falsch sein. Um herauszufinden, welche korrekt sind, wird schrittweise zu den vorhergehenden Schritten zurückgekehrt und die verbleibenden Möglichkeiten ausprobiert.

Die dritte Dame kann weder im 3. noch im 4. Feld stehen. Also wird sie vorerst entfernt und später erneut auf mögliche Positionen getestet. Da es für die 2. Dame auch keine weitere sichere Platzierung gibt, wird auch sie vom Brett genommen.

Nun steht nur noch die erste Dame auf dem Brett, da bis zu diesem Punkt zurückgegangen wurde. Diese wird jetzt um eine Position nach unten verschoben.

Die zweite Dame wird wieder platziert. Auf den ersten 3 Feldern der zweiten Spalte findet sie keinen sicheren Platz, auf dem vierten Feld steht sie jedoch sicher, also kann die dritte Dame platziert werden. Schon auf dem 1. Feld kann sie konfliktfrei positioniert werden.

Fehlt nur noch die vierte Dame: Auf den ersten beiden Feldern der vierten Spalte steht sie in Konflikt mit anderen Damen. Auf dem dritten Feld steht sie – wie alle anderen Damen auch – in einer konfliktfreien Position. Damit ist das Problem gelöst.

Backtracking Beispiel

Neben dem N-Damen-Problem existieren einige andere gängige Beispiele, welche mithilfe von Backtracking gelöst werden können.

Diese Beispiele für das Backtracking können auch Probleme genannt werden, konkret mithilfe von Backtracking lösbare Probleme.

Backtracking im Labyrinth

Ein sehr bekanntes Beispiel steht am Anfang dieser Erklärung – das Labyrinth. Natürlich kann man planlos durch ein solches laufen und darauf hoffen, das Ziel zu finden. Mithilfe des Backtracking und einer gewissen strukturierten Herangehensweise geht dies allerdings einfacher und vielleicht sogar schneller.

Bevor Du das Labyrinth betrittst, überlegst Du Dir, in welche Richtung Du an jeder Kreuzung zuerst gehen willst, beispielsweise links. Sollte diese Richtung in eine Sackgasse führen, gehst Du zur vorherigen Kreuzung zurück. Dann nimmst Du den Weg, der am weitesten links liegt, jedoch nicht den, den Du schon genommen hast. Das führst Du fort, bis Du die nächste Kreuzung erreichst. Sollten alle Abzweige einer Kreuzung in eine Sackgasse führen, musst Du zur Kreuzung davor zurück, und die restlichen Abzweige ausprobieren.

Backtracking in anderen Problemen

Ein weiteres Problem aus der Schachwelt kann ebenfalls durch Backtracking gelöst werden. Beim Springerproblem liegt das Ziel darin, ohne das Spielbrett zu verlassen, mit gültigen Zügen jedes Feld des Brettes genau einmal zu besuchen.

Auch durch Backtracking lösbar ist das Färbeproblem. Ziel ist es, eine bestimmte Anzahl von Ländern auf einer Landkarte in einer bestimmten Anzahl unterschiedlicher Farben zu färben. Dabei dürfen Länder mit einer gemeinsamen Grenze nicht in der gleichen Farbe angemalt werden.

Backtracking und Rekursion

Die zwei gängigsten Problemlösungsverfahren der Algorithmik sind Backtracking und Rekursion. Tatsächlich ist es so, dass die Rekursion eine Implementierung von Backtracking nutzen kann, um zur Lösung von Problemen zu kommen. Damit Du einen kurzen Überblick erhältst, folgt nun eine schnelle Einführung in die Rekursion.

Um einen Algorithmus zu implementieren, der Backtracking anwendet, kann der Code einen rekursiven Selbstaufruf einer Funktion beinhalten. Dies ist die gängigste Form der Implementierung eines Backtracking-Algorithmus. Die Abbruchbedingung dieser ist dann erreicht, wenn keine ungetesteten möglichen Lösungen mehr zur Verfügung stehen. Dann gibt es keine Lösung für das Problem.

Durch die Zerlegung des Problems, welche durch die Rekursion automatisch gegeben ist, wird das Backtracking recht effizient auf den zu lösenden Sachverhalt angewandt.