Zur MathePrisma-Startseite
Zur Modul-Startseite  


Das Vierfarbenproblem (Backtracking 2)
 

 
 
Neue Idee
 
Die Nachteile des sturen Hochzählens können wir umgehen, indem wir die Lösung schrittweise aufbauen.
 

 

Wir färben das erste Land grün und lassen die übrigen Länder zunächst ungefärbt.
Das entspricht dem Tachostand 0*****.
Jetzt versuchen wir, das zweite Land zu färben.
Der erste Tachostand, für den das geht, ist 01****.
 







Reihenfolge für Test der Farben
 
Im Vergleich zum vorigen Verfahren haben wir jetzt 256 Versuche überschlagen. Nun versuchen wir, die dritte Stelle im Tacho zu belegen, also das Land 3 zu färben und so weiter.

Wir arbeiten uns also schrittweise von links nach rechts vor, indem wir ein Land nach dem nächsten mit einer erlaubten Farbe belegen.

Für jedes neue Land, das wir färben wollen, probieren wir zuerst die Farbe grün (Ziffer 0), dann blau (Ziffer 1), dann rot (Ziffer 2) und zuletzt gelb (Ziffer 3).

 
Seite 6/18