Algoritmo de dios

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 7 de marzo de 2022; las comprobaciones requieren 2 ediciones .

El algoritmo de Dios  es un concepto que surgió durante la discusión sobre las formas de resolver el cubo de Rubik . El término también se puede utilizar en relación con otros acertijos de permutación . El algoritmo de dios del rompecabezas es cualquier algoritmo que produce una solución de rompecabezas que contiene el mínimo número posible de movimientos (solución óptima) a partir de cualquier configuración dada.

Uno de los pioneros de la teoría matemática del Cubo de Rubik , David Singmaster [1] , describe la aparición del término de la siguiente manera:

John Conway , uno de los principales teóricos de grupos del mundo, señaló que el Cubo obedece a las llamadas leyes de conservación (o paridad), lo que significa que algunos movimientos son simplemente imposibles. Conway o uno de sus colegas en Cambridge definió el camino más corto desde cualquier estado hasta el estado inicial como "algoritmo de Dios".

Texto original  (inglés)[ mostrarocultar] John Conway, uno de los mayores grupos de teóricos del mundo, observó que el Cubo obedece a lo que se conoce como leyes de conservación (o paridad), lo que significa que algunos movimientos simplemente no son posibles. Conway o uno de sus colegas en Cambridge definió la ruta más corta desde cualquier posición dada de regreso a la posición inicial como "Algoritmo de Dios". —David Singmaster [2]

Definición

El algoritmo de Dios puede existir para acertijos con un número finito de configuraciones posibles y con un conjunto finito de "movimientos" permitidos en cada configuración que traducen la configuración actual en otra. El término "resolver el rompecabezas" significa indicar una secuencia de movimientos que lleva una configuración inicial a una configuración final. La solución óptima al acertijo es indicar la secuencia más corta de movimientos para resolver el acertijo. Puede haber varias soluciones óptimas.

Los acertijos notables que se incluyen en esta definición incluyen el Cubo de Rubik , la Torre de Hanoi , el Juego de 15 , el Chip Solitaire , varios problemas de transfusión y transporte (" Lobo, cabra y repollo "). Todos estos rompecabezas tienen en común que pueden describirse como un gráfico , cuyos vértices son todas las configuraciones posibles del rompecabezas, y los bordes son las posibles transiciones entre ellos ("movimientos").

En muchos de estos rompecabezas, la configuración final se asume implícitamente, por ejemplo, en "etiquetas", una disposición ordenada de huesos, para un cubo de Rubik, del mismo color que las caras. En estos casos, "ensamblar el rompecabezas" significa que para una configuración inicial arbitraria, se requiere especificar una secuencia de movimientos que conducen a una configuración final fija .

El algoritmo resuelve el rompecabezas si toma como entrada un par arbitrario de configuraciones inicial y final (o solo la configuración inicial si la configuración final es fija) y devuelve como resultado una secuencia de movimientos que transfiere la configuración inicial a la final ( si tal secuencia existe, de lo contrario, el algoritmo informa de la imposibilidad de una solución). La solución óptima contiene el mínimo número posible de movimientos.

Entonces, el algoritmo de Dios (para un acertijo dado) es un algoritmo que resuelve el acertijo y encuentra al menos una solución óptima para un par arbitrario de configuraciones.

Algunos autores creen que el algoritmo de Dios también debería ser práctico , es decir, usar una cantidad razonable de memoria y completarse en un tiempo razonable.

Sea G un grupo de acertijos de permutación (con un conjunto generador dado), v un vértice del gráfico de Cayley de G . Encuentre un algoritmo práctico y eficiente para determinar un camino desde v hasta un vértice v 0 asociado con un elemento neutro cuya longitud es igual a la distancia desde v hasta v 0 . [...] Este algoritmo se llama el algoritmo de Dios .

Texto original  (inglés)[ mostrarocultar] Sea G el grupo de un rompecabezas de permutaciones (con un conjunto generador fijo) y sea v un vértice en el gráfico de Cayley de G. Encuentre un algoritmo práctico y eficaz para determinar un camino desde v hasta el vértice v 0 asociado a la identidad que tiene una longitud igual a la distancia de v a v 0 . [...] Este algoritmo se llama el algoritmo de Dios . –David Joyner [3]

La practicidad se puede entender de diferentes maneras. Así, existen programas informáticos que permiten encontrar la solución óptima para una configuración arbitraria del cubo de Rubik en un tiempo razonable [4] . Al mismo tiempo, una tarea similar para un cubo de 4×4×4 sigue siendo prácticamente irrealizable en este momento [5] [6] [7] . Para algunos acertijos , existe una estrategia que permite, según reglas simples, determinar la solución óptima manualmente, sin la ayuda de una computadora.

Definición alternativa del algoritmo de Dios: no se requiere que el algoritmo encuentre la secuencia completa de movimientos; en cambio, basta con encontrar el primer movimiento de la solución óptima que lo acerque a la meta y lo transfiera a una nueva configuración. Las dos definiciones son equivalentes: volver a aplicar el algoritmo a un nuevo par de configuraciones encuentra nuevamente el movimiento de la solución óptima, lo que hace posible obtener la secuencia completa de movimientos de la solución óptima.

Número de Dios

El número de Dios de un acertijo dado es un número n , tal que hay al menos una configuración del acertijo, cuya solución óptima consiste en n movimientos, y no hay configuración, la longitud de la solución óptima excede n . En otras palabras, el número de Dios es el límite superior mínimo en el conjunto de longitudes de soluciones óptimas para configuraciones de rompecabezas.

El número de Dios para un cubo de Rubik de 3x3x3 es 20: este es el diámetro del gráfico de Cayley del grupo de cubos de Rubik [8] .

En general (para un acertijo de permutación arbitraria), el número de Dios no es igual al diámetro del gráfico de Cayley del grupo del acertijo, sino a la excentricidad del vértice correspondiente al estado "ensamblado" del acertijo.

Ejemplos

• Un cubo de Rubik de 3  ×  3  × 3  siempre se puede resolver en no más de 20 movimientos (contando un giro de cualquiera de las 6 caras de 90 o 180 grados por movimiento). Se conocen configuraciones que requieren al menos 20 movimientos para ensamblarse. Así, el "número de Dios" del cubo de Rubik es 20 [9] .

• Si solo se permiten giros de 90 grados (pero no de 180 grados, que son posibles, pero cuentan como dos movimientos), el "número de Dios" del cubo de Rubik es 26 [10] .

• El Número de Dios de un  dado de 2  ×  2  × 2 es 11 movimientos si un giro de 180° se cuenta como 1 movimiento, o 14 movimientos si un giro de 180° se cuenta como 2 movimientos. Un pequeño número ( 3 674 160 ) de configuraciones del cubo 2  ×  2  ×  2 hizo posible calcular el algoritmo de Dios (en forma de una solución óptima para cada configuración) allá por los años 80 [11] .

• El número de la pirámide del Dios de Meffert es 11 [12] .

• Un cubo de tres colores, cuyos lados opuestos tienen el mismo color. El número de configuraciones de un cubo tricolor es

En marzo-abril de 2012, se descubrió que el número del Dios del cubo de tres colores es 15 FTM , 17 QTM o 14 STM (según la métrica STM , la rotación de cualquier capa intermedia también se considera 1 vuelta ) [13] .

• " Quince " se puede resolver en 80 movimientos "cortos" [14] o 43 "largos" [15] en el peor de los casos (por movimientos "cortos" nos referimos a mover fichas individuales, y por movimientos "largos" - mover filas enteras de 1, 2 o 3 huesos). Para etiquetas generalizadas (con más de 15 mosaicos), el problema de encontrar la solución más corta es NP-completo [16] .

• Para la Torre de Hanoi , el algoritmo de Dios existe para cualquier número de discos, pero con la adición de discos, el número de movimientos crece exponencialmente [17] .

Véase también

• Algoritmo del fin del mundo
• Diámetro gráfico
• matemáticas del cubo de rubik

Notas

1. ↑ Historia del Cubo de Rubik (enlace inaccesible) . Consultado el 20 de julio de 2013. Archivado desde el original el 4 de septiembre de 2013. (indefinido) 
2. ↑ Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. El cubo: la guía definitiva para el rompecabezas más vendido del mundo: secretos, historias, soluciones . - 2009. - S. 26. - 142 p. - ISBN 978-1-57912-805-0 .
3. ↑ David Joyner. Aventuras en la teoría de grupos: el cubo de Rubik, la máquina de Merlín y otros juguetes matemáticos . - 2008. - S. 149. - 328 p.  (enlace no disponible)
4. ↑ Herbert Kociemba. Explorador de cubos . Consultado el 27 de julio de 2013. Archivado desde el original el 4 de septiembre de 2013. (indefinido)
5. ↑ Bigger rubik cube binded Archivado el 29 de mayo de 2014.
6. ↑ ¿Generador de algoritmos 4x4x4? (como el explorador de cubos) . Consultado el 26 de julio de 2013. Archivado desde el original el 29 de mayo de 2014. (indefinido)
7. ↑ Algoritmos 4x4 (enlace inaccesible) . Consultado el 26 de julio de 2013. Archivado desde el original el 29 de mayo de 2014. (indefinido) 
8. ↑ Weisstein, Eric W. Número de Dios . Consultado el 4 de mayo de 2020. Archivado desde el original el 21 de febrero de 2020. (indefinido)
9. ↑ Rokicki, T.; Kociemba, H.; Davidson, M.; y Dethridge, J. El número de Dios es 20 . Fecha de acceso: 19 de julio de 2013. Archivado desde el original el 26 de julio de 2013.  
10. ↑ Rokicki, T. y Davidson, M. El número de Dios es 26 en la métrica de cuarto de vuelta  . Consultado el 2 de julio de 2015. Archivado desde el original el 7 de julio de 2015.
11. ↑ Jaap Scherphuis. Mini Cube, el Cubo de Rubik 2×2×2 . Consultado el 21 de julio de 2013. Archivado desde el original el 4 de septiembre de 2013.  
12. ↑ Jaap Scherphuis. Pyraminx (inglés) . Consultado el 21 de julio de 2013. Archivado desde el original el 29 de agosto de 2013.  
13. ↑ Algunos resultados de cubos de 3 colores . Foro del Dominio del Cubo. Consultado el 29 de julio de 2013. Archivado desde el original el 4 de septiembre de 2013. (indefinido)
14. ↑ A. Brüngger, A. Marzetta, K. Fukuda y J. Nievergelt, El banco de búsqueda paralelo ZRAM y sus aplicaciones Archivado el 11 de noviembre de 2017 en Wayback Machine , Annals of Operations Research 90 (1999), págs. 45-63.
15. ↑ Bruce Norskog. El Quince Puzzle se puede resolver en 43 "movimientos" . Foro Dominio del Cubo (inglés) (12 de agosto de 2010) . Consultado el 20 de julio de 2013. Archivado desde el original el 4 de septiembre de 2013.  
16. ↑ Daniel Ratner, Manfred K. Warmuth (1986). "Encontrar una solución más corta para la extensión N × N del rompecabezas de 15 es intratable" . Archivado el 9 de marzo de 2012 en Wayback Machine . en Actas AAAI-86 . Congreso Nacional de Inteligencia Artificial, 1986. pp. 168-172.
17. ↑ Carlos Rueda, "Una solución óptima al rompecabezas de las Torres de Hanoi" .

Enlaces

• Cubo de Rubik: Asalto a la fortaleza (Konstantin Knop)

Speedcubing
Organización	Asociación Mundial de Speedcubing
Equipo deportivo	Cubo 2x2x2 Cubo 3x3x3 Cubo 4x4x4 Cubo 5x5x5 Cubo 6x6x6 Cubo 7x7x7 Pirámide Megaminx escafandra autónoma Cuadrado-1 reloj de rubik
Conceptos	alfombrilla Lucha algoritmo de dios Intento fallido Resolver un cubo de Rubik con una mano Construyendo un cubo de Rubik con tus pies Cubo de Rubik ciego Montaje de un cubo de Rubik para el número de movimientos Disciplinas no oficiales de speedcubing
Campeonatos mundiales	mil novecientos ochenta y dos 2003 2005 2007 2009 2011 2013 2015 2017 2019 2021