MathePrisma Logo

Das Vierfarbenproblem

Das Vierfarbenproblem

Backtracking+

Frage 1

Welche Probleme können mit einem Backtracking-Algorithmus gelöst werden?

Problemklassen für Backtracking

Es gibt drei wesentliche Merkmale für die Anwendbarkeit eines Backtracking-Algorithmus:

  1. Die Lösung kann schrittweise durch eine Folge von Entscheidungen aufgebaut werden.
  2. Bei jeder Entscheidung gibt es nur endlich viele Möglichkeiten.
  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.

Illustration am Beispiel des Vierfarbenproblems

Zu Merkmal 1. "Die Lösung kann schrittweise durch eine Folge von Entscheidungen aufgebaut werden."
Beim Vierfarbenproblem geben wir dafür eine Reihenfolge für die Länder vor. Dann lautet eine Entscheidung \(E_{j}\) so:

      \(E_{j}\): "Färbe Land \(L_{j}\) mit Farbe f."

Wir fassen diese Einzelentscheidungen zu einer Folge F zusammen. Wenn wir bereits i Länder gefärbt haben, können wir dies wie folgt formulieren:

      \( F=(E_{1},E_{2},...,E_{i}) \)



Beispiel:
                                          

\(E_{1}\): "Färbe Land \(L_{1}\) mit Farbe grün."
\(E_{2}\): "Färbe Land \(L_{2} \) mit Farbe blau."
\(E_{3}\): "Färbe Land \(L_{3} \) mit Farbe blau."
\( F=(E_{1},E_{2},E_{3}) \)


Ist n die Anzahl der Länder einer Karte und besteht die Folge F aus n Entscheidungen, so haben wir eine Lösung gefunden.

Zu Merkmal 2. "Bei jeder Entscheidung gibt es nur endlich viele Möglichkeiten."
Bei der Entscheidung

      \(E_{j}\): "Färbe Land \(L_{j}\) mit Farbe f."

gibt es für f nur die vier Möglichkeiten

      grün, blau, rot, gelb.


Zu Merkmal 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 Bedingungen 1 und 2 sind notwendige Bedingungen für eine korrekte Einfärbung der Karte. Sind sie nicht erfüllt, dann ist die Kolorierung in jedem Fall ungültig. Die zuletzt getroffene Entscheidung muss zurückgenommen werden.

0 = grün
1 = blau
2 = rot
3 = gelb

Beispiel:

                                          

Land 6 ist unfärbbar.

Nach diesen Betrachtungen können wir unsere frühere algorithmische Formulierung für das Backtracking beim Vierfarbenproblem auf den allgemeinen Fall übertragen.

Algorithmus

i=1

1. Solange noch keine Lösung gefunden, d.h. i <= n

        2. {Kommentar: \(F=(E_{1},...,E_{i-1})\) ist die bisher
          erzeugte Folge von Entscheidungen.}
          betrachte Position i der Entscheidungsfolge.
        3. Wenn noch nicht alle Möglichkeiten durchprobiert
            dann
                    wähle die nächste mögliche Entscheidung \(E_{i}\).
                    Wenn \(E_{i}\) nicht als falsch erkennbar ist
                    dann
                                 i=i+1
                                 gehe zu 1.
                    sonst
                                 gehe zu 3.

            sonst
                    nimm Entscheidung \(E_{i}\) zurück
                    i=i-1
                    gehe zu 2.