Frage 2
Wie formuliert man Backtracking-Algorithmen ohne Sprunganweisungen wie "gehe zu 1."?
Sprünge vermeiden
Bei unserem ersten Entwurf haben wir mit Anweisungen wie "gehe zu 1." gearbeitet. In einem Computerprogramm sind solche Sprunganweisungen (GOTO = gehe zu) fehlerträchtig und führen zu schlechter Lesbarkeit des Programmcodes.
Daher:
| "Unser Motto: ohne GOT(T)O" |
Eine sicherere und elegantere Methode ist es, mit Rekursionen zu arbeiten. Wir erlauben also, dass ein Algorithmus sich selbst wieder aufruft.
Die folgende Prozedur fortsetzen hat exakt den gleichen Anweisungsablauf wie unser erster Entwurf. Sie vermeidet aber Sprunganweisungen und arbeitet stattdessen rekursiv.
Prozedur fortsetzen für das Vierfarbenproblem
Prozedur fortsetzen(F)
|
Das Gesamtverfahren stellt sich dann wie folgt dar:
Prozedur Lösung mit Backtracking
|
Nummeriere die Länder mit einer geeigneten Strategie. fortsetzen()
|
Prozedur fortsetzen im allgemeinen Fall
Für den allgemeinen Fall brauchen wir die Prozedur fortsetzen nur noch geringfügig zu modifizieren:
Prozedur fortsetzen(F)
|
Dieses Gerüst benutzt man in einer Vorlesung für Studenten im zweiten Semester, um verschiedene Probleme zu lösen.
Zum Beispiel kann man diesen Algorithmus anwenden, um eine Maus durch ein Labyrinth zu führen.
