Algoritmos

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úsquedainformada 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 generandosistemá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 elmejor”, 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). Laevaluació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ónheurí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 lascaracterí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 laaplicació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...