Beiträge: 14
Themen: 1
Registriert seit: Jun 2010
Es gibt schon eine mathematische Lösung zum Würfel, sie stammt von einem Herrn Morwen B. Thistletwaite. Meines Wissens hat er als erster eine maximale Länge für die Lösungen des Würfels angeben können.
Seine Zahl lag damals noch bei 45, das ist heute vielleicht nicht mehr so beeindruckend.
Die Methode, die er dafür verwendet hat beruht aber nicht auf einem Suchalgorithmus der eine Unmenge von Stellungen "absucht". Thistletwaite gibt für jeden beliebigen Würfel die Lösung in Form von 4 Tabellen an. Das heißt eine maximal 45 Züge lange Lösung ist direkt aus diesen Tabellen ablesbar, für einen Computer also praktisch ohne jede Rechenzeit.
Diese Tabellen wurden allerdings nicht von Hand erstellt, denn sie enthalten 2048, 1082565, 29400 und 663552 Einträge. Das Erstellen dieser Tabellen dauert auf meinem PC weniger als 1 Sekunde.
Beiträge: 815
Themen: 103
Registriert seit: Mar 2009
11.06.2010, 09:53
(Dieser Beitrag wurde zuletzt bearbeitet: 11.06.2010, 09:53 von Hubi.)
ja, Thistlethwaite kenne ich. Ich wusste auch, dass sie mehr für Computer als für Menschen geeignet ist, aber ich wusste nicht, dass sie tatsächlich eine mathematische Lösung in diesem Sinne ist.
Zitat:<Faz>that fast guy
<Faz>hubi
Beiträge: 1.184
Themen: 14
Registriert seit: Oct 2009
11.06.2010, 10:53
(Dieser Beitrag wurde zuletzt bearbeitet: 11.06.2010, 11:00 von Stefan Pochmann.)
Fuer die, die Thistlet
hwaite's Methode nicht kennen:
http://www.jaapsch.net/puzzles/thistle.htm
(11.06.2010, 09:02)Wuerfelschrauber schrieb: Meines Wissens hat er als erster eine maximale Länge für die Lösungen des Würfels angeben können
Ich glaub andere hatten das auch schon, aber halt laengere. Hier zB ein Buch, das einige Maximallaengen bis 140q nennt (die Markierung ignorieren, die war fuer was anderes):
http://stefan-pochmann.info/misc/images/...orrect.jpg
Thistlethwaite selbst hatte zuerst auch bloss eine 52er-Loesung, das wurde erst im Nachhinein auf 45 verbessert. Dafuer kam er aber mit kleineren Tabellen aus (siehe Jaap's Seite).
(11.06.2010, 09:02)Wuerfelschrauber schrieb: Die Methode, die er dafür verwendet hat beruht aber nicht auf einem Suchalgorithmus der eine Unmenge von Stellungen "absucht".
Nicht mehr beim Loesen, aber bei wie du schon sagtest beim Erstellen der Tabellen. Insofern nicht "mathematischer" als andere Programme/Methoden auch. Im Gegenteil,
"Loesung in Tabelle nachgucken" find ich eher *weniger* mathematisch. Und es bezieht sich auf seine Implementation der Methode, die ja nicht zwingend ist. Man kann ja auch mit der eigentlichen Methode on-the-fly suchen, ohne die Tabellen. So hab ich's vor ein paar Jahren auch mal implementiert, und Tomas und Jaap glaub ich auch (wobei ich deren Codes nie gelesen habe, ist nur eine Vermutung aufgrund der Laufzeiten):
http://tomas.rokicki.com/cubecontest/
Beiträge: 14
Themen: 1
Registriert seit: Jun 2010
Zitat:wobei ich deren Codes nie gelesen habe, ist nur eine Vermutung aufgrund der Laufzeiten
Der Code von Tomas ist ja kaum lesbar, aber recht witzig, sollte man sich anschauen. Die Vermutung stimmt übrigens, ich habe mir beides angesehen und natürlich auch Dein Programm.
Ob man das für Mathematik hält oder nicht mag Geschmackssache sein, aber ich finde doch, dass die Thistletwaite'sche Lösung einen gewissen theoretischen Wert hat. Im Gegensatz zu den Suchalgorithmen (Kociemba oder die drei genannten Contest-Programme) enthalten die Tabellen ja die Lösung für alle möglichen Würfelkonfigurationen.
Die 45 erwähnt Thistletwaite schon in dem Aufsatz der mir vorliegt. Ich habe es so verstanden, dass er die vollständigen Tabellen nur der Papierverschwendung wegen nicht ausgedruckt hat.