El Algoritmo de Dios

Algoritmo de Dios es un concepto originario de las discusiones sobre maneras de resolver el cubo de Rubik rompecabezas, pero que también se puede aplicar a otras combinatorias rompecabezas y juegos matemáticos . Se refiere a cualquier algoritmo que produce una solución con el menor número posible de movimientos, con la idea de que un omnisciente sabría ser un paso óptimo de cualquier configuración dada.
El concepto se aplica a los enigmas que pueden asumir un finito número de "configuraciones", con un relativamente pequeño arsenal, bien definido de "movimientos" que pueden ser aplicables a las configuraciones y luego condujo a una nueva configuración. Resolviendo el rompecabezas significa para llegar a una "configuración final" específico designado (o una de una colección de configuraciones finales) mediante la aplicación de una secuencia de movimientos, a partir de una cierta configuración inicial arbitraria. Algunos puzzles conocidas encajan esta descripción son los rompecabezas mecánicos , como el Cubo de Rubik , Torres de Hanoi , y el rompecabezas de 15 . El juego de una sola persona de peg solitaire también está cubierto, así como muchos puzzles de lógica , como los misioneros y caníbales problema . Estos tienen en común que pueden ser modeladas matemáticamente como un grafo dirigido , en los que las configuraciones son los vértices y los movimientos de los arcos. Un algoritmo puede ser considerado para resolver un enigma si se 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 es resoluble a partir de que la configuración inicial, de lo contrario, apunta a la imposibilidad de un solución). Una solución es óptima si la secuencia de movimientos es tan corto como sea posible. Algoritmo de Dios, entonces, para un rompecabezas dado, es un algoritmo que resuelve el enigma y sólo produce soluciones óptimas. Algunos escritores, tales como David Joyner, consideran que para un algoritmo que se refiere correctamente como "algoritmo de Dios", sino que también debe ser práctica , lo que significa que el algoritmo no requiere cantidades extraordinarias de la memoria o el tiempo. Por ejemplo, el uso de un gigante tabla de consulta indexada por configuraciones iniciales permitiría soluciones que se pueden encontrar muy rápidamente, pero requeriría una cantidad extraordinaria de la memoria.

Scramble	Scramble
Solve	Solve