Neue Lösungsansätze
Für Lösungen mathematischer Probleme wird oft ein Backtracking-Algorithmus verwendet. Backtracking heisst übersetzt Rückverfolgung.und gibt das dahinterstehende Prinzip gut wieder. Es wird versucht eine Teillösung zu einer Gesamtlösung auszubauen. Falls es dabei zu einem Fehler kommt wird der letzte Schritt zurückgenommen und ein alternativer Weg ausprobiert. Dies wird solange fortgeführt bis entweder eine Lösung gefunden wurde oder alls möglichen Lösungswege zu keine Lösung führten, was bedeutet das keine Lösung für das Problem existiert.
Bei einem einfachen Labyrinth bei dem es die 4 möglichen Richtungen rechts, links, vorwärts und rückwärts gibt, würde ein Backtracking-Algorithmus zur Suche des Ausgangs folgendermaßen aussehen:
[Bild oder Animation von Labyrinth einfügen]
- 1) Gehe zum Eingang des Labyrinths und führe die folgenden Schritte nacheinander aus, wenn nicht anders angegeben..
- 2) Wähle von den vier möglichen Richtungen (rechts, links, vorwärts, rückwärts) die erste aus, die möglich ist und die Du noch nicht ausprobiert hast und gehe bis zur nächsten Abzweigung
- 2a) Solltest Du dabei den Ausgang erreicht haben ist die Suche erfolgreich beendet.
-
2b) Solltest Du alle möglichen Richtungen erfolglos ausprobiert haben, gehe zur vorigen Abzweigung zurück. Wenn keine vorige Abzweigung mehr existiert ist die Suche erfolglos beendet (dies ist nur beim Startort der Fall!)
- 3) Gehe wieder zu Schritt 2
Der Algorithmus endet also damit dass man den Ausweg findet oder wieder beim Eingang
Der Backtracking-Algorithmus hat den großen Vorteil dass er immer eine Lösung liefert wenn es eine gibt.
Für den Versuche eine beliebige Landkarte mit 4 Farben zu färben würde der Backtracking-Algorithmus folgendermaßen funktionieren:
- 1) Ausgangsposition: Wir haben eine Karte in der alle Länder mit der neutralen Farbe weiss gefärbt sind. Starte mit einem beliebigen Land der Karte.
- 2) Färbe das Land mit der ersten Farbe der Menge von 4 Farben (rot, grün, blau, gelb) die Du noch nicht ausprobiert hast und die mit keiner Farbe eines Nachbarlandes übereinstimmt.
- Hast Du damit das letzte Land gefärbt wird die Suche erfolgreich beendet.
- Ist das Färben nicht möglich weil alle Farben erfolglos ausprobiert wurden dann färbe das Land in der neutralen Farbe weiss, gehe zum zuletzt gefärbten Land zurück und färbe dieses weiss. Ist kein zuletzt gefärbtes Land vorhanden weil Du bereits beim Ausgangsland angekommen bist, ist eine Färbung nicht möglich und die Suche kann beendet werden,
- 4) Gehe wieder zu Schritt 2
Es werden also nacheinander alle Länder mit einer Farbe gefärbt und anschließend getestet ob die Färbung die Vierfarben-Regel verletzt. Ist dies der Fall wird mit einer anderen Farbe fortgefahren, ist alles ok wird mit dem nächsten Land genauso verfahren. Führen bei einem Land alle 4 Färbungen nicht zum Erfolg bekommt das davor gefärbte Land eine neue Farbe. Der Algorithmus endet entweder damit dass alle Länder gefärbt sind oder er bricht ab weil keine Färbung der Landkarte mit 4 Farben möglich ist. Da der Vierfarbensatz durch den Computerbeweis als bewiesen gilt müsste der Algorithmus immer erfolgreich beendet werden.
Da jedoch nur eine bestimmte Karte gefärbt wird kann mit dem Backtracking-Algorithmus der Vierfarbensatz zumindestens nicht direkt bewiesen werden. Der Vierfarbensatz soll ja für alle möglichen Landkarten gültig sein, wir müßten daher den Algorithmus für alle möglichen Landkarten durchführen um den Vierfarbensatz zu beweisen. Da es unendlich viele Karten gibt kann dies nicht gelingen.
Das bedeutet jedoch nicht dass der Backtracking-Algirithmus nicht dabei helfen kann, einen Beweis für den Vierfarbensatz zu finden. Würde man ein entsprechendes Programm schreiben dass es ermöglicht die Suchwege zu analysieren könnte dies durchaus wertvolle Erkenntnisse bringen. Es könnte sich zum Beispiel herausstellen, dass die Suche bei bestimmten Konstellationen besonders viele Rückschritte benötigt und bei anderen Konstellationen nur selten Rückschritte nötig sind.
Eine weitere interessante Möglichkeit ist das Verändern der Reihenfolge für die Färbung in Schritt 2. Hier wurde willkürlich festgelegt dass die Farben rot, grün, blau und gelb nacheinander ausprobiert werden. Stattdessen könnten wir eine Reihenfolge festlegen die unmittelbar mit den bisher gefärbten Ländern zusammenhängt. Beispielsweise könnten wir von den noch nicht getesteten Farben immer die nehmen die bisher am seltesten bei den bereits gefärbten Ländern verwendet wurde. Dies würde wahrscheinlich zu einer gleichmässigeren Verteilung der Farben führen und könnte die Suche positiv beeinflussen.
Die vielfältigen Erkenntnisse aus der Vierfarbenforschung und der Graphentheorie bieten sicher noch eine Vielzahl anderer interessanter Möglichkeiten die Reihenfolge der Färbung festzulegen. Für die Analyse können die unterschiedlichen Regeln für die Färbung miteinander verglichen werden. Je weniger Rückschritte im Backtracking-Algorithmus eine Färbungsregel benötigt desto interessanter dürfte diese Regel für einen Beweis des Vierfarbensatzes sein. Sollte eine Färbungsregel bei einer relevanten Anzahl von Versuchen mit komplexen Landkarten mit möglichst unterschiedlichem Aufbau jedesmal ganz ohne Rückschritte auskommen, ist es sehr wahrscheinliich, dass der Beweis des Vierfarbensatzes aus dieser Färbungsregel abgeleitet werden kann.