Tema 2 · Heurísticas

A* paso a paso

Dos formatos, el mismo algoritmo: tablero (rejilla con muros, con dos modos de movimiento: Simple (4 direcciones) y Con diagonales (8 direcciones), con coste diagonal de 1,4) y grafo (nodos con nombre, aristas con coste explícito y heurísticas h(n) por nodo). Cambia la vista y el modo de movimiento para ver el mismo A* en el contexto en el que caiga en el examen. Verás con detalle los cambios de padre cuando A* descubre un camino mejor hacia un nodo ya en la Frontera.

Vista:

Edición:

Movimiento:

Heurística usada por A*:

Vista previa en casillas libres:

Origen / camino Destino Muro Expandiendo Interior Frontera

1 / 1

Paso

Frontera

Interior

Qué ha pasado en este paso

Qué recordar de A*

g(n) = coste real acumulado desde el origen hasta n. En el tablero es el número de pasos (coste 1 por movimiento); en el grafo es la suma de los costes de las aristas del camino elegido.
h(n) = estimación del coste desde n hasta el destino. En el tablero se calcula (Manhattan o Euclídea); en el grafo viene dada por una tabla fija h(A), h(B), ....
f(n) = g(n) + h(n) = coste total estimado del mejor camino que pase por n.
En cada paso se saca de la Frontera el nodo con menor f. Se marca como interior (cerrado). Sus vecinos se generan y se comparan con lo que ya sabíamos: si el nuevo camino es mejor, se actualiza el nodo en la Frontera y se cambia su puntero de padre al que ha ofrecido el camino más barato. Cuando el destino sale de la Frontera se reconstruye el camino óptimo siguiendo esos punteros de padres hacia atrás.

Los cambios de padre, en detalle

Un cambio de padre ocurre cuando A*, al expandir el nodo actual u, descubre un vecino v con un g'(v) = g(u) + coste(u, v) mejor que el g(v) con el que estaba ya en la Frontera. Entonces:

Se elimina la entrada anterior de v en la Frontera.
Se inserta la nueva con g'(v), f'(v) = g'(v) + h(v) y padre = u.
El camino final se reconstruye siguiendo los padres actualizados, así que un cambio de padre en mitad de la búsqueda puede alterar el trazado del camino final.

Si h es consistente (monótona), un nodo nunca vuelve a mejorar una vez cerrado, así que sólo hay que mirar los que están todavía en la Frontera. Si h es solamente admisible (nunca sobreestima) pero no consistente, en teoría podría ser necesario reabrir un nodo cerrado; en esta asignatura solemos usar heurísticas consistentes, así que basta con actualizar los nodos abiertos.

Movimiento: Simple vs Con diagonales

Simple (4 direcciones): sólo N, S, E, O. Cada paso cuesta 1. Es el formato clásico del A* del tema.
Con diagonales (8 direcciones): se añaden las 4 diagonales. El coste de cada paso es 1 si es ortogonal y 1,4 si es diagonal (aproximación habitual de √2 en el examen).
g(n) deja de ser un simple contador de pasos: es la suma de 1 por cada movimiento ortogonal más 1,4 por cada movimiento diagonal del camino desde el origen.

La heurística h(n) se calcula siempre sobre las coordenadas y no cambia con el modo de movimiento; sólo cambia lo que suma g(n) con cada paso.

Manhattan vs Euclídea (modo tablero)

Manhattan: h = |Δfila| + |Δcolumna|. Es la distancia real cuando sólo se puede mover en horizontal y vertical con coste 1. Admisible y consistente en modo Simple. En modo Con diagonales puede llegar a sobreestimar (perdiendo la admisibilidad estricta), pero es la formulación que suele pedirse en el examen.
Euclídea: h = √(Δfila² + Δcolumna²). Es la distancia en línea recta. En modo Simple subestima más que Manhattan y hace que A* expanda más nodos. En modo Con diagonales sigue siendo admisible.
Cambia la heurística usada por A* arriba y el modo de movimiento para ver cómo cambia el número de nodos en el Interior y el coste g del camino.
La vista previa es independiente de la heurística usada por el algoritmo: te permite ver el valor de una u otra en cada casilla, aunque la simulación esté usando la contraria.

Regla práctica: si los movimientos son en 4 direcciones con coste igual → Manhattan. Si son en 8 direcciones o hay diagonales con coste √2 → Euclídea (o Chebyshev / Octile en otros contextos). Si el movimiento es continuo (no en rejilla) → Euclídea.

A* en grafo: cómo leerlo en un examen

En un ejercicio de examen te suelen dar el grafo dibujado, los costes en cada arista y una tabla con h(n) para cada nodo. Origen y destino se indican en el enunciado.
La ejecución es idéntica al tablero: mantén una tabla con Frontera (abiertos, ordenada por f) e Interior (cerrados). En cada iteración expande el nodo con menor f, y para cada vecino aplica la comparación de g descrita arriba.
Un truco: escribe cada nodo generado como [nodo, g, h, f, padre] y ve tachando/reescribiendo cuando cambien los valores por un mejor camino. Al final, recorriendo los padres hacia atrás desde el destino sale el camino óptimo.
El coste total del camino óptimo coincide con el g del destino cuando lo sacas de la Frontera (y con f, porque h(destino) = 0).

Prueba en el simulador: elige distintos pares origen/destino y verás cómo cambia el orden de expansión y qué nodos sufren cambios de padre en la Frontera.