El algoritmo de Dios es una noción que se origina en discusiones sobre formas de resolver el rompecabezas del cubo de Rubik , [1] pero que también se puede aplicar a otros rompecabezas combinatorios y juegos matemáticos . [2] Se refiere a cualquier algoritmo que produce una solución con la menor cantidad de movimientos posibles, la idea es que solo un ser omnisciente conocería un paso óptimo de cualquier configuración dada.
La noción se aplica a los rompecabezas que pueden asumir un número finito de "configuraciones", con un arsenal relativamente pequeño y bien definido de "movimientos" que pueden ser aplicables a configuraciones y luego conducir a una nueva configuración. Resolver el rompecabezas significa llegar a una "configuración final" designada, una configuración singular o una de una colección de configuraciones. Para resolver el rompecabezas se aplica una secuencia de movimientos, partiendo de alguna configuración inicial arbitraria.
Se puede considerar que un algoritmo resuelve un rompecabezas de este tipo si toma como entrada una configuración inicial arbitraria y produce como salida una secuencia de movimientos que conducen a una configuración final ( si el rompecabezas se puede resolver a partir de esa configuración inicial, de lo contrario, indica la imposibilidad de una configuración inicial ). solución). Una solución es óptima si la secuencia de movimientos es lo más corta posible. Este recuento se conoce como el número de Dios , [3] o, más formalmente, el valor minimax . [4] El algoritmo de Dios, entonces, para un rompecabezas dado, es un algoritmo que resuelve el rompecabezas y produce solo soluciones óptimas.
Algunos escritores, como David Joyner, consideran que para que un algoritmo se denomine correctamente "algoritmo de Dios", también debe ser práctico , lo que significa que el algoritmo no requiere cantidades extraordinarias de memoria o tiempo. Por ejemplo, el uso de una tabla de búsqueda gigante indexada por configuraciones iniciales permitiría encontrar soluciones muy rápidamente, pero requeriría una cantidad extraordinaria de memoria. [5]
En lugar de pedir una solución completa, se puede pedir de manera equivalente un solo movimiento de una configuración inicial pero no final, donde el movimiento es el primero de alguna solución óptima. Un algoritmo para la versión de un solo movimiento del problema se puede convertir en un algoritmo para el problema original invocándolo repetidamente mientras se aplica cada movimiento informado a la configuración actual, hasta que se alcanza uno final. Por el contrario, cualquier algoritmo para el problema original se puede convertir en un algoritmo para la versión de un solo movimiento truncando su salida a su primer movimiento.
Los acertijos más conocidos que se ajustan a esta descripción son los acertijos mecánicos como el Cubo de Rubik , las Torres de Hanoi y el 15 . También se cubre el juego para una persona del solitario peg , así como muchos acertijos de lógica , como el problema de los misioneros y caníbales . Estos tienen en común que se pueden modelar matemáticamente como un grafo dirigido , en el que las configuraciones son los vértices y los movimientos los arcos.