Gottes Algorithmus

Gottes Algorithmus (englisch God’s Algorithm) ist ein Begriff aus Diskussionen über die optimale Lösung des Zauberwürfels. Die Formulierung stammt von dem englischen Gruppentheoretiker John Conway oder einem seiner Kollegen in Cambridge.^[1] Er kann auch auf andere Probleme der Kombinatorik und Spieltheorie bezogen werden. Er bezeichnet jeden Algorithmus, der eine Lösung mit kleinstmöglichster Anzahl von Schritten oder Zügen produziert. Ein allwissendes Wesen wüsste einen optimalen Weg von jeder möglichen Konfiguration.

Anwendungsbereich und Definition

Der Begriff bezieht sich auf Puzzle, die eine endliche Anzahl von „Konfigurationen“ annehmen können, mit einer eher kleinen, wohldefinierten Menge an „Zügen“, die Transformationen zwischen Konfigurationen darstellen. Ein Puzzle lösen heißt, eine oder mehrere bestimmte spezifische „Endkonfigurationen“ (von endlicher Anzahl) von irgendeiner willkürlichen Startkonfiguration zu erreichen, durch die Anwendung einer Sequenz von Zügen.

Auf einige gut bekannte Puzzle trifft die Beschreibung zu, z.B. Mechanische Geduldspiele wie den Zauberwürfel, Türme von Hanoi und das 15-Puzzle. Auch Solitaire zählt dazu, ebenso viele Logik-Puzzle wie das Problem der Missionare und Kannibalen. Ihnen gemeinsam ist die mathematische Modellierbarkeit als gerichteter Graph, wobei die Konfigurationen zu Punkten und die Züge zu Pfeilen werden.

Ein Algorithmus gilt als lösend, wenn er aus dem Input einer willkürlichen Anfangskonfiguration einen Output in Form einer Zugsequenz, die die Wunschkonfiguration herstellt, generiert, falls das Puzzle von dieser Anfangskonfiguration lösbar ist, und ansonsten die Unmöglichkeit einer Lösung ausgibt. Eine Lösung ist optimal, wenn die Sequenz von Zügen so kurz wie möglich ist. Ein Gottes-Algorithmus löst ein Puzzle immer optimal.

Ein echter „Gottes-Algorithmus“ soll auch praktikabel sein, d.h. nicht außergewöhnlich viel Speicherplatz oder Zeit benötigen. So würde eine riesige Lookup-Tabelle, indiziert für alle Startkonfigurationen, Lösungen sehr schnell ausgeben, aber viel zu viel Speicherplatz belegen.

Anstatt nach einer vollständigen Lösung zu fragen, kann man auch nach dem besten ersten Einzelzug nach der Startkonfiguration fragen. Ein Algorithmus für einzelne Züge kann in einen Algorithmus für die Gesamtlösung transformiert werden, indem man ihn bis zur Schlusskonfiguration wiederholt. Umgekehrt kann so auch der Algorithmus für die Gesamtlösung in Algorithmen für Einzelzüge zerlegt werden.

Beispiele

Das 15-Puzzle lässt sich in maximal 80 Zügen lösen; eine aus den 16!/2 = 10.461.394.944.000 zufällig gewählte Ausgangskonfiguration lässt sich in durchschnittlich 53 Zügen lösen.^[2] Für das N-Puzzle, ein generalisiertes 15-Puzzle, ist das Problem einer Lösung als NP-schwer bekannt. Unbekannt ist jedoch, ob ein praktischer Gottes-Algorithmus existiert.^[3] Zumindest für das 3- und das 8-Puzzle sind auch Gottes Zahlen bekannt, ersteres ist in maximal 6 (durchschnittlich 3), letzteres in maximal 31 (durchschnittlich 22) Zügen lösbar.^[4]

Für die Türme von Hanoi gibt es einen Gottes-Algorithmus für beliebig viele Scheiben.^[5]

Eine Endspieldatenbank im Schach findet einen Gottes-Algorithmus für den kürzesten Weg zum Schachmatt.

Der Zauberwürfel lässt sich in maximal 20 Zügen lösen^[6] (siehe Optimale Lösungen des Zauberwürfels).

Einzelnachweise

1. ↑ Vgl. Jerry Slocum: The Cube. The Ultimate Guide to the World's Bestselling Puzzle. Secrets – Stories – Solutions. New York: Black Dog & Leventhal, 2009, S. 26.
2. ↑ Richard E. Korf; Peter Schultze: Large-Scale Parallel Breadth-First Search. In: AAAI Conference On Artificial Intelligence. Proceedings of the 20th national conference on Artificial intelligence 3 (2005), S. 1380-1385, hier S. 1384-1385 (Fifteen Puzzle), Table 2 (States as a Function of Depth for Fifteen Puzzle).
3. ↑ Richard E. Korf: Finding optimal solutions to Rubik's Cube using pattern databases. In: Proceedings of the National Conference on Artificial Intelligence (AAAI-97), Providence, Rhode Island, Jul 1997, S. 700–705.
4. ↑ Alexander Reinefeld: Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence (1993), Chambery Savoi, France, S. 248-253.
5. ↑ Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“
6. ↑ God's Number is 20

Literatur

• David Joyner: Adventures in Group Theory. Johns Hopkins University Press (2002), ISBN 0-8018-6947-1.

Siehe auch

• Orakel-Turingmaschine