Busqueda a*

Algoritmo A*

Usaremos dos listas de nodos (ABIERTA Y CERRADA)
_ Abierta: nodos que se han generado y a los que se les ha aplicado la función heurística, pero que aún no han sido examinados (esdecir, no se han generado sus sucesores)
_ Es decir, es una cola con prioridad en la que los elementos con mayor prioridad son aquellos que tienen un valor más prometedor de la función heurística.
_Cerrada: nodos que ya se han examinado. Es necesaria para ver si cuando se genera un nuevo nodo ya ha sido generado con anterioridad.

Definiremos una función heurística f como la suma de dosfunciones g y h:
_ Función g: es una medida del coste para ir desde el estado inicial hasta el nodo actual (suma de los costes o valores heurísticos de todos los nodos).
_ Función h: es una estimación delcoste adicional necesario para alcanzar un nodo objetivo a partir del nodo actual, es decir, es una estimación de lo que me queda por recorrer hasta la meta.
_ La función combinada f una estimacióndel coste necesario para alcanzar un estado objetivo por el camino que se ha seguido para generar el nodo actual (si se puede generar por varios caminos el algoritmo se queda con el mejor).
_ NOTA:los nodos buenos deben poseer valores bajos.

En cada paso se selecciona el nodo más prometedor que se haya generado hasta ese momento (función heurística).
_ A continuación se expande el nodoelegido generando todos sus sucesores.
_ Si alguna de ellos es meta el proceso acaba. Si no continúo con el algoritmo.
_ Es parecido a la búsqueda en profundidad, pero si en una rama por la que estoyexplorando no aparece la solución la rama puede parecer menos prometedora que otras por encima de ella y que se habían ignorado. Podemos pues abandonar la
rama anterior y explorar la nueva.
_ Sinembargo al vieja rama no se olvida. Su último nodo se almacena en el conjunto de nodos generados pero aún sin expandir.

1. Empezar con ABIERTA conteniendo sólo el nodo inicial. Poner el valor g de ese...