utiliza solucion sirve redes que para flujo etiquetas diagrama cual aplicaciones algoritmo artificial-intelligence graph-theory dijkstra a-star

artificial intelligence - solucion - ¿Cómo resuelves el 15-puzzle con A-Star o el Algoritmo de Dijkstra?



dijkstra redes (8)

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

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

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

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

En tu caso, las hojas de cada nodo serán la posición del juego después de realizar uno de los movimientos disponibles en el nodo actual.

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.

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 .

Recuerde que A * buscará a través del espacio problemático procediendo por el camino más probable al objetivo según lo define su heurético.

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 para su problema.

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 así como la Distancia Mahattan del tablero para derivar un camino más corto desde el inicio configuración a la solución.

Un problema con este enfoque es que para cualquier placa nxn donde n > 3 el espacio de juego se vuelve tan grande que no está 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 trayectorias se vuelve inviable desde el punto de vista computacional.

Este artículo de Ian Parberry Un algoritmo en tiempo real para el (n^2 − 1) - Puzzle describe un algoritmo codicioso simple que llega a una solución de manera ineficiente al completar 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 óptima; 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 segundos . Sin embargo, ¡esta hazaña de Jiri es algo sobrehumana!

El método que Parberry describe mueve solo un mosaico 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 del camino desde n^3 , pero reduciría el coeficiente del término principal.