Backtracking
Nur Leistungskurs. Diese Lektion gehört zu den zusätzlichen Anforderungen des Leistungskurses. Im Grundkurs kannst du sie überspringen.
Die Idee
Manche Probleme lassen sich nicht ausrechnen, sondern nur ausprobieren. Ein Labyrinth zum Beispiel: Man weiß an einer Kreuzung nicht, welcher Weg zum Ziel führt. Also probiert man einen – und wenn er in eine Sackgasse führt, geht man zurück und nimmt den nächsten.
Backtracking ist eine systematische Suche durch alle Möglichkeiten:
- Triff eine Entscheidung und merke sie dir.
- Versuche rekursiv, von dort aus weiterzukommen.
- Führt das zum Ziel: fertig.
- Führt es nicht zum Ziel: nimm die Entscheidung zurück und probiere die nächste Möglichkeit.
Sind alle Möglichkeiten erschöpft, gibt es von hier aus keine Lösung.
Der entscheidende Schritt ist Nummer 4 – das Zurücknehmen. Er gibt der Strategie ihren Namen.
Das Labyrinth
Das Labyrinth aus dem Kapitel über zweidimensionale Felder – jetzt suchen wir einen Weg hindurch.
a) Blaue Zellen gehören zum gefundenen Weg, rosa Zellen wurden ausprobiert und wieder verworfen. Finde beide im Bild.
b) Zeige im Quelltext, wo die Entscheidung getroffen und wo sie zurückgenommen wird.
c) Warum ist es wichtig, dass die vier rekursiven Aufrufe mit || verknüpft sind und nicht einzeln aufgerufen werden?
Auflösung
a) Der Weg vom Start unten links durch das Labyrinth ist blau. Die Abzweigungen, die in Sackgassen führten, sind rosa.
b) Die Entscheidung ist plan[pZeile][pSpalte] = '+'; vor den rekursiven Aufrufen. Die Rücknahme ist plan[pZeile][pSpalte] = 'x'; danach – sie wird nur erreicht, wenn keiner der vier Wege zum Ziel führte.
c) Wegen der Kurzschlussauswertung: Sobald einer der Aufrufe true liefert, werden die übrigen gar nicht mehr ausgeführt. Der erste gefundene Weg beendet die Suche.
Würde man sie einzeln aufrufen, liefe die Suche weiter, obwohl das Ziel längst erreicht ist – und würde den gefundenen Weg womöglich wieder überschreiben.
Das Markieren mit '+' erfüllt zwei Aufgaben gleichzeitig:
- Es merkt sich den Weg.
- Es verhindert, dass die Suche im Kreis läuft – eine bereits betretene Zelle ist kein
'.'mehr und wird beim nächsten Besuch abgewiesen.
Ohne diese Markierung liefe die Rekursion sofort endlos: von A nach B, von B zurück nach A, von A nach B …
Das Muster
Jedes Backtracking-Verfahren hat dieselbe Form:
boolean loese(Zustand):
wenn Zustand ist eine Lösung:
gib true zurück
wenn Zustand ist ungültig:
gib false zurück
für jede mögliche Entscheidung:
treffe die Entscheidung
wenn loese(neuer Zustand):
gib true zurück
nimm die Entscheidung zurück
gib false zurückDu musst also nur drei Dinge festlegen:
- Wann ist ein Zustand eine Lösung?
- Wann ist er ungültig?
- Welche Entscheidungen gibt es von hier aus?
Aufgabe 1: Das Acht-Damen-Problem
Auf einem Schachbrett sollen acht Damen so stehen, dass keine eine andere bedroht. Eine Dame bedroht alles in ihrer Zeile, Spalte und auf beiden Diagonalen.
a) Überlege zuerst: Warum kann in jeder Spalte genau eine Dame stehen? Was vereinfacht das?
b) Beantworte die drei Fragen des Musters: Was ist eine Lösung, was ist ungültig, welche Entscheidungen gibt es?
c) Setze es um, sodass die Tests grün werden.
Tipp 1: Warum eine Dame pro Spalte?
Weil zwei Damen in derselben Spalte einander sofort bedrohen. Bei n Damen auf einem n-mal-n-Brett muss also in jeder Spalte genau eine stehen.
Das vereinfacht die Suche enorm: Statt jedes Feld einzeln zu betrachten, geht man Spalte für Spalte vor und probiert dort nur die n möglichen Zeilen.
Tipp 2: istSicher
Prüfe alle bereits besetzten Spalten links von pSpalte:
for (int s = 0; s < pSpalte; s++) {
int z = stellung[s];
if (z == pZeile) {
return false; // gleiche Zeile
}
if (Math.abs(z - pZeile) == pSpalte - s) {
return false; // gleiche Diagonale
}
}
return true;Der Diagonaltest ist der Kern: Zwei Felder liegen genau dann auf einer Diagonalen, wenn ihr Zeilenabstand so groß ist wie ihr Spaltenabstand.
Tipp 3: loese
if (pSpalte == groesse) {
return true; // alle Damen gesetzt
}
for (int zeile = 0; zeile < groesse; zeile++) {
if (istSicher(zeile, pSpalte)) {
stellung[pSpalte] = zeile; // Entscheidung
if (loese(pSpalte + 1)) {
return true;
}
stellung[pSpalte] = -1; // Rücknahme
}
}
return false;Aufgabe 2: Wie viel wird ausprobiert?
Wie viele Stellungen müsste man durchprobieren, wenn man stur alle Möglichkeiten testete?
a) Bei acht Damen mit einer pro Spalte gibt es 8⁸ mögliche Stellungen. Wie viele sind das?
b) Backtracking probiert weit weniger, weil es Zweige früh abschneidet. Zähle mit, wie oft istSicher tatsächlich aufgerufen wird.
c) Beurteile: Ist Backtracking damit ein schnelles Verfahren?
Auflösung
a) 8⁸ = 16 777 216 Stellungen.
b) Backtracking kommt mit einigen hundert Prüfungen aus – etwa ein Zehntausendstel davon.
c) Nein, schnell ist es nicht. Im schlechtesten Fall probiert Backtracking tatsächlich alles durch, und der Aufwand ist exponentiell. Bei 20 Damen dauert es schon spürbar, bei 30 nicht mehr praktikabel.
Der Gewinn liegt woanders: Backtracking probiert nur die Zweige, die überhaupt noch Aussicht auf Erfolg haben. Es macht ein prinzipiell riesiges Problem für kleine Eingaben lösbar – aber es ändert nichts an der Wachstumsklasse.
Für Probleme, bei denen man wirklich alle Möglichkeiten prüfen muss, gibt es kein schnelles Verfahren. Das ist keine Frage besserer Programmierung, sondern eine Eigenschaft des Problems.
Zusatzaufgabe
Sudoku. Ein 9-mal-9-Feld ist teilweise gefüllt; leere Felder bekommen Ziffern von 1 bis 9, sodass in jeder Zeile, jeder Spalte und jedem 3-mal-3-Block jede Ziffer genau einmal vorkommt.
a) Beantworte die drei Fragen des Musters.
b) Setze es um. Die Methode istErlaubt(zeile, spalte, ziffer) ist der aufwendigste Teil – überlege dir gut, wie du den 3-mal-3-Block bestimmst.
c) Miss, wie lange dein Programm für ein leichtes und für ein schweres Sudoku braucht. Erkläre den Unterschied.
d) Zeige das Ergebnis mit Scratch for Java auf der Bühne an.