Backtrackingverfahren dienen der Lösung von Problemfeldern. Dabei geht es
nicht um die sequentielle Lösung eines Problems, sondern um die Lösung
durch Versuchen und Irren ( trial and error ) einer Gruppe von Problemen.
Sollte sich der beschrittene Weg als falsch herausstellen, geht man bis
an die Stelle zurück, von welcher sich ein alternativer Weg bietet. Als
bekanntes Beispiel sei der Back - Pfeil im Browser genannt. Diese
Probleme spielen in der Graphentheorie eine entscheidende Rolle und werden
dort bei entsprechenden Suchverfahren verwendet.Die folgenden Beispiele
sollen das Verfahren erläutern.
|
springe (i) #initialisiere Wert für i-te Dame gehe durch Zeile 1 bis 9 if sicher setze die Dame if Spalte 8 erreicht : return else : springe (i+1) entferne die Dame
Ein weiteres Problem, dessen Lösung Backtrackingalgorithmen benötigt ist das Springerproblem. gegenüber dem oben dargestellten
Dameproblem ist es insofern interessanter, als das für die Lösung weitaus mehr Ressourcen benötigt werden. Die im
folgenden dargestellte Lösung beschränkt sich aus diesen Gründen auf ein 6x6 schachbrett. Eine Erweiterung ist auch hier
leicht möglich.
|
Als Schachrettmodul kann das beim Dameproblem zur Vefügung gestellte Modul genutzt werden. Der nebenstehende Screenshot stellt eine Momentaufnahme des laufenden Algorithmus dar. |
Das Problem besteht hier darin einen Springer nach den Schachregeln so über ein n x n Feld zu führen, dass er genau einmal jedes
der n² Felder besucht, wenn ein solcher Weg möglich ist.
springe (x,y) # initialisiere Startposition wenn nicht besetzt besetzen (x,y) if zaehler = n x n : return else : prüfe die potenziellen Sprungfelder (xneu, yneu) if definiert : springen (xneu, yneu) freigeben (x,y)
Auch hier sei die Spezifikation des Ausgabemoduls vorgegegeben und ein testbare Version der Implementierung
zur Verfügung gestellt.
[TOP]
[Protected]