IMPLEMENTACIÓN DEL  ALGORITMO A*  EN 8‐PUZZLE Y 8‐REINA 

Trabajo realizado por: Alonso García, Rubén Sanz Fernández, Rafael

1. INTRODUCCIÓN 1.1. Introducción a los algoritmos de búsqueda informada y exploración Los algoritmos de búsqueda informada son más eficientes que los algoritmos de búsqueda no informada, debido a que éstos últimos pueden encontrar soluciones a problemas generando sistemáticamente nuevos estados y probándolos con el objetivo. Los algoritmos de búsqueda informada son muy útiles en problemas donde lo que importa es el estado de solución en sí mismo, no el camino. Utilizan métodos inspirados en la física estadística (temple simulado) y la biología evolutiva (algoritmos genéticos). Un primer contacto con éstos algoritmos es el siguiente: “búsqueda primero el mejor”, que es un caso particular del algoritmo general de “búsqueda de árboles” o “búsqueda de grafos”, en el cuál se selecciona un nodo para la expansión basada en una función de evaluación, f(n). La evaluación mide la distancia al objetivo. Otro algoritmo importante es el “búsqueda voraz primero el mejor” que expande el nodo más cercano al objetivo. Evalúa los nodos utilizando solamente la función heurística: f(n) = h(n) En nuestro trabajo nos centraremos en la búsqueda A* y sus variantes.

2. CARACTERIZACIÓN DEL ALGORITMO A*. Un algoritmo de búsqueda por el mejor nodo combina las características de los métodos en anchura y en profundidad. Se caracteriza porque para cada nodo se generan todos los posibles sucesores y de estos sólo se expande aquel que sea más prometedor después de la aplicación sobre ellos de una función heurística h(n) que estima el coste del camino desde cada nodo al objetivo. El uso de este tipo de algoritmo, al minimizar el coste estimado hasta el objetivo, disminuye considerablemente el coste de la búsqueda. Desafortunadamente, no es ni óptimo ni completo. Por otra parte, la búsqueda de coste uniforme minimiza el coste del camino hasta el nodo, g(n) , es decir, expande para cada conjunto de sucesores aquel cuyo camino desde el nodo raíz tenga un menor coste. Este es un algoritmo óptimo y completo, pero puede ser muy ineficiente. Sería bueno poder combinar estas dos estrategias para conseguir las ventajas de ambos. Afortunadamente, podemos hacer eso exactamente, combinando las dos funciones de evaluación simplemente sumándolas: f(n) = g(n) + h(n).

Ya que g(n) proporciona el coste del camino desde el nodo de inicio hasta el nodo n, y h(n) es el coste estimado del camino de menos coste desde n hasta el objetivo, f(n) es el coste estimado de la solución de menor coste que atraviesa el nodo n. Si se intenta encontrar la solución de menor coste, es razonable intentar primero el nodo con el menor valor de f. Lo bueno de esta estrategia, es que es más que razonable. Se puede comprobar que es completa y óptima, dando una simple restricción de la función h. La restricción es escoger una función h que nunca sobreestime el coste para alcanzar el objetivo. Una función h de este tipo es una heurística admisible. A este algoritmo se le conoce con el nombre de A*. Los algoritmos de búsqueda heurística tradicionales como A* pueden llegar a necesitar un espacio de almacenamiento que crece de manera exponencial con la longitud de la solución del problema. Esto puede propiciar que, a pesar de que el problema tenga un coste temporal relativamente asequible, el coste espacial lo convierta en un problema intratable. 2.1. Optimalidad de A* Definir f* - el costo de la solución óptima para la ruta ¾ A* expande todos los nodos con f(n)