¿Hay máximos locales en la cantidad de movimientos necesarios para resolver un cubo de Rubik?

22

Peter Shor planteó un punto interesante en relación con un intento de responder una pregunta anterior sobre la complejidad de resolver el cubo n×n×n Rubik. Había publicado un intento bastante ingenuo de mostrar que debe estar contenido en NP. Como Peter señaló, mi enfoque falla en algunos casos. Un caso potencial de tal instancia es donde existe un máximo local en la longitud de la ruta. Con esto quiero decir que puede tomar movimientos SA para resolver el cubo desde la configuración A , y SA o . Ahora, esto no es necesariamente un problema si S ASA1 movimientos para resolver el cubo desde cualquier posición que se pueda alcanzar en un movimiento desde ASA es el número máximo de movimientos necesarios para resolver el cubo en general (número de Dios para ese cubo), pero definitivamente es un problema si SA es estrictamente menor que el número de Dios para ese cubo . Entonces mi pregunta es ¿existen tales máximos locales? Incluso una respuesta para el cubo 3×3×3 sería de mi interés.

Joe Fitzsimons
fuente
Aunque no tengo un ejemplo, me sorprendería si no lo hay, porque eso parece implicar que podemos calcular el número de Dios con solo encontrar una configuración que sea un máximo local (sin embargo, este no es un argumento riguroso).
Tsuyoshi Ito
@Tsuyoshi Ah, ¡pero puede que no se haya sabido si hubo máximos locales hasta después de que se calculó el Número de Dios! Pero estoy de acuerdo en que espero que estos máximos locales existan. Simplemente no lo sé con certeza, y estaría interesado en averiguarlo.
Joe Fitzsimons
@ Joe: Sí, eso es exactamente lo que no es riguroso sobre mi argumento. Me sorprendería más rigurosamente :) si es posible demostrar que no hay máximos locales sin realizar una búsqueda exhaustiva.
Tsuyoshi Ito
1
@ Tsuyoshi Parece que los máximos locales no pueden ocurrir para distancias de camino muy cortas, y solo parecen existir cerca del número de Dios, por lo que creo que no es tan definitivo que existan.
Joe Fitzsimons
1
Sé que los gráficos de Cayley para grupos arbitrarios pueden tener máximos locales. Olvidé dónde vi este resultado, pero estoy seguro de que lo vi en alguna parte. Entonces, a menos que el grupo de cubos de Rubik sea de alguna manera especial, uno espera que también tenga máximos locales.
Peter Shor

Respuestas:

9

Al preguntarle a Tomas Rokicki, esta pregunta arrojó de inmediato la respuesta correcta ("sí, existen máximos locales"):

Si una posición exhibe simetría total, es necesariamente un máximo local (todos excepto el inicio). Un poco de reflexión debería aclarar por qué este es el caso en la QTM [métrica de cuarto de vuelta]. Para el HTM [métrica de media vuelta] es un poco más sutil pero no está mal.

...

Tal posición es pons asinorum, que es la distancia 12 en QTM y la distancia 6 en HTM (U2D2F2B2L2R2).

No veo por qué este es el caso de la métrica de media vuelta; pero para la métrica de cuarto de vuelta está claro. En una posición con simetría total, todas las posiciones vecinas deben tener la misma longitud de ruta (ya que todos los movimientos son equivalentes por simetría). Por lo tanto, una posición con simetría total debe ser un máximo local o un mínimo local estricto. Pero no pueden existir mínimos locales estrictos ... tiene que haber algún movimiento que reduzca la distancia al estado resuelto, solo por la definición de la distancia. El argumento de simetría se traduce en el cubo , al igual que la posición de ejemplo proporcionada.n×n×n

mjqxxxx
fuente
¡Qué argumento tan simple, esto es brillante!
Hsien-Chih Chang 張顯 之
Excelente, ese es un muy buen argumento!
Joe Fitzsimons
2

Aquí hay un argumento extremadamente heurístico que sugiere dónde se pueden encontrar los máximos locales. Sea el número de posiciones que requieren exactamente d movimientos para resolver. Cada movimiento desde dicha posición lleva el cubo a la distancia d - 1 , d o d + 1 ; entonces hay un total de N d - 1 + N d + N d + 1 posiciones que son accesibles. Hay M movimientos desde cada posición, lo que lleva a M nuevas posiciones; una posición a distancia dNddd1dd+1Nd1+Nd+Nd+1MMdes un máximo local cuando ninguna de estas posiciones está a la distancia d + 1 . Si tomamos estas posiciones para que se dibujen de manera uniforme al azar desde las posiciones accesibles (que, por supuesto, no lo son; esta es la parte heurística), tenemos:Md+1

Xd=P[ a given position at d is a local max ]=(Nd1+NdNd1+Nd+Nd+1)M=(1+Nd+1Nd1+Nd)M.

El número esperado de máximos locales a la distancia es N d X d .dNdXd

Para el cubo , el número de movimientos desde una posición dada es M = 18 , y las estimaciones para N d se proporcionan en el Número de Dios es 20 . Usando estos valores, encontramos que el número esperado de máximos locales es N 16 X 16 = 0.2 , N3×3×3M=18NdN16X16=0.2 y N 18 X 18 =1.5× 10 19 . Por lo tanto, es poco probable que haya máximos locales paraN17X17=9×109N18X18=1.5×1019 . En d = 17 , el número total de posiciones se estima en 12 × 10 18 , por lo que uno podría esperar probar mil millones de posiciones antes de encontrar un máximo local. Finalmente, en d = 18 , uno espera un máximo local en cada veinte posiciones.d16d=1712×1018d=18

mjqxxxx
fuente
Nd1+Nd+Nd+1Nddd1dd1d+1d. No tengo idea de cuán comunes o raras serán estas situaciones.
Joe Fitzsimons