Backtracking

[Back]    [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.

[TOP]

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.


[TOP]                [Protected]