Kurz zur Erläuterung für alle, die nicht wissen, was damit gemeint ist:
God's Number bezeichnet die die maximale Anzahl von Zügen, die man bei einer optimalen Lösung braucht, um den Würfel zu lösen (siehe z.B.
hier).
Mein letzter Kenntnisstand ist, daß diese für den 3x3x3 Würfel irgendwo zwischen 20 (ein Beispiel für ein Sample, dessen Lösung mindestens 20 Züge braucht ist der Superflip U R U2 R F2 L U2 R F' B' R2 D R' L U2 F2 D2 F R2 D) und 22 Zügen (Beweis von Tomas Rokicki, siehe
hier) liegt. Sprich, die gesuchte Zahl ist 20, 21 oder 22.
Gibts da irgendwas Neues? Z.B. ein Beispiel für ein Sample, das nicht in 20 Zügen gelöst werden kann?
also durchschnittlich wenns optimal ist 18 und nie mehr als 20...so stehts jedenfalls in wiki
Wo steht das? Kannst du einen Link angeben?
Da steht 20 als untere und 22 als obere Grenze, wie ich ja im Ursprungsposting auch geschrieben hatte. Von 20 als obere Grenze kann ich da nichts finden.
In Patricks Link finde ich lediglich die Aussage, daß bisher kein Sample bekannt ist, das mehr als 20 Züge braucht. Aber das heißt ja nicht, daß es keins gibt.
Die erste theoretisch optimale Lösung stammt von Richard E. Korf, der 1997 zeigte, dass die durchschnittliche optimale Lösung 18 Züge benötigt.[3] Er ging außerdem davon aus, dass nie mehr als 20 Züge (Gottes Zahl) erforderlich sind,
ôps hätte mal zu ende lesen solln...wär glaub ich klüger gewesen sry^^
Davon darf er aber nicht einfach so ausgehen (im Sinne von voraussetzen). Es ist wohl ein anderes "davon ausgehen" gemeint (im Sinne von "er war der Ansicht"). Es steht auch dort, dass er das mit 20 nicht beweisen konnte.
Bisher ist nur
a) gezeigt, dass es IMMER in 22 geht
b) gezeigt, dass es FAST IMMER in 18 geht (darum benötigt auch die durchschnittliche optimale Lösung 18 moves)
c) keine Lage gefunden worden, die mehr als 20 benötigt.
Man hat aber noch längst nicht alles untersucht.
Also: Yeti hatte im Ursprungspost recht, wir wissen noch nicht, ob es "nie mehr als 20" sind.
(02.12.2009, 16:03)Hubi schrieb: [ -> ]Bisher ist nur
...
b) gezeigt, dass es FAST IMMER in 18 geht (darum benötigt auch die durchschnittliche optimale Lösung 18 moves)
Durchschnittlich 18 heißt noch lange nicht in den meisten Fällen 18. Theoretisch könnte es z.B. in 25% der Fälle in 3 Zügen gehen und in den anderen 75% der Fälle braucht man jeweils 23 Züge. Dann wären das durchschnittlich auch exakt 18 Züge.
Im streng mathematischen Sinn hast du allerdings sicher Recht:
"fast immer" heißt
"immer bis auf endlich viele Fälle". Aber so gesehen kann man den Würfel auch fast immer in einem Zug lösen.
Nur mal so ein Analogbeispiel zum Nachdenken: Die meisten Menschen haben überdurchschnittlich viele Beine.
(02.12.2009, 16:47)Yeti schrieb: [ -> ] (02.12.2009, 16:03)Hubi schrieb: [ -> ]Bisher ist nur
...
b) gezeigt, dass es FAST IMMER in 18 geht (darum benötigt auch die durchschnittliche optimale Lösung 18 moves)
Durchschnittlich 18 heißt noch lange nicht in den meisten Fällen 18. Theoretisch könnte es z.B. in 25% der Fälle in 3 Zügen gehen und in den anderen 75% der Fälle braucht man jeweils 23 Züge. Dann wären das durchschnittlich auch exakt 18 Züge.
Ich weiß, dass das noch lange nicht dasselbe ist. Das wollte ich damit auch nicht sagen. Das in der Klammer war nur so nebenbei gemerkt, aha, es geht fast immer in 18, und die optimale Lösung ist auch im Schnitt 18. Liegt wohl daran, dass die 18er-Gruppe wirklich überragend groß sein muss...
Aber ganz grob gesprochen ist es so.
btw: so wie es hier ausschaut (hab mir grad Rokickis Bericht nochmal durchgelesen) benötigt der allergrößte Teil 19 moves, nicht 18; wobei dort wiederum steht: 19 (or less)