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.<ref>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.</ref> Sie kann auch auf andere Probleme der Kombinatorik und Spieltheorie bezogen werden. Ein Algorithmus wird als Gottes Algorithmus für ein Problem oder Puzzle bezeichnet, wenn er stets eine Lösung mit kleinstmöglichster Anzahl von Schritten oder Zügen produziert.
Anwendungsbereich und Definition
Der Begriff Gottes Algorithmus bezieht sich jeweils auf ein Problem oder Puzzle, das eine endliche Anzahl von „Konfigurationen“ annehmen kann, in Verbindung mit einer eher kleinen, wohldefinierten Menge an „Zügen“, die Transformationen zwischen Konfigurationen darstellen. Ein Puzzle lösen heißt, von irgendeiner willkürlichen Startkonfiguration aus eine oder mehrere bestimmte spezifische „Endkonfigurationen“ (von endlicher Anzahl) durch die Anwendung einer Sequenz von Zügen zu erreichen. Eine solche Zugsequenz entspricht einer Lösung des Puzzles.
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 den Knoten („Punkten“) und die Züge den Kanten („Pfeilen“) des Graphen entsprechen. Eine lösende Zugsequenz (eine Lösung des Puzzles) entspricht dabei einem (gerichteten) Pfad im Graphen, der von einer Ausgangs- zu einer Endkonfiguration führt.
Ein Algorithmus heißt lösend, wenn er zu einer willkürlichen Anfangskonfiguration als Eingabe
- eine Lösung ausgibt, falls das Puzzle von der Anfangskonfiguration lösbar ist, und andernfalls
- ausgibt, dass es keine Lösung gibt.
Eine Lösung heißt optimal, wenn die Sequenz von Zügen so kurz wie möglich ist. Ein lösender Algorithmus für ein Puzzle wird Gottes-Algorithmus genannt, wenn er stets eine optimale Lösung ausgibt. Gottes Zahl schließlich ist definiert als die Länge der längsten Zugsequenz unter allen optimalen Lösungen für das Puzzle.
Ein echter „Gottes-Algorithmus“ soll auch praktikabel sein, d. h. nicht außergewöhnlich viel Speicherplatz oder Zeit benötigen. Bei vielen Puzzles könnte man zwar mit Hilfe einer riesigen Lookup-Tabelle, indiziert über alle Startkonfigurationen, schnell eine Lösung ausgeben können, aber dieses Vorgehen würde zu viel Speicherplatz erfordern.
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
| Problem | Gottes Zahl | Größe des Zustandsraums | Verdienst / Anmerkungen | Jahr | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| N-Puzzle (das verallg. 15-Puzzle) |
? | ? | NP-vollständig, vergleiche Ratner und Warmuth<ref>D. Ratner, M. Warmuth: Finding a shortest solution for the (N X N)-extension of the 15-puzzle is intractable. Journal of Symbolic Computation 10 (1990), S. 111–137</ref> | 1990 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 15-Puzzle | 80 (durchschnittlich 52,6) |
<math>\frac{16!}{2} = 10.461.394.944.000</math> | Korf und Schultze<ref>Richard E. Korf; Peter Schultze: Large-Scale Parallel Breadth-First Search (PDF; 104 kB). 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).</ref> | 2005 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 8-Puzzle | 31 (durchschnittlich 22) |
<math>\frac{9!}{2} = 181.440</math> | Reinefeld<ref name="Reinefeld_1993">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.</ref> | 1993 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 3-Puzzle | 6 (durchschnittlich 3) |
<math>\frac{4!}{2} = 12</math> | Reinefeld<ref name="Reinefeld_1993" /> | 1993 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Türme von Hanoi mit n Scheiben |
<math>2^n - 1</math> | <math>3^n</math> | siehe auch Rueda<ref><templatestyles src="Webarchiv/styles.css" />{{#if:20160304085917 | * | {{#if: Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“ | {{#invoke:WLink|getEscapedTitle|Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“}} | {{#invoke:Webarchiv|getdomain|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc}} }} (Archivversionen) | 20160304085917}} | {{#if: | }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
|
{{#invoke:WLink|getEscapedTitle|Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“}} | {{#invoke:Webarchiv|getdomain|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc}} }}] {{#ifeq: | [] | [ | ( }}{{#if: {{#if: 2025-05-22 06:41:12 InternetArchiveBot | 2025-05-22 06:41:12 InternetArchiveBot | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20160304085917}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}} }} |
{{#if: | {{{webciteID}}}}} | len|{{{webciteID}}}}} | {{#invoke:WLink|getEscapedTitle|Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“}} | {{#invoke:Webarchiv|getdomain|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc}} }}] {{#ifeq: | [] | [ | ( }}{{#if: {{#if: 2025-05-22 06:41:12 InternetArchiveBot | 2025-05-22 06:41:12 InternetArchiveBot | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }} | {{#invoke:WLink|getEscapedTitle|Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“}} | {{#invoke:Webarchiv|getdomain|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc}} }}] {{#ifeq: | [] | [ | ( }}{{#if: {{#if: 2025-05-22 06:41:12 InternetArchiveBot | 2025-05-22 06:41:12 InternetArchiveBot | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }} | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: | }}
}} |
{{{webciteID}}}}} {{#if: Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“ | {{#invoke:WLink|getEscapedTitle|Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“}} | {{#invoke:Webarchiv|getdomain|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc}} }}] ({{#if: {{#if: 2025-05-22 06:41:12 InternetArchiveBot | 2025-05-22 06:41:12 InternetArchiveBot | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}} |
{{#if: | Vorlage:Webarchiv/Today | {{#if: | Vorlage:Webarchiv/Generisch | {{#invoke:WLink|getEscapedTitle|Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“}} | {{#invoke:Webarchiv|getdomain|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc}} }}]
}}}}}}}}{{#if:2025-05-22 06:41:12 InternetArchiveBot
|
Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|
all = url= | opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original= | cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv | errNS = 0 | template = Vorlage:Webarchiv | format = * | preview = 1
}}{{#ifexpr: {{#if:20160304085917|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
|
{{#if: | }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
|
getdomain|{{{archiv-url}}}}} | web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
|
webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
|
archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
|
Execute}}|}} | {{#if: | }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}} | }} | {{#if: | }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}} |
{{#if: | {{#if: | }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc}}
|
{{#if: | }}
}}{{#if: Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“
|
isBracketedLink|Carlos Rueda: „An optimal solution to the Towers of Hanoi Puzzle“}} | {{#if: | }}
}} |
{{#if: | }}
}}{{#switch:
|
addlpages= {{#if: | }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc%7Carchiv}} |-1
|
{{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc%7C4}}%7Chttp}} |-1 | {{#switch: {{#invoke:Webarchiv|getdomain|http://www.jamesdang.com/Documents/An%20optimal%20solution%20of%20Hanoi%27s%20toweri.doc }} | daserste.ndr.de | inarchive.com | webcitation.org = | #default = {{#if: | }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}} (MS Word; 33 kB)</ref> || historisch
|
| Zauberwürfel | 20 (Viertel- und Halbdrehungen) bzw. 26 (nur Vierteldrehungen; Halbdrehung zählt als 2 Vierteldrehungen) |
<math>\frac{ 8! \cdot 3^8 \cdot 12! \cdot 2^{12}}{3 \cdot 2 \cdot 2} = </math> <math>43.252.003.274.489.856.000</math> |
Rokicki, Davidson, Dethridge und Kociemba<ref>God's Number is 20 (cube20.org)</ref>, siehe auch Optimale Lösungen des Zauberwürfels | 2010 bzw. 2014 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Schach | ? | ? | Eine Endspieldatenbank im Schach findet den kürzesten Weg zum Schachmatt. |
Siehe auch
Literatur
- David Joyner: Adventures in Group Theory. Johns Hopkins University Press (2002), ISBN 0-8018-6947-1.
Einzelnachweise
<references />