Backtracking | MathePrisma

so war es vorher

Algorithmus 'Zum Ausgang'

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 Feld

Prinzip

Der 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.

Voraussetzungen:

Das Problem lässt sich durch eine Folge von Entscheidungen lösen.
Zu jedem Zeitpunkt stehen nur endlich viele Entscheidungen zur Wahl.
Manchmal - aber nicht immer - ist sofort erkennbar, dass eine mögliche Entscheidung falsch ist.

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:

Algorithmus Backtracking:

solange Lösung noch nicht gefunden

falls es jetzt eine noch nicht probierte, mögl. 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:

Entscheidung: Ein angrenzendes Feld, auf welches der Held bewegt wird. Je nachdem, wo sich der Held gerade befindet, gibt es bis zu vier mögliche Entscheidungen.
Entscheidungsfolge: Eine Folge begangener, benachbarter Felder - also ein Weg - im Labyrinth.
Erkennbar falsch ist eine Entscheidung, wenn sie auf ein bereits begangenes Feld führt.
Lösung gefunden: aktuelles Feld ist der Ausgang.