Zur MathePrisma-Startseite
Zur Modul-Startseite  


Das Vierfarbenproblem (Backtracking 1)
 

 
 

 
Beim erschöpfenden Durchsuchen sind wir bisher immer so vorgegangen:
 
erst färben, dann prüfen
 
"Färbe die ganze Karte erst vollständig ein und prüfe anschließend, ob die Kolorierung gültig oder ungültig ist."
 

 
Die Reihenfolge, in der wir versuchen, die Karte einzufärben, ist durch den Tachometer festgelegt. Betrachten wir noch einmal die vorherige Karte.
 
nochmal die Karte mit sechs Ländern
 


Nach Drücken des Reset-Knopfes wird der Tachostand auf 000000 gesetzt und dann (mit "weiter") stur hochgezählt.
 

 
Wir können Folgendes beobachten:
  • Alle Tachostände, die mit 00 beginnen, führen auf eine ungültige Einfärbung, weil Land 1 und Land 2 benachbart sind.
  • Das Verfahren probiert also alle Tachostände der Form 00**** durch, obwohl klar ist, dass keiner dieser Tachostände eine Lösung sein kann.
  • Der erste Tachostand, ab dem eine korrekte Einfärbung erst wieder möglich ist, muss die Form 01**** haben. Um von Tachostand 000000 zu Tachostand 010000 kommen, müsste man 256 mal auf die Taste "weiter" klicken.

 
Seite 5/18