Zur MathePrisma-Startseite
Zur Modul-Startseite  


Das Vierfarbenproblem (Backtracking+ 3)
 

 
 
Frage 2








Sprünge vermeiden
 
Wie formuliert man Backtracking-Algorithmen ohne Sprunganweisungen wie "gehe zu 1."?


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)
      {Kommentar: F=(E1,...,Ei-1) ist die bisher erzeugte Folge von Entscheidungen. Ej: "Färbe Land Lj mit Farbe f".}
wenn F Lösung ist
dann stop
sonst  
für alle Möglichkeiten, F fortzusetzen {d.h. probiere nacheinander die Farben grün, blau, rot und gelb aus.}
    Ei= "Färbe Land Li mit Farbe f".
wenn  
Ei nicht als falsche Entscheidung erkennbar ist {d.h. Bedingungen 1 und 2 sind erfüllt.}
dann  
fortsetzen(F, Ei )
 

 
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)
      {Kommentar: F=(E1,...,Ei-1) ist die bisher erzeugte Folge von Entscheidungen.}
wenn F Lösung ist
dann stop
sonst  
für alle Möglichkeiten, F fortzusetzen
    {Sei Ei die aktuell betrachtete Entscheidung}
wenn  
Ei nicht als falsche Entscheidung erkennbar ist
dann  
fortsetzen(F, Ei )
 

 
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.
 
Seite 13/18