Backtracking

Donnerstag, 09. April 2009 um 14:43 Uhr
Drucken
   Dameproblem    Springerproblem

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.

Dameproblem

Das Dameproblem stellt ein typisches Beispiel für trial and error Verfahren dar. Bereits im Jahre 1850 arbeitete C.F. Gauss an diesem Problem, welches bis heute nicht vollständig gelöst ist.

Das Problem besteht darin, 8 Damen auf einem Feld so zu verteilen, dass keine Dame die andere bedroht.

Queens


Zur Nutzung des Moduls schachbrett_ausgabe kann dieses heruntergeladen und entsprechend seiner Spezifikation verwendet werden. Das Dameproblem selber lässt sich wie folgt darstellen :

 	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


Um das Damenproblem zu implementieren sind weitere Methoden zu notwendig, die der Spezifikation entnommen werden können. Die Implementierung wird durch die Auslagerung der GUI Methoden überschaubar und kann nach dem saugen mit python ausgabe_versuch1.pyc getestet werden. Wichtig ist im Besonderen bei der Programmierung der Backtrackingmoduls die Methode nicht_bedroht , die garantiert, dass wirklich nur eine Dame je Spalte aufgestellt wird. Hier gibt es verschiedene Möglichkeiten der Implementierung.

Eine mögliche Steigerung des Problems besteht in der Möglichkeit einer Implementierung aller potenziellen Lösungen. Durch den hier vorgestellten Ansatz über eine graphische Oberfläche ist diese Erweiterung etws komplizierter und vor allem ineffizient. Hier würde eine Darstellung in einer funktionalen Sprache (Haskell, Miranda) anbieten.


Springerproblem

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.

Queens

        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.

Aktualisiert ( Freitag, 10. April 2009 um 08:55 Uhr )