Unser Held - ein roter Punkt - muss aus dem Labyrinth entkommen. Der Held ist nicht schlau, aber ausdauernd. An jeder Kreuzung entscheidet er einfach per Zufall, wie er weitergeht.
Ob das zum Ziel ( = Ausgang ) führt? Überlasse den Zufall-Helden seinem Schicksal. Du kannst ja nochmals nach ihm sehen, wenn du diese Seite durchgearbeitet hast.
Hier kannst du per Pfeiltasten den Helden immer bis zur nächsten Kurve oder Kreuzung fortbewegen. Sicher bist du schneller am Ausgang als der Zufall-Held.
Du hattest entscheidende Informationen: du kanntest den Plan des Labyrinths und wusstest zu jedem Zeitpunkt, wo auf dem Plan du dich befindest. Das ist doch eher untypisch.
Führe den Helden wieder mit den Pfeiltasten aus dem Labyrinth. Deine Sicht ist diesmal auf Fackel-Leuchtweite eingeschränkt.
solange nicht am Ausgang falls es ein angrenzendes, nicht markiertes Feld gibt bewege den Helden auf dieses Feld und markiere es sonst bewege den Helden auf ein angrenzendes, markiertes FeldWenn man nur noch markierte Felder um sich hat, ist man auf dem Holzweg. Man will umkehren. Das ist im obigen Algorithmus allerdings so noch nicht präzisiert. Man möchte also bis zur nächsten Kreuzung zurückgehen. Wenn dort auch schon alle Felder markiert sind, möchte man noch weiter zurück usw. Um 'zurück' zu gehen, muss man immer wissen, wo man her kam.
Hier kannst du den Helden beobachten, wie er mit Kreide und Faden ganz systematisch aus dem Labyrinth findet. Der Ariadne-Faden ist durch die schwarzen Punkte dargestellt.
Im obigen Experiment arbeitet der Held die Möglichkeiten immer nach denselben Präferenzen ab. Ziehe jede Richtung auf die passende Reihenfolge.
solange nicht am Ausgang falls es ein angrenzendes, nicht markiertes Feld gibt bewege den Helden auf dieses Feld und markiere es sonst bewege den Helden zurück auf das zuletzt begangene FeldDieser Algorithmus ist ein erstes Beispiel für die Backtracking-Strategie. Im nächsten Abschnitt werden wir dieses Prinzip allgemein beschreiben. Beantworte zuvor noch folgende Frage.
Wie oft wird jetzt jedes Feld maximal begangen?
Der bisherige Algorithmus verfährt nach dem Prinzip wenn möglich vorwärts, sonst rückwärts. Dieses Prinzip lässt sich auch bei vielen anderen Problemen anwenden.
Nicht jede falsche Entscheidung ist sofort als eine solche erkennbar. Es ist z.B. falsch, in eine Sackgasse einzubiegen. Das erkennt man aber erst später, nämlich wenn man merkt, dass es nicht weiter geht. Man kann nun folgendermaßen eine zur Lösung führende Entscheidungsfolge aufbauen:
solange Lösung noch nicht gefunden
falls es jetzt eine noch nicht probierte, \
mögliche Entscheidung gibt
falls diese nicht erkennbar falsch ist
verlängere die Entscheidungsfolge um \
diese Entscheidung
{'treffe die Entscheidung'}
sonst
entferne die letzte Entscheidung aus der \
Entscheidungsfolge
{'nimm die zuletzt getroffene Entscheidung zurück'}
Beim Labyrinth ist die Zuordnung so:
Gib in den folgenden Situationen an, wieviele Entscheidungen prinzipiell möglich und wieviele davon erkennbar falsch sind.
Das Backtracking-Prinzip lässt sich elegant als rekursiver Algorithmus formulieren und dann auch so implementieren.
Ein rekursiver Algorithmus ist ein Algorithmus, der sich selbst wieder aufruft.
EF bezeichnet eine Entscheidungsfolge.
falls EF Lösung ist stop sonst für alle jetzt möglichen Entscheidungen falls Entscheidung nicht erkennbar falsch verlängere Entscheidungsfolge EF \ um diese Entscheidung, (die verlängerte \ Entscheidungsfolge heiße EF') BacktrackingRek(EF')Der Algorithmus wird mit der leeren Entscheidungsfolge gestartet.
Bei Verwendung von Rekursion muss man sich keine Gedanken mehr darüber machen, wie man eine Entscheidung zurücknimmt: der Rechner organisiert dies von sich aus beim Verwalten der rekursiven Aufrufe.
Der Rechner verwaltet eine Datenstruktur Stack ('Stapel').
falls EF = Lösungsonstbestimme die Menge M der möglichen Richtungenfür alleRichtungen X aus Mfalls Feld in Richtung X nicht besuchtStelle 8 Damen so auf ein Schachbrett, dass keine Dame eine andere bedroht. Eine Dame kann horizontal, vertikal und diagonal schlagen.
Du kannst das Schachbrett auch verkleinern. Bei Größe n musst du n Damen auf einem n*n Schachbrett unterbringen. Ein Klick auf eine Dame entfernt sie wieder.