Zur MathePrisma-Startseite
Zur Modul-Startseite  


Das Vierfarbenproblem (Backtracking 4)
 

 
 

 
Wir geben jetzt ein Verfahren an, das den schrittweisen Aufbau der Lösung steuert, die  Bedingungen 1 und 2 überprüft und schließlich zu einer korrekten Einfärbung der Karte führt:

Wir nummerieren die Länder durch und bezeichnen sie mit \(L_{1},...,L_{n}\).
Erinnerung:
Die Farben probieren wir in der Reihenfolge grün, blau, rot, gelb durch.

 
Algorithmus
 
i=1

1. Solange i<=n

        2. betrachte Land \(L_{i}\)
        3. Wenn noch nicht alle Farben durchprobiert
            dann
                    färbe das Land \(L_{i}\) mit der nächsten Farbe.
                    Wenn Bedingungen 1 und 2 erfüllt sind
                    dann
                                 i=i+1
                                 gehe zu 1.
                    sonst
                                 gehe zu 3.

            sonst
                    entfärbe Land \(L_{i}\)
                    i=i-1
                    gehe zu 2.
 

 
Wir wenden dieses Verfahren jetzt auf die Karte mit n=6 Ländern von vorhin an. Im Protokollfeld unten werden die wichtigsten Statusmeldungen und Aktionen aufgelistet.
 






grün
blau
rot
gelb

 
 

 
Das Verfahren findet die Lösung bei Tachostand 012123. Beim erschöpfenden Durchsuchen hätte man dafür 411 Versuche gebraucht.
Hier dagegen haben wir nur 16 Mal die "weiter"-Taste drücken müssen. Dabei wurden 27 verschiedene Tachostände betrachtet.

Das folgende Beispiel mit n=9 Ländern demonstriert an vielen Stellen, dass die Entscheidung, ein Land mit einer bestimmten Farbe zu belegen, zwar die Bedingungen 1 und 2 erfüllt, aber dennoch in eine Sackgasse führt.
 






grün
blau
rot
gelb

 
 

 
Trotzdem sehen wir, wie der Algorithmus aus den Sackgassen herausfindet, indem er seine Spur zurückverfolgt. Daher auch der Name Backtracking = Rückverfolgung.

Die Lösung wird beim Tachostand 012312312 gefunden. Beim erschöpfenden Durchsuchen wären also 28086 Versuche notwendig gewesen.

( \(28086 = 1*4^{7} + 2*4^{6} + 3*4^{5} + 1*4^{4} + 2*4^{3} + 3*4^{2} + 1*4^{1} +2*4^{0}\))
 
Seite 8/18