Tema 2 · Heurísticas

IDA* en modo tablero

IDA* = A* + búsqueda en profundidad con corte. Se hacen sucesivas exploraciones DFS priorizando el hijo con menor f; cuando un nodo n tiene f(n) > Corte se poda y se retrocede. Si la iteración termina sin llegar al destino, se sube el Corte al menor f que lo había superado, y se repite. Consume mucho menos que A* porque en memoria sólo lleva el camino actual (pila DFS), no una Frontera completa.

Escenario:

Edición:

Heurística:

Redondeo del corte:

Origen / camino final Destino Muro Nodo actual (DFS) Camino DFS actual Podado por f > Corte

Iteración

Corte actual

Próximo corte

Profundidad DFS

Qué ha pasado en este paso

Pila DFS actual de la raíz al nodo actual

#	Celda	g	h	f

Cómo funciona IDA* en modo tablero (los 5 pasos)

Corte inicial = f(nodo inicial) = 0 + h(inicial). En el tablero, si usamos Euclídea, es la distancia en línea recta origen → destino.
Haces una búsqueda en profundidad (DFS) desde el origen priorizando el hijo con menor f disponible.
Cuando alcanzas un nodo n con f(n) > Corte → retrocedes (poda). Ese nodo no entra en el camino de esta iteración.
Cuando la profundización termina sin haber llegado al destino, se incrementa el Corte al menor f que había superado al corte anterior.
En simuladores como Pathdemo se redondea al siguiente entero por precisión numérica. En este simulador tienes el botón Al siguiente entero (Pathdemo) / Exacto arriba para elegir la política.
Se repite con el nuevo Corte hasta llegar al destino (o hasta que la próxima frontera sea ∞, señal de que no hay camino).

Ejemplo intuitivo (implementado en este simulador)

Imagina un tablero donde la distancia euclídea del origen al destino es 5 pero hay un obstáculo por medio que obliga a rodearlo. Al pulsar el pill "Ejemplo del Word" arriba se carga exactamente ese caso con origen (2,0), destino (2,5) y un muro en (2,3).

Iteración 1: Corte = 5. Bajas por la línea recta ((2,0) → (2,1) → (2,2)); todos esos nodos tienen f = 5. En cuanto intentas rodear el muro, cualquier nodo tiene f > 5 (por ejemplo (1,2) con f ≈ 6,16) → poda y retroceso hasta agotar la iteración.
Iteración 2: Corte = 7 (el mínimo f podado era ≈ 6,10, redondeado al siguiente entero da 7 en modo Pathdemo). Ahora todos los nodos del rodeo (f entre 6 y 7) pasan el corte y se llega al destino con coste 7.

En el material del Word el ejemplo usa números redondos (5 → 5,04 → 5,21 → 6) para ilustrar; la mecánica es exactamente la misma. Lo esencial: si el corte no basta, se sube al menor f que había superado el corte y se repite.

IDA* vs A*: qué recordar

Memoria: A* mantiene toda la Frontera. IDA* sólo mantiene el camino actual (la pila DFS), así que consume mucho menos. Por eso se usa cuando el espacio de estados es enorme.
Optimalidad: con la misma heurística admisible, IDA* devuelve el mismo camino óptimo que A*.
Trabajo repetido: IDA* re-explora nodos en cada iteración con el corte incrementado. En dominios donde la heurística está bien informada este trabajo repetido es despreciable respecto al ahorro de memoria.
Frontera vs Pila: en A* la Frontera está ordenada por f; en IDA* no hay Frontera explícita, la ordenación se hace a la hora de elegir hijo dentro de la DFS.