Backtracking-Algorithmen

Backtracking-Algorithmen sind vom Prinzip erstaunlich simpel, und doch ziemlich mächtig. Sie verkörpern das Prinzip von Versuch und Irrtum. Von einem Startpunkt aus wird versucht, ein Problem zu lösen. Wenn dabei absehbar ist, dass der aktuelle Weg nicht funktionieren kann, wird dieser verworfen und ein anderer versucht. Das klassische Beispiel ist das Finden eines Wegs durch ein Labyrinth. Das folgende Java-Applet veranschaulicht einen solchen Vorgang.

Ziel ist, den kürzesten Weg aus dem Labyrinth zu finden. Vom Startpunkt aus werden dazu alle möglichen Wege durchprobiert, wobei in dieser Implementierung die Suchreihenfolge Nord, Ost, Süd, West ist. Wenn absehbar ist, dass ein Weg nicht funktioniert (z.B. weil man nur noch in Wände läuft, oder aber schon mehr Schritte verbraucht wurden, als der bisher kürzeste Weg umfasst), wird dieser verworfen und ein anderer gewählt. Aus der Sicht eines allwissenden Beobachters ist das Vorgehen des Programms ziemlich blöd. Systematisch, zielstrebig, aber blöd. Es ist natürlich möglich, nach dem einmaligen Finden des Ziels effizienter vorzugehen. Andererseits ist der Algorithmus in diesem Applet etwa 30 Zeilen lang; ein intelligenterer Algorithmus dürfte deutlich umfangreicher sein.

In meinem Artikel geht es neben Labyrinth-Spielchen auch um Probleme aus der Graphentheorie. Ein Programm beschäftigt sich mit dem Finden aller Lösungen des Haus-vom-Nikolaus. Ein anderes handelt von gewichteten Graphen, deren Kanten mit "Kosten" verknüpft sind. Als Beispiel dient die Suche nach dem schnellsten Weg durch ein Strassennetz.

Downloads

Zurück zur Hauptseite