¿Cómo resuelves el 15-puzzle con A-Star o el algoritmo de Dijkstra?

Question

He leído en uno de mis libros de AI que los algoritmos populares (A-Star, Dijkstra) para buscar rutas en simulación o juegos también se usan para resolver el conocido "15-puzzle".

¿Alguien puede darme algunos consejos sobre cómo reduciría el 15-puzzle a un gráfico de nodos y bordes para poder aplicar uno de estos algoritmos?

Si tuviera que tratar cada nodo del gráfico como un estado de juego, ¿no sería ese árbol demasiado grande? ¿O es solo la manera de hacerlo?

Answer 1

Solo usa el árbol de juego. Recuerde que un árbol es una forma especial de gráfico.

En su caso, las hojas de cada nodo serán la posición del juego después de hacer uno de los movimientos que está disponible en el nodo actual.

Answer 2

Una rápida búsqueda en Google se convierte en imagen un par de documentos que cubren esta con cierto detalle: uno en Parallel Combinatorial Search, y uno en External-Memory Graph Search

Regla general cuando se trata de problemas algorítmicos: una persona que probablemente ha hecho antes usted, y publicó sus hallazgos.

Answer 3

También. tenga en cuenta que con el algoritmo A-Star, al menos, tendrá que descubrir una heurística admisible para determinar si un posible siguiente paso está más cerca de la ruta finalizada que otro paso.

Answer 4

Una buena heurística para A-Star con el rompecabezas 15 es el número de cuadrados que están en la ubicación incorrecta. Como necesita al menos 1 movimiento por cuadrado que está fuera de lugar, se garantiza que el número de cuadrados fuera de lugar será menor o igual al número de movimientos necesarios para resolver el rompecabezas, lo que lo convierte en una heurística apropiada para A-Star .

Answer 5

Aquí tiene http://www.heyes-jones.com/astar.html

Answer 6

Esta es una asignación para el problema 8-rompecabezas hablado sobre el uso del algoritmo A * con cierto detalle, pero también bastante sencillo:

http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html

Answer 7

recordar que una * buscará a través del espacio problemático procediendo por el camino más probable a la meta según lo definido por su heurestic.

Solo en el peor de los casos terminará teniendo que inundar todo el espacio del problema, esto tiende a suceder cuando no hay una solución real a su problema.

Answer 8

La forma teórica de los gráficos para resolver el problema es imaginar cada configuración del tablero como un vértice del gráfico y luego usar una búsqueda inicial con poda basada en algo como la Distancia Mahattan del tablero para derivar el más corto camino desde la configuración inicial hasta la solución.

Un problema con este enfoque es que para cualquier placa n x n donde n > 3 el espacio de juego sea tan grande que no queda claro cómo se pueden marcar eficientemente los vértices visitados. En otras palabras, no hay una manera obvia de evaluar si la configuración actual de la placa es idéntica a una que se haya descubierto anteriormente al atravesar alguna otra ruta. Otro problema es que el tamaño del gráfico crece tan rápido con n (es aproximadamente (n^2)!) que simplemente no es adecuado para un ataque de fuerza bruta ya que el número de rutas se vuelve inviable desde el punto de vista computacional.

Este artículo de Ian Parberry A Real-Time Algorithm for the (n^2 − 1) - Puzzle describe un algoritmo codicioso que llega a una solución completando la primera fila, luego la primera columna, luego la segunda fila ... Llega a una solución casi de inmediato, sin embargo, la solución está lejos de ser óptimo; esencialmente resuelve el problema como lo haría un ser humano sin aprovechar ningún músculo computacional.

Este problema está estrechamente relacionado con el de resolver el cubo de Rubik. La gráfica de todos los juegos es demasiado grande para ser resuelta por la fuerza bruta, pero hay un método bastante simple de 7 pasos que puede ser usado para resolver cualquier cubo en aproximadamente 1 ~ 2 minutos por un humano diestro. Esta ruta es, por supuesto, no óptima. Al aprender a reconocer patrones que definen secuencias de movimientos, la velocidad puede reducirse a 17 seconds. Sin embargo, ¡esta hazaña de Jiri es algo sobrehumana!

El método que Parberry describe mueve solo una ficha a la vez; uno imagina que el algoritmo podría mejorarse empleando la destreza de Jiri y moviendo varias fichas al mismo tiempo. Esto no sería, como lo demuestra Parberry, reducir la longitud de la ruta desde n^3, pero reduciría el coeficiente del término principal.