Suche im Labyrinth
Anwendungen:
+ Routenplaner (Wanderwege, Radwege, Straßen, Bahn, Flugverbindungen,...)
+ Kommunikation im Internet (Finden des Servers)
+ Kommunikation in Handy-Netzen
Vereinfachung:
Von jedem Feld gibt es genau vier mögliche Richtungen (oben-unten-rechts-links bzw. Nord-Ost-Süd-West).
Lösung:
1 Die Nachbarfelder werden in einer konstanten Reihenfolge überprüft, ob sie betreten werden können. Diese Reihenfolge kann zum Beispiel Süd-Nord-Ost-West (SNOW) sein.
(Ein Feld kann betreten werden, wenn es nicht zu einer Mauer gehört und noch nicht als bereits besucht markiert ist.)
2 Wenn ein Feld betreten werden kann, wird es sofort betreten und als schon besucht markiert.
3 Von hier aus wiederholen sich die Schritte 1 und 2. (Rekursion)
4 Wenn man in eine Sackgasse gerät, werden so viele Schritte rückgängig gemacht, bis sich eine neue Wegmöglichkeit ergibt.
5 Das Verfahren endet, wenn alle Wege vom Start zum Ziel gefunden wurden oder wenn klar ist, dass es keinen Weg zum Ziel gibt.
Backtracking-Verfahren (Trial-and-Error-Verfahren):
Bezeichnung für ein Lösungsverfahren, bei dem man versucht,eine Teillösung eines Problems systematisch zu einer Gesamtlösung auszubauen. Falls in einem gewissen Stadium ein weiterer Ausbau einer vorliegenden Lösung nicht mehr möglich ist (Sackgasse), werden einer oder mehrere der letzten Teilschritte rückgängig gemacht. Die dann erhaltene reduzierte Teillösung versucht man auf einem anderen Weg wieder auszubauen. Das Zurücknehmen von Schritten und erneute Vorangehen wird solange wiederholt, bis eine Lösung des vorliegenden Problems gefunden ist oder bis man erkennt, daß das Problem keine Lösung besitzt. Die Möglichkeit in Sackgassen zu laufen und aus ihnen wieder herauszufinden, zeichnet das Backtracking-Verfahren aus.
Das Backtracking kann auf zwei Weisen terminieren:
1 wenn die Datenbasis vollständig durchsucht wurde und definitiv keine Lösung gefunden wurde,
2 wenn eine Lösung gefunden worden ist,
3 wenn alle Lösungen gefunden worden sind.