Gibt es lokale Maxima in der Anzahl der Züge, die erforderlich sind, um einen Zauberwürfel zu lösen?

Peter Shor brachte einen interessanten Punkt im Zusammenhang mit dem Versuch zur Beantwortung einer früheren Frage zur Komplexität der Lösung des Rubiks-Würfels . Ich hatte einen ziemlich naiven Versuch gepostet zu zeigen, dass es in NP enthalten sein muss. Wie Peter betonte, schlägt mein Ansatz in einigen Fällen fehl. Ein möglicher Fall eines solchen Falles besteht darin, dass in der Pfadlänge ein lokales Maximum existiert. Damit meine ich, dass es möglicherweise Züge , um den Würfel aus Konfiguration zu lösen , und entweder oder Züge, um den Würfel aus jeder Position zu lösen, die in einem Zug von . Nun, das ist nicht unbedingt ein solches Problem, wennS A A S A S A - 1 A S $n \times n \times n$$S_A$$A$$S_A$$S_A - 1$$A$$S_A$ist die maximale Anzahl von Zügen, die erforderlich sind, um den Würfel im Allgemeinen zu lösen ( Gottes Nummer für diesen Würfel), ist jedoch definitiv ein Problem, wenn streng unter Gottes Nummer für diesen Würfel liegt. Meine Frage ist also, ob es solche lokalen Maxima gibt. Sogar eine Antwort für den Würfel würde mich interessieren. 3 × 3 × $S_A$$3 \times 3 \times 3$

Wenn Sie Tomas Rokicki diese Frage stellen, erhalten Sie sofort die richtige Antwort ("Ja, es gibt lokale Maxima"):

Wenn eine Position eine vollständige Symmetrie aufweist, ist zwingend ein lokales Maximum erforderlich (alle außer dem Start). Ein kleiner Gedanke sollte verdeutlichen, warum dies bei der QTM [Vierteldrehungsmetrik] der Fall ist. Für die HTM ist es etwas subtiler, aber nicht zu schlecht.

...

Eine solche Position ist pons asinorum, dh Abstand 12 in QTM und Abstand 6 in HTM (U2D2F2B2L2R2).

Ich verstehe nicht, warum dies für die Metrik mit halber Umdrehung der Fall ist. aber für die Vierteldrehungsmetrik ist es klar. In einer Position mit vollständiger Symmetrie müssen alle benachbarten Positionen dieselbe Pfadlänge haben (da alle Bewegungen symmetrisch sind). Eine Position mit vollständiger Symmetrie muss also entweder ein lokales Maximum oder ein striktes lokales Minimum sein. Aber strenge lokale Minima nicht existieren können ... es muss sein , einiger Schritt, um den Abstand zu dem gelösten Zustand reduziert, nur durch die Definition des Abstands. Das Symmetrieargument wird wie die angegebene Beispielposition in den Würfel übersetzt .$n \times n \times n$

Hier ist ein extrem heuristisches Argument, das vorschlägt, wo lokale Maxima gefunden werden können. Sei die Anzahl der Positionen, für deren Lösung genau d Züge erforderlich sind . Jede Bewegung von einer solchen Position bringt den Würfel zum Abstand d - 1 , d oder d + 1 ; es sind also insgesamt N d - 1 + N d + N d + 1 Positionen zugänglich. Es gibt M Züge von jeder Position, die zu M neuen Positionen führen. eine Position im Abstand $N_d$$d$$d-1$$d$$d+1$$N_{d-1} + N_d + N_{d+1}$$M$$M$$d$ist ein lokales Maximum, wenn sich keine dieser Positionen im Abstand d + 1 befindet . Wenn wir davon ausgehen, dass diese Positionen gleichmäßig zufällig aus den zugänglichen Positionen gezogen werden (was natürlich nicht der Fall ist; dies ist der heuristische Teil), haben wir:$M$$d+1$

$d$$N_d X_d$

$3 \times 3 \times 3$$M=18$$N_d$$N_{16} X_{16} = 0.2$$N_{17} X_{17} = 9 \times 10^9$$N_{18} X_{18} = 1.5 \times 10^{19}$$d \le 16$$d=17$$12 \times 10^{18}$$d=18$