Peter Shor planteó un punto interesante en relación con un intento de responder una pregunta anterior sobre la complejidad de resolver el cubo 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 para resolver el cubo desde la configuración , y o . Ahora, esto no es necesariamente un problema si S A movimientos para resolver el cubo desde cualquier posición que se pueda alcanzar en un movimiento desde 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 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 sería de mi interés.
fuente
Respuestas:
Al preguntarle a Tomas Rokicki, esta pregunta arrojó de inmediato la respuesta correcta ("sí, existen máximos locales"):
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
fuente
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 dNd d d−1 d d+1 Nd−1+Nd+Nd+1 M M d es 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:M d+1
El número esperado de máximos locales a la distancia es N d X d .d NdXd
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×3 M=18 Nd N16X16=0.2 y N 18 X 18 =1.5× 10 19 . Por lo tanto, es poco probable que haya máximos locales paraN17X17=9×109 N18X18=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.d≤16 d=17 12×1018 d=18
fuente