Backtracking
"nach vorn wenn möglich, zurück wenn nötig"
Autor(en): Andreas Frommer - Oktober 2019
Kapitelübersicht
Du musst versuchen, aus einem Labyrinth zu entkommen. Dabei wirst du das Prinzip des Backtracking verwenden.
Hier wird das Backtracking als allgemeines Prinzip formuliert. Ein rekursiver Algorithmus wird angegeben.
Backtracking wird zur Lösung des n-Damen-Problems angewendet.
Auch beim Quinto-Spiel kann man Backtracking einsetzen. Das wird in diesem Kapitel klar gemacht.
Arbeitsblatt
Aufgabe 1
Das n-Damen-Problem besitzt in der Regel mehrere Lösungen.
Wir nennen zwei Lösungen wesentlich verschieden, wenn sie nicht durch Rotation oder Spiegelung auseinander hervorgehen.
a) Gib alle Lösungen des 4-Damen-Problems an. Gibt es wesentlich verschiedene Lösungen?
b) Gib zwei wesentlich verschiedene Lösungen des 5-Damen-Problems an.
c) Wie muss man den Backtracking-Algorithmus für das n-Damen-Problem modifizieren,
damit er alle Lösungen bestimmt? Schreibe dazu den modifizierten
Algorithmus (rekursiv oder nicht-rekursiv) im Detail auf.
Aufgabe 2
Mit welchem Wert für i muss man den rekursiven
Algorithmus N-DamenRek(i) starten?
Aufgabe 3
Formuliere einen rekursiven und einen nicht-rekursiven
Backtracking-Algorithmus für das Spiel Quinto.
Aufgabe 4
Wir haben uns bei den hier behandelten Aufgaben nie
überlegt, ob es überhaupt eine Lösung gibt.
a) Hat das n-Damen-Problem für n=3 eine Lösung?
(Begründung!)
b) Hat Quinto für die Größe 3 eine Lösung?
c) Wie muss man die Backtracking-Algorithmen (nicht-rekursiv
und rekursiv) abändern, dass sie die Information 'es gibt keine
Lösung' ausgeben?
Aufgabe 5
Bearbeite das MathePrisma-Modul 'Vierfarbenproblem'.
Beschreibe in eigenen Worten die Aufgabenstellung und eine nicht-rekursive
sowie eine rekursive Variante eines Backtracking-Algorithmus, welcher
für eine gegebene Karte eine gesuchte Einfärbung findet.
Drucken
Inhalt
Das Verfahren des Backtrackings wird anhand der Sage von Theseus, der mit Hilfe des Ariadne-Fadens aus dem Labyrinth entkommt, motiviert und allgemein hergeleitet.
Anschließend wird Backtracking auf das n-Damen-Problem und das Spiel Quinto angewendet.
Glossar
