MathePrisma Logo

Das Vierfarbenproblem

Das Vierfarbenproblem

Maus

Eine Anwendung des Backtracking-Algorithmus für ein Labyrinthproblem.

                                          

Eine Maus soll in dem Labyrinth links starten und einen Weg durch diesen Irrgarten finden.

Die drei Merkmale des Backtracking-Algorithmus:
  1. Die Lösung kann schrittweise durch eine Folge von Entscheidungen aufgebaut werden.
      
    • Jeder Schritt bringt die Maus ein Kästchen weiter.
  2. Bei jeder Entscheidung gibt es nur endlich viele Möglichkeiten.
      
    • Die Maus hat nur die Möglichkeiten, nach Süden, Westen, Norden oder Osten zu gehen. Sie testet die Möglichkeiten in der Reihenfolge W-N-O-S.
  3. Es ist nicht von vorneherein klar, welche Entscheidung jeweils richtig ist. Es gibt aber Situationen, in denen klar wird, dass die zuletzt getroffene Entscheidung falsch war.
      
    • Die notwendigen Bedingungen dafür, dass ein Schritt erlaubt ist, sind:
          1.   In der Richtung darf keine Mauer sein.
      2. Die Maus darf das Feld noch nicht betreten haben.
      3. Das Feld darf nicht außerhalb des Labyrinths liegen.
Ein Backtracking-Algorithmus (Reihenfolge der Möglichkeiten: W-N-O-S) würde z.B. diesen Weg durch das Labyrinth finden:

                                          


Dabei deuten die gestrichelten Linien die Wege an, die die Maus innerhalb des Backtracking-Algorithmus versucht, die sich aber als Sackgassen herausstellen.