Backtracking

Carl Friedrich Gauß (1777-1855)

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.

        Spezifikation des Schachbrettmoduls

	
	Schachbrettmodul :    [Linux]  	 [Windows]    [Solaris]

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. 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 sich 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.

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.

[TOP] [Protected]