La disminución de límite superior en el Cubo de Rubik de soluciones - ¿por qué tanto tiempo?

Question

Recuerdo claramente la noticia en 2007 acerca de cómo los investigadores de la Universidad Northwestern, había establecido la parte superior del obligado en cuanto a movimientos necesarios para resolver un Cubo de Rubik en el 26. (No he estado prestando atención, ya, pero es obviamente mucho menor ahora.)

Dado: El número de estados posibles de un adecuado Cubo de Rubik es

$$ 11! \cdot 8! \cdot 3^{8} \cdot 2^{12} = 43,252,003,274,489,856,000 ~~ (4.3252 \times 10^{19}) $$

Utilizando el trimestre-gire a la métrica, sólo hay seis (6) posibles movimientos disponibles para cualquier cubo en cualquier momento (utilizando la notación Singmaster):

$$ \text{L, R, U, D, F, y B} $$

Suponiendo que:

1. sólo el cuarto de vuelta métrica se utiliza (por ejemplo, $\text{F}2$ es considerado dos movimientos, F),
2. todos los movimientos son en una sola dirección (por ejemplo, $\text{R'}$ se conseguiría $\text{R R R}$ o $\text{R}3$]),
3. la aplicación de un movimiento y, posteriormente, su inversa sería ignorado estipulado por el punto (2) anterior, y también ignorando el mismo movimiento 4 veces (para producir el mismo estado original antes de los 4 movimientos),

entonces: un árbol de decisión puede ser hecho en donde cada nodo representa un singular (válido) del estado. Este sería un 6-ary árbol de decisión, con cada rama representa cada uno de los 6 movimientos básicos por encima.

Desde mi CS de la educación, sé que cualquier árbol de decisión con $n$ nodos y $b$ hija ramas por nudo tendrá en la mayoría de las $\lceil\textbf{log}_{b} \textbf{n}\rceil$ niveles. Para los estados de un Cubo de Rubik, este es

$$ \log_{6} (11! \cdot 8! \cdot 3^{8} \cdot 2^{12}) \cong \lceil 24.8473 \rceil = 25 ~\text{niveles} $$

Lo que esto significa es que uno puede barajar un Cubo de Rubik de un estado a cualquier otro estado (por ejemplo, el cubo resuelto) en no más de 25 movimientos.

A pesar de que muchos simetrías y optimizaciones señaló en code20.org muestran que el número máximo de movimientos es menor, mi pregunta es sobre el Noroeste de la Univ. descubrimiento en particular.

Dado que

• el Cubo de Rubik fue inventado en 1974 y públicamente introducido en 1980,
• árboles de decisión en ciencias de la computación han existido desde al menos la década de 1970, y
• la Universidad de Northwestern de investigación (2007) dio a 26 mueve como un recién establecido límite superior (de acuerdo con mis cálculos anteriores),

entonces mi pregunta es:

Lo que llevó tanto tiempo?

Hay algo que falta en mi matemáticas de arriba? O fue la complejidad de resolver el cubo no se entiende completamente?

Una última nota: recuerdo claramente esta investigación anuncio en particular en lo que yo estaba enseñando en una CS de laboratorio en la escuela de posgrado en el tiempo, y he discutido este tema con mis alumnos. El Noroeste de la nota de prensa parece dar a entender que su descubrimiento fue una "oferta muy grande", sin embargo, el análisis matemático que parecía obvio para mí en ese momento. Extraño...

Para el registro, he leído varios cubo de Rubik preguntas (y respuestas) aquí en matemáticas SE (y también de CS SE y Stack Overflow), pero no pude encontrar nada sobre este tema en particular.

Answer 1

Los nodos del árbol que describe no son únicas. Asegúrese de que usted puede caber 43 trillones nodos en niveles de 25, pero debido a su árbol permite duplicados, usted no puede estar seguro de que tienes todas las posiciones únicas de el cubo.

Por ejemplo, considere el nodo alcanzado por el giro de RL en comparación con el nodo alcanzado por el giro de LR.

Creo que eso es lo que se hacer con la Regla #3: tratando de eliminar obvio duplicados, pero en ese caso cada nodo no tiene 6 hijos, por lo tanto ya no puede hacer $\lceil\log_b n\rceil$. Por ejemplo ¿cuántos niños el nodo alcanzado por RRR?

Por lo que vale no es necesario definir en una sola dirección-sólo métrica para ello (por desgracia imperfecto) análisis. En regular media vuelta métrica, cada nodo tiene 18 hijos. Por lo $\lceil\log_{18} n\rceil=\lceil15.6428\rceil=16$, que es mucho menos de lo que sabemos que es necesario, debido a tantos nodos duplicados en nuestro árbol.

(Crédito donde el crédito es debido: esto es básicamente @Arthur respuesta que dio en los comentarios.)

Answer 2

Sí, me he dado @timidpueo el crédito para responder a esta pregunta, y @Arthur hizo algunos buenos comentarios, pero todavía siento la necesidad de aclarar el gráfico de la topología de la modelo estaba reclamando en referencia a resolver el Cubo de Rubik en 26 o menos se mueve.

Primero: Mi pregunta puede aparecer en el límite de la retórica (gee, espero que el SE de la comunidad no me echan para eso!!!), pero yo estaba sinceramente curioso lo que llevó tanto tiempo para las matemáticas para ponerse al día con probar la solución de mover las secuencias en un número finito de movimientos.

Segundo: La topología me había descrito en el 6-ary árbol que he mencionado anteriormente fue sustancialmente carece de lo que yo había imaginado hace unos 10 años (en el momento que vio el Noroeste de prensa). Esto se debe principalmente a un descuido por mi parte en la pregunta anterior, así que me gustaría volver a hacer la afirmación de que el Cubo puede ser resuelto en 26 movimientos o menos.

Dado un (válido) $3 \times 3$ Cubo de Rubik, con el mismo 3 de las restricciones indicadas anteriormente, en la representación de una solución, pero con las siguientes restricciones adicionales, todavía reclamo de una solución de secuencia podría ser modelado por una 6-ary árbol:

4. Con todos los movimientos en una sola dirección, entonces el árbol de decisión se convierte en un dirigidos gráfico. Por ejemplo, Si se aplica un movimiento $R$ a un cubo, entonces el $R'$ no puede ser hecho simplemente para volver al estado original. (Tendrías que hacer movimientos $\{R R R\}$ para volver al primer estado.)

5. Cada nodo en el 6-ary árbol representa un único estado del cubo. Esto significa que hay NO DUPLICADOS en el árbol. Más sobre esto más adelante...

6. En una situación teórica en la que alguien considera que la aplicación de la mudanza secuencia $\{R R\}$ dos veces (volviendo al estado original), entonces esto representa una ruptura filosófica en lo que define a resolver el Cubo. Así, por ejemplo, un grafo dirigido con cada estado es único, entonces esto significa que usted no puede simplemente ir de $S \rightarrow \{F F\} \rightarrow S' \rightarrow \{F F\} \rightarrow S$. Por lo tanto, no hay ciclos, y no hay nodos duplicados. Si estás tratando de ir de por ejemplo, un estado resuelto a un estado diferente, a continuación, utilizando el 6-ary árbol modelo implica que el estado de destino es el superior (raíz) del nodo.

7. Esto también significa que la deseada (nodo raíz) del estado es arbitraria. Mi reclamo es que uno puede ir de cualquier estado a cualquier otro estado en 26 movimientos (o menos), independientemente de lo que dichos estados. (Por supuesto, la mayoría de la gente quiere resolver el cubo, así que va sin razón que la solución de estado es también el nodo raíz.)

8. Si dos diferentes soluciones fueron a existir desde el mismo estado inicial al mismo estado final, a continuación, cada uno iba a tomar una ruta diferente hasta el árbol, pero cada estado intermedio a lo largo de cada ruta de acceso será exclusivo de cualquiera de los otros. Pero esto no puede suceder! La prueba por contradicción: Si el mismo estado existido a lo largo de dos soluciones diferentes caminos, a continuación, sólo una de las soluciones podría existir desde que el estado para el estado resuelto. Inductivamente, esta podría ser la que se muestra todo el camino hacia abajo a sólo dos movimientos, pero como he dicho anteriormente en (4), que no puede suceder.

9. Un último punto, pero uno muy importante: a Pesar de las limitaciones que yo he descrito, es posible aplicar un movimiento de la secuencia de cualquier posible estado a cualquier otro posible estado con sólo los seis movimientos de $\{L R F B U D\}$. Para aquellos familiarizados con la Notación Singmaster, luego pensar en el sentido contrario "prime" se mueve, (por ejemplo, $\{L', R', etc.\}$) como el paso hacia adelante tres veces, y el interior de la capa se mueve (por ejemplo, $\{.L, etc.\}$) como una combinación de $\{L L L R\}$ que realiza el mismo.

Una nota final: En la contestación de mi "¿por Qué les tomó tanto tiempo" pregunta, supongo que basar un modelo de árbol matemáticamente para resolver el Cubo de Rubik se tomó algún tiempo para desarrollarse adecuadamente, y ver cómo todas las restricciones mencionadas en el modelado de la solución de árbol de decisión de las cosas un poco complicado, ahora puedo entender por qué tomó un tiempo.

También me gustaría agradecer a la cube20.org página web tal como se menciona algunas de las razones por las que Dios "Número" es sólo el 20 para el conjunto completo de movimientos Singmaster-pero tenga en cuenta que su sitio todavía se menciona 26 mueve como una mínima cota superior en resolver el Cubo con el trimestre-gire a la métrica.

Los comentarios son sin duda bienvenida. Gracias!