Eine notwendige Anzahl der Züge, um den Zauberwürfel zu lösen

Und für wie viel ist in der Regel den Würfel Rubiks Sie sammeln?

Daniel Kunkle (Daniel Kunkle) und Gene Cooperman (Gene Cooperman) von der Northeastern University Boston (Northeastern University) einen Supercomputer-Programm, 63 Stunden Arbeit die minimale Anzahl von Bewegungen, die immer ausreicht, um den Zauberwürfel aus beliebigen Quellen zusammenzubauen gefunden Position.

Die Gesamtzahl der möglichen Kombinationen von einem klassischen Zauberwürfel (3 x 3 x 3 Zellen) ist 43 Trillionen (a Milliarden Milliarden).

Finden aller möglichen Lösungen für jede Startposition — eine unmögliche Aufgabe, selbst für einen Supercomputer. Deshalb haben die Autoren mit einem speziellen Algorithmus von der Arbeit kommen, so dass sie zur Lösung von langjährigen Problemen kam in der Nähe — Erkenntnis «Gottes» (Gods Number) — so ist die kleinste Anzahl von Zügen, für die im Prinzip möglich, einen Würfel von absolut jeder Ausgangsposition aufbauen (vorausgesetzt, dass Gott weiß immer die kürzeste Strecke).

Daniel und seine Frau haben den Computer programmiert, um die kürzeste Lösung, um eine von jeder 15.000 einiger Zwischenstellungen, Festlegung im Voraus, was jeder von ihnen kann auf die Anordnung eines Würfels für eine angemessene Anzahl von Stufen führen zu finden.

So stellte sich heraus, dass mit jeder Ausgangslage Würfel können Sie maximal 29 bewegt sich zu sammeln (und manchmal — viel schneller). D.h. — Andere Lösungen, wobei die Anzahl von Windungen 30, 75 oder 200, zum Beispiel, muss es nicht optimal erkannt werden.

Der Großteil der Startpositionen erfordern nur eine 26-minütige oder weniger bewegt sich für seine Entscheidung.

Die Autoren der Arbeit an mehreren Positionen fokussiert, dessen Lösung erforderlich 27-29 bewegt. Die Anzahl solcher Kombinationen Problem war nicht groß, so dass sie einen Supercomputer haben, Ordnung in alle strategischen Optionen einen Würfel zu bauen und den kurzen zu finden. Es stellte sich heraus, dass alle schweren Gegenstände sind auch in 26 bewegt oder weniger gelöst!

Kein Wunder also, wir werden von den Aufzeichnungen überrascht — siehe zum Beispiel, 11-Sekunden-cube Montage.

Die Forscher vermuten, dass «die Zahl der Gott»Letztlich muss mit 20 klein sein. So in diesem Kalkül, sie sind sehr nah an ihm.

Seine Co-Autoren Berechnungen auf dem Internationalen Symposium über Symbolische und Algebraische Computing (ISSAC 2007) vorgestellt, die vor kurzem in der kanadischen Stadt Waterloo (Waterloo) statt.

Finden Sie heraus, zur gleichen Zeit die letzten endgültigen und vollständigen Lösung der Kontrolleure.

Share →