+- Speedcube.de Forum (https://forum.speedcube.de)
+-- Forum: Speedcubing (https://forum.speedcube.de/forumdisplay.php?fid=7)
+--- Forum: Diskussion zu Methoden, Theorie und Techniken (https://forum.speedcube.de/forumdisplay.php?fid=26)
+--- Thema: Mathematische Lösung + Gottes Algorithmus (/showthread.php?tid=5317)
RE: Mathematische Lösung + Gottes Algorithmus - Swert - 16.03.2010
Wenn man einem alten Mann glaubt, der mit meinem Kumpel gesprochen hat glaubt, geht das.
Er sprach davon, dass er ein Buch hat, worin steht, wie man den Cube in "nicht mehr als 20 Zügen" löst.
Aber Spass bei Seite, wenn man das wirklich berechnen will, müsste man erst eine Translation finden, mit dem man rechnen kann. Also auch z.B. beweisen, dass RUR'U' x 6 zum gleichen Ergebnis führt, wie R'R. Ich vermute, dass es daran scheitern wird..
RE: Mathematische Lösung + Gottes Algorithmus - Von Birne - 16.03.2010
ein freund von mir lässt grad nen programm laufen, um zu gucken, wieviele mögliche stellungen es gibt.
Dies hat er selbst geschrieben, nachdem wir nicht auf ne lösung gekommen sind, wie man das ausrechnen könnte...
RE: Mathematische Lösung + Gottes Algorithmus - Stefan Pochmann - 16.03.2010
(16.03.2010, 19:55)Von Birne schrieb: ein freund von mir lässt grad nen programm laufen, um zu gucken, wieviele "muster" es gibt.
Was meinst du mit "muster"?
RE: Mathematische Lösung + Gottes Algorithmus - Swert - 16.03.2010
(16.03.2010, 19:55)Von Birne schrieb: ein freund von mir lässt grad nen programm laufen, um zu gucken, wieviele mögliche stellungen es gibt.
Dies hat er selbst geschrieben, nachdem wir nicht auf ne lösung gekommen sind, wie man das ausrechnen könnte...
Und dafür brauch man ein Programm? Wenn es dir nur um die Stellungen geht ist das wirklich rein mathematisch zu lösen, da du nicht von Drehungen, sondern von Stellungen ausgehst.
RE: Mathematische Lösung + Gottes Algorithmus - Hubi - 17.03.2010
(16.03.2010, 19:55)Von Birne schrieb: ein freund von mir lässt grad nen programm laufen, um zu gucken, wieviele mögliche stellungen es gibt.
Dies hat er selbst geschrieben, nachdem wir nicht auf ne lösung gekommen sind, wie man das ausrechnen könnte...
Die Ordnung der Rubikgruppe ist:
(8!*12!*3^8*2^12)/(2*2*3) = 43 252 003 274 489 856 000
8! für CP, 12! für EP, 3^8 für CO, 2^12 für EO.
/2 für OP, /2 für PP und /3 für Corner Misorientation.
Er kann ein Programm schreiben, das Positionen durchgeht, kommt aber nicht auf diese - zugegeben eher simple - Möglichkeit, die Ordnung der Rubikgruppe auszurechnen? achja, und GIDF.
RE: Mathematische Lösung + Gottes Algorithmus - Flo - 17.03.2010
(16.03.2010, 19:25)Swert schrieb: Aber Spass bei Seite, wenn man das wirklich berechnen will, müsste man erst eine Translation finden, mit dem man rechnen kann. Also auch z.B. beweisen, dass RUR'U' x 6 zum gleichen Ergebnis führt, wie R'R. Ich vermute, dass es daran scheitern wird..
Diese "Translation" die du meinst, nennt sich "Permutation". Die Ordnung eines Zuges (in deinem Fall: RUR'U' hat Ordnung 6) auszurechnen ist in dieser Schreibweise völlig trivial (Stichwort "kleinstes gemeinsames Vielfaches") und dauert mit Stift und Papier maximal 5 Minuten. Google mal nach "Permutation", "disjunkter Zykelschreibweise" und "Ordnung von Gruppenelementen".
Es ist natürlich theoretisch kein Problem, die Gotteszahl auszurechnen oder für einen beliebigen Scramble die kürzeste Lösung zu finden, schliesslich gibt es nur endlich viele Möglichkeiten für beides (dümmster Ansatz: Alles ausprobieren). Problem in der Praxis ist, wie Moritz schon sagte, dass man dafür nichtmal Ansatzweise genug Rechenpower oder Speicherplatz zur Verfügung hat.
Ich habe sowas vor einiger Zeit mal Ansatzweise auf dem Matheplaneten beschrieben, vielleicht hilft dir das.
RE: Mathematische Lösung + Gottes Algorithmus - Stefan Pochmann - 17.03.2010
(17.03.2010, 07:54)Hubi schrieb: (8!*12!*3^8*2^12)/(2*2*3) = 43 252 003 274 489 856 000
Je nachdem, was mit "Muster" gemeint ist, zaehlst du da aber eventuell fast alle mehrfach. Zum Beispiel ist es voellig legitim, zu sagen, dass RU2 und FL2 dasselbe Muster erzeugen.
RE: Mathematische Lösung + Gottes Algorithmus - Hubi - 19.03.2010
Darüber gab es, wenn ich mich richtig entsinne, schon eine laaaaange Diskussion im speedsolving-Forum. Und du hast auch Recht.
Was macht man dann? noch einmal /24?
an und für sich kann dann nämlich jeder "Muster-Algorithmus" auf 24 verschiedene Arten ausgeführt werden: mit jeder der 6 Seiten als U, jeweils mit 4 verschiedenen Seiten als F
RE: Mathematische Lösung + Gottes Algorithmus - Stefan Pochmann - 20.03.2010
(19.03.2010, 07:26)Hubi schrieb: Was macht man dann? noch einmal /24?
an und für sich kann dann nämlich jeder "Muster-Algorithmus" auf 24 verschiedene Arten ausgeführt werden: mit jeder der 6 Seiten als U, jeweils mit 4 verschiedenen Seiten als F
Nee, nee, nee, so einfach ist das nicht. Beim Superflip zB ist es ja egal, wie man den Wuerfel haelt, wird also durch die urspruengliche Zahlung *nicht* 24 mal gezaehlt. Und zB bei der U-Drehung oder der H-Perm sind y-Rotationen wirkungslos, die werden also nur 6 mal gezaehlt. Da kannst du nicht einfach durch 24 teilen, da musst du auf solche Symmetrien achten!
Hier die wohl erste Berechung, wenn Muster nach M-Symmetrien als aequivalent angesehen werden (das ist etwa Faktor 48, durch die 24 Wuerfelrotationen sowie Spiegelung oder Invertierung, bin mir grad nicht sicher welches von beidem):
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__The_real_size_of_cube_space.html
RE: Mathematische Lösung + Gottes Algorithmus - Marv_sc - 29.03.2010
Der Würfel als mathematische Gruppe
Der Würfel kann als mathematische Gruppe aufgefasst werden.
Hierfür wird jede Stellung als eine Verknüpfung der sechs möglichen Basis-Permutationen \boldsymbol B = \{V, H, R, L, O, U\} betrachtet.
Alle möglichen Permutationen (Stellungen) bilden die Menge \boldsymbol G_W. Jede Stellung ist durch eine Verknüpfung der sechs Grundpermutationen \boldsymbol B_W = \{V, H, R, L, O, U\} \subset \boldsymbol G_W zu erreichen, die mit der zweistelligen Verknüpfung \circ:\boldsymbol G\times \boldsymbol G\rightarrow \boldsymbol G verbunden werden.
Außerdem existiert sowohl ein neutrales Element, die Grundstellung i (entspricht einer „Nulloperation“ ausgeführt auf dem gelösten Würfel), denn für alle möglichen Permutationen (Gruppenelemente) p gilt p\circ i = i \circ p = p, als auch ein inverses Element, da zu jeder Permutation p ein Element p − 1 mit p\circ p^{-1} = p^{-1}\circ p = i existiert, zum Beispiel R \circ R^{-1} = i oder H^{-2} \circ U^{-1} \circ U \circ H^2 = i. Weiterhin gilt für alle X \in \boldsymbol B_W: X^2 = X^{-2}.
Das Tripel (\boldsymbol G,\circ, i) bildet daher eine Gruppe im Sinne der Algebra. Diese ist nicht kommutativ, da die Verknüpfung \circ nicht kommutativ ist (R \circ H \neq H \circ R).
Lösungen des Würfels
Sei jetzt eine Permutation s \in \boldsymbol G_W gegeben (ein verdrehter Würfel), so besteht die Aufgabe darin, eine endliche Folge (σi) von Permutationen aus der Menge \boldsymbol B_W zu finden, die genau diese Permutation s erzeugt:
\sigma_1 \circ \sigma_2 \circ \ldots \circ \sigma_n = s
Die Lösung ist nicht eindeutig, das heißt, es gibt viele Lösungen, von denen die kürzeste gesucht ist. Der Durchmesser der Gruppen, also die maximale Länge einer Permutation, mit der alle Elemente aus \boldsymbol G erreicht werden, ist für \boldsymbol G_W unbekannt.
Im Juni 2007 haben Gene Cooperman und Dan Kunkle von der Northeastern University in Boston gezeigt, dass 26 Züge stets ausreichen.[5] Im April 2008 hat sich diese Schranke nochmal auf 23 verringert (s.o.).
Ordnung der Gruppe G
Die Ordnung einer Gruppe (\boldsymbol G,\circ,i) entspricht der Mächtigkeit ihrer Trägermenge |\boldsymbol G|. Da es nur eine endliche Zahl von möglichen Stellungen geben kann, entspricht diese der Anzahl der möglichen Stellungen:
|\boldsymbol G_W| = \frac{ 8! \cdot 3^8 \cdot 12! \cdot 2^{12}}{3 \cdot 2 \cdot 2} = 43.252.003.274.489.856.000 \approx 4{,}3 \cdot 10^{19} [6]
Diese ergeben sich aus
* 8 Stellen, an denen sich die Eckwürfel befinden können (8!),
* 3 Drehpositionen, die jeder Eckwürfel einnehmen kann (38),
* 12 Stellen, auf die sich die Kantenwürfel verteilen (12!),
* 2 Drehpositionen, die jede Kante einnehmen kann (212).
Der Nenner ergibt sich aus drei Bedingungen, die gelten, wenn der Würfel verdreht, aber nicht auseinandergenommen wird:
* Wenn ein Eckwürfel verdreht ist, dann ist immer eine weitere Ecke verdreht (3)
* Wenn eine Kante verdreht ist, dann ist immer eine weitere Kante verdreht (2)
* Wenn zwei Eckwürfel in ihrer Stelle vertauscht, aber nicht verdreht sind, dann sind auch zwei Kanten miteinander vertauscht (2).
Aus Wikipedia da