Zur MathePrisma-Startseite
Zur Modul-Startseite  


Das Vierfarbenproblem (Action! 1)
 

 
 

 
Auf dieser Seite können wir anhand weiterer Beispiele beobachten, wie der Backtracking-Algorithmus arbeitet.

Die hier dargestellte Karte kennen wir bereits. Sie wurde erstmalig von einem Mathematiker namens Martin Gardner im Jahre 1975 veröffentlicht. Nach vielen eigenhändigen Färbungsversuchen behauptete man damals im Scherz, diese Karte sei ein Gegenbeispiel zur Vierfarbenvermutung. Mit unseren Algorithmen haben wir jetzt die Möglichkeit, uns zurückzulehnen und ein Computerprogramm für uns arbeiten zu lassen.

Im ersten Film haben wir die Karte mit einer Nummerierung "von innen nach außen" belegt. Das rechteckige Element in der Mitte wird zuerst gefärbt, danach windet sich der Lösungsweg schneckenförmig entgegen dem Uhrzeigersinn zum äußeren Rand hin.
 

 
Wir können dieses Applet als fortlaufende Animation (Funktionstasten "Film ab!" und "Film stop") oder in Einzelschritten ("schrittweise") verwenden. Mit "Reset" kann der Ausgangszustand wiederhergestellt werden. Der Film läuft mit circa einer halben Sekunde Verzögerung zwischen den einzelnen Schritten ab.

 

 
Bei der obigen Nummerierung findet der Algorithmus nach wenigen Fehlversuchen eine korrekte Einfärbung. Der zweite Film zeigt, dass bei einer ungünstigen Nummerierung das Auffinden einer Lösung wesentlich länger dauern kann. Konkret haben wir die Karte einfach mit der umgekehrten Nummerierung aus dem ersten Film belegt. Wir haben die Verzögerung zwischen zwei Schritten auf 50 Millisekunden reduziert. Trotzdem braucht der Algorithmus wesentlich länger als bei der anderen Nummerierung.
 

 
 

 
Beim Beobachten des Lösungsvorgangs bleibt einige Zeit für einen abschließenden Gedankengang:

Wir haben erkannt, dass man mit Algorithmen und deren Implementierung zwar viel Kleinarbeit von einem Computer erledigen lassen kann. Jedoch ist immer noch menschliche Intuition, bei unserem Färbungsproblem kombiniert mit einer Portion mathematischer Formulierung und Abstraktion notwendig, um Aufgaben wirklich effizient und elegant zu lösen.

Ende

    zur Startseite
Wie das war alles?
zum Wieviel-Farben-Problem
 
Seite 9/18