Tema

Búsqueda A estrella

IA clásica
Nivel intermedio
Con simulador interactivo

La búsqueda A estrella expande siempre el nodo de menor f(n) = g(n) + h(n), donde g(n) es el coste real acumulado desde el inicio y h(n) es una estimación del coste que falta hasta la meta.

Nombre en inglés

A star search

Intuición

Conviene pensar en g como lo que ya se pagó y en h como el presupuesto de lo que queda. La suma ordena la frontera por el coste total previsto del camino que pasa por ese nodo, de modo que el algoritmo estira la mancha de búsqueda hacia la meta en lugar de extenderla en círculos. Con h igual a cero el método degenera en coste uniforme, y con h perfecta camina en línea recta hasta la meta sin expandir nada de más.

Fórmula

f(n) = g(n) + h(n),  con h(n) <= h*(n) para que la solución sea óptima

Ejemplo resuelto

En una rejilla de 4 por 4 con movimientos de coste 1 en las cuatro direcciones, el inicio está en (0, 0) y la meta en (3, 3), con la heurística de Manhattan h(x, y) = (3 - x) + (3 - y). El inicio tiene f = 0 + 6 = 6. Sus vecinos (1, 0) y (0, 1) tienen g = 1 y h = 5, luego f = 6 en ambos. Cualquier nodo que se aleje de la meta, por ejemplo volver a (0, 0) desde (1, 0), daría g = 2 y h = 6, o sea f = 8, y queda al final de la cola. Mientras exista un camino sin obstáculos, todos los nodos de la diagonal mantienen f = 6 y A estrella recorre el camino directo expandiendo 7 nodos.

Errores frecuentes

Usar una heurística que sobreestima el coste restante y esperar optimalidad, ya que basta con inflar h en un solo nodo para que A estrella devuelva un camino peor y ni siquiera avise.
Cerrar un nodo para siempre cuando la heurística es admisible pero no consistente, porque en ese caso puede aparecer después un camino más barato hacia el mismo estado y hay que permitir la reapertura.
Comparar nodos por h en lugar de por f, error que convierte el método en búsqueda voraz por el mejor primero, rápida pero sin ninguna garantía de coste.

Ejercicio

Tres nodos están en la frontera con estos valores. El nodo P tiene g = 4 y h = 3, el nodo Q tiene g = 2 y h = 6 y el nodo R tiene g = 6 y h = 0. Indica cuál se expande primero y cuál queda para el final.

Ver la solución

Se calcula f en cada nodo. En P la suma es 4 + 3 = 7, en Q es 2 + 6 = 8 y en R es 6 + 0 = 6. A estrella expande el menor, que es R con f igual a 6, y deja para el final a Q con f igual a 8. Conviene notar que R ya está en la meta si su h vale cero y la heurística es admisible, de modo que su camino de coste 6 es óptimo.