Hace algunos años leí un libro de inteligencia artificial, desde entonces me di a la tarea de resolver el rompecabezas de 8 piezas mediante el Algoritmo A*. Este algoritmo resuelve el problema por búsqueda exhaustiva en un árbol de juego, un árbol que contiene todos los escenarios posibles del juego.
Se utiliza una función de evaluación estática F formada por:
F = g + h
La función g es una función que representa el costo de llegar del estado inicial al estado evaluado.
La función h es una estimación del costo de llegar desde el estado evaluado al estado final u objetivo. Para este juego h corresponde al número de piezas que no están en la posición correcta en relación al estado final.
En cada paso, el algoritmo selecciona el mejor nodo que no se ha expandido hasta el momento, es decir, aquel que tiene el menor valor de funcion F. Este nodo se agrega a una lista de nodos explorados y sus nodos sucesores o hijos se agregan a la lista de nodos pendentes de ser explorados
En nuestro ejemplo, se expande el nodo inicial con 2 sucesores que se agregan a la lista de nodos pendientes de ser explorados. Según la funcion heurística, el mejor nodo es el de la derecha con un valor de 2 (g=1 y h=1). Este nodo se toma y se generan sus sucesores que se agregan a la lista de pendientes, entre ellos se encuentra la solución con un valor de h=0 y g=2 que es el mejor nodo.
El codigo presentado es mas claro que mi explicación...
http://rapidshare.com/files/294439459/codigo_puzzle_java.zip.html
No hay comentarios:
Publicar un comentario