Las dos lecciones anteriores buscaban y ordenaban valores en colecciones. Esta lección cierra el módulo con una búsqueda de otra naturaleza: encontrar una secuencia de decisiones que lleve de una situación inicial a un objetivo — la ruta de una furgoneta de Rutalia por una cuadrícula con calles cortadas, la planificación de un reparto con restricciones. El marco formal se llama espacio de estados, y es el punto donde confluyen varias ideas que ya tienes: los grafos implícitos de 03-01, el BFS/DFS de 03-02, el Dijkstra de 03-03 y los árboles de exploración del backtracking de 02-03. Aquí les daremos un techo común y añadiremos la pieza prometida desde el módulo 3: A*, el "Dijkstra con brújula", que usa una heurística para expandir muchísimos menos nodos. Compararemos experimentalmente Dijkstra contra A* y aclararemos el mapa mental completo de técnicas de exploración del curso.

1. Qué es un espacio de estados: estado, operadores, objetivo, coste
2. Espacios de estados vs. grafos explícitos: lo implícito y lo gigante
3. BFS y DFS sobre espacios implícitos: la cuadrícula de 01-03 revisitada
4. Búsqueda de coste uniforme: Dijkstra sin grafo
5. A*: heurísticas, admisibilidad y consistencia
6. Implementación completa: ruta de reparto en cuadrícula con obstáculos
7. Comparación experimental: nodos expandidos con y sin brújula
8. Heurísticas no admisibles, A* ponderado e IDA* (breve)
9. El mapa mental: búsqueda de caminos vs. optimización exacta (02-03)

Un espacio de estados es una forma de plantear un problema como exploración. Se define con cuatro piezas:

Una solución es un camino de operadores del estado inicial a un estado objetivo; una solución óptima es la de coste mínimo. Fíjate en que el estado puede ser mucho más rico que una posición: si la furgoneta debe recoger y entregar, el estado podría ser (posición, paquetes_a_bordo); si hay ventanas horarias, (posición, tiempo). Elegir qué información entra en el estado es la decisión de diseño más importante: todo lo que afecte a los movimientos futuros debe estar dentro; todo lo que no, fuera (o el espacio explota sin necesidad).

Un espacio de estados es un grafo: los estados son vértices y los operadores, aristas ponderadas. Entonces, ¿qué hay de nuevo respecto al módulo 3? La diferencia es de representación y de escala, y ya la anticipamos en 03-01 al hablar de grafos implícitos:

• Grafo explícito (la red de 9 zonas de Rutalia): cabe entero en memoria como lista de adyacencia; podemos iterarlo, precalcular Floyd-Warshall 9×9, dibujarlo.
• Grafo implícito (un espacio de estados): solo existe la función sucesores(estado). El grafo completo puede tener 10²⁰ estados — nunca lo materializaremos. Lo único que podemos hacer es generarlo sobre la marcha a partir del estado inicial, y la pregunta central pasa a ser: ¿cuántos estados necesitamos tocar antes de encontrar el objetivo?

Esa pregunta — nodos generados y expandidos, no vértices totales — es la métrica de esta lección. Con un factor de ramificación b (sucesores por estado) y una solución a profundidad d, una exploración ciega toca del orden de b^d estados. Todo lo que sigue es la lucha por reducir ese número.

Los algoritmos de 03-02 funcionan sin cambios: nunca exigieron tener el grafo entero, solo pedir vecinos. La cuadrícula del coste mínimo de 01-03 — que en 03-01 ya reconocimos como un grafo — es nuestro espacio de estados de juguete: la resolvimos con programación dinámica porque solo se podía ir a la derecha y abajo; ahora la furgoneta se mueve en las cuatro direcciones y hay obstáculos, así que la PD por barrido ya no aplica y toca buscar.

Observa la firma: bfs_estados no recibe un grafo, recibe funciones (es_objetivo, sucesores_fn). Ese es el cambio de mentalidad de la lección — el algoritmo es el mismo de 03-02.

Sobre cuándo usar cada exploración ciega:

El conjunto de visitados (padre hace ese doble papel) merece énfasis: en un espacio de estados los caminos se cruzan constantemente (a la casilla (3, 4) se llega por miles de rutas). Sin visitados, el mismo estado se re-explora una y otra vez y el coste pasa de b^d a mucho peor. La excepción es cuando el espacio es un árbol de verdad — como en el backtracking de 02-03, donde cada nodo tenía un único camino desde la raíz; volveremos sobre esta distinción al final.

Si los operadores tienen costes distintos (cruzar una avenida congestionada cuesta 3 minutos; una calle vacía, 1), BFS deja de ser óptimo: minimiza pasos, no coste. La solución ya la conoces de 03-03: expandir siempre el estado de menor coste acumulado con un heap. Aplicado a un espacio implícito, el algoritmo se llama búsqueda de coste uniforme (UCS), pero es literalmente Dijkstra con sucesores generados al vuelo — mismo invariante ("lo que sale del heap es definitivo"), mismo borrado perezoso.

No lo implementamos por separado: en el código de A* de la sección siguiente, UCS es el caso particular h = 0. Esa es exactamente la relación entre ambos.

Dijkstra/UCS explora en círculos concéntricos de coste creciente alrededor del inicio: es exhaustivo y ciego, gasta el mismo esfuerzo hacia el objetivo que en dirección contraria. Pero en muchos espacios de estados sabemos algo sobre dónde está el objetivo. Ese algo se formaliza como una heurística:

h(n) = estimación del coste restante desde el estado n hasta el objetivo.

A* ordena el heap no por el coste acumulado g(n), sino por

f(n) = g(n) + h(n) — coste ya pagado + coste estimado pendiente = estimación del coste total pasando por n.

Intuición: entre dos estados con el mismo coste acumulado, A* expande antes el que parece más cerca del objetivo. Es Dijkstra con brújula: la exploración deja de ser un círculo y se convierte en una elipse estirada hacia el objetivo.

Las garantías dependen de la calidad de h:

• Admisibilidad: h nunca sobreestima el coste real restante (h(n) ≤ h*(n) para todo n). Con h admisible, A* encuentra la solución óptima. La intuición de la prueba: si A* fuera a devolver un camino subóptimo, el camino óptimo tendría en la frontera algún estado con f menor (porque su h no sobreestima), y ese estado se habría expandido antes.
• Consistencia (o monotonía): h(n) ≤ coste(n → n') + h(n') para toda arista — una desigualdad triangular. Implica admisibilidad y algo más: los valores f nunca decrecen por un camino, así que la primera vez que un estado sale del heap, su g es definitivo — exactamente el invariante de Dijkstra, que se conserva. Con h consistente basta el mismo conjunto "cerrado" de siempre; con h admisible pero inconsistente, un estado cerrado puede tener que reabrirse.
• Casos extremos que sitúan a A* en el mapa: con h = 0 (admisible y consistente trivialmente), A* es UCS/Dijkstra; con h = h* (la heurística perfecta), A* va directo al objetivo sin expandir nada superfluo. Toda heurística real vive entre ambos: cuanto más "informada" (mayor sin pasarse), menos nodos expande.

Para moverse en cuadrícula con pasos de coste ≥ 1, la heurística canónica es la distancia Manhattan: |f1 − f2| + |c1 − c2|. Es admisible (ningún camino real puede ser más corto que ignorar todos los obstáculos) y consistente (moverse una casilla cambia la estimación en ±1 como mucho, y el paso cuesta al menos 1).

La furgoneta de Rutalia sale del depósito D y debe llegar al cliente C en un barrio en obras (# = calle cortada). Implementamos A* completo, con contador de nodos expandidos para la comparación experimental posterior.

Puntos finos del código, uno a uno:

• La prueba de objetivo se hace al EXTRAER del heap, no al generar el sucesor. Es un error clásico hacerla al generar: podrías encontrar el objetivo por un camino caro mientras uno barato espera en el heap. Al extraer, la consistencia de h garantiza que su g es ya el óptimo (mismo argumento que el invariante de Dijkstra en 03-03).
• g_mejor + borrado perezoso: idéntico patrón que nuestro Dijkstra del módulo 3 — se permiten entradas obsoletas en el heap y se descartan al salir comparando con el mejor g conocido.
• La tupla del heap es (f, g, estado): se ordena por f; incluir g de segundo criterio desempata a favor de estados más avanzados, un detalle práctico que suele reducir expansiones.
• UCS gratis: pasar h = lambda n, obj: 0 convierte la función en Dijkstra implícito, sin tocar nada más. Es la mejor demostración de que A* generaliza a Dijkstra.

Ejecutemos las tres variantes sobre el mismo mapa y contemos expansiones:

Ambos devuelven un camino de la misma longitud — los dos son óptimos —, pero A* expande bastantes menos nodos. En un mapa 10×10 la diferencia es modesta; la brecha crece con el tamaño del espacio: en cuadrículas grandes con obstáculos dispersos, A* con Manhattan expande órdenes de magnitud menos que Dijkstra, porque este último rellena el círculo completo de radio 18 mientras A* excava un pasillo hacia el objetivo. Te propongo el experimento como hábito: siempre que implementes A*, instrumenta el contador de expansiones y compáralo con h = 0. Es la forma honesta de saber cuánto vale tu heurística (y de detectar heurísticas rotas: si A* expande más que Dijkstra, algo va mal — probablemente h no es consistente o está mal escalada).

¿Y si renunciamos a la optimalidad a cambio de velocidad? Si h sobreestima, A* puede devolver caminos subóptimos, pero suele expandir muchos menos nodos. La versión controlada de esta idea es el A* ponderado: usar f(n) = g(n) + w·h(n) con w > 1. Se demuestra que el camino devuelto cuesta como mucho w veces el óptimo — un compromiso explícito y ajustable. Para la furgoneta de Rutalia, un w = 1,2 ("acepto rutas hasta un 20 % más largas") puede reducir el tiempo de planificación drásticamente en mapas grandes; es el mismo espíritu que las metaheurísticas del módulo 2 (02-04, 02-05): cambiar garantía por tiempo, pero aquí con una cota de calidad demostrable.

El otro límite práctico de A* es la memoria: el heap y g_mejor crecen con los nodos generados. IDA* (iterative deepening A*) aplica la idea de la profundización iterativa: DFS con un umbral sobre f que se incrementa en cada pasada. Memoria O(d) manteniendo la optimalidad, a cambio de repetir trabajo. Es el algoritmo clásico para puzzles de espacio gigantesco (el 15-puzzle se resolvió óptimamente con IDA*); lo dejamos en mención.

En 02-03, el backtracking y el branch and bound también exploraban árboles de estados — de hecho el B&B mejor-primero usaba un heap de nodos con cotas optimistas, sospechosamente parecido a A*. Conviene cerrar el curso de exploración con el mapa completo, porque la confusión entre ambas familias es habitual:

Las dos familias comparten el ADN (generar sucesores, priorizar con una estimación optimista, usar un heap) y por eso B&B mejor-primero y A* son casi el mismo algoritmo con distinto propósito. El criterio para elegir: si tu problema es "encontrar el camino/secuencia hasta un objetivo", piensa en A*; si es "encontrar la mejor solución completa entre todas las combinaciones", piensa en B&B. El TSP de Rutalia era lo segundo; guiar la furgoneta por el barrio en obras es lo primero.

• Comprobar el objetivo al generar en vez de al extraer. El bug más frecuente en A*/UCS: devuelve caminos subóptimos de forma intermitente y difícil de reproducir. La prueba de objetivo va cuando el estado sale del heap.
• Heurística que sobreestima "solo un poco". Usar la distancia euclídea ×1,5, o Manhattan cuando se permite movimiento diagonal (ahí Manhattan sobreestima y la admisible es la distancia de Chebyshev o la octil). Adiós optimalidad, y de forma silenciosa: el camino devuelto parece razonable. Justifica siempre por qué h no puede superar el coste real.
• Olvidar el conjunto de visitados/g_mejor en espacios con ciclos. El síntoma es un programa que "se cuelga" o consume memoria sin parar: está re-expandiendo los mismos estados por caminos distintos.
• Meter en el estado menos (o más) de lo necesario. Si la furgoneta no puede pasar dos veces por la misma casilla con obras temporales que dependen de la hora, el estado debe incluir el tiempo; si no lo incluye, A* dará rutas ilegales. Al revés, meter información irrelevante (el nivel de combustible cuando no restringe nada) multiplica el espacio inútilmente.
• Heurística cara de calcular. Si evaluar h cuesta más de lo que ahorra en expansiones, A* pierde contra Dijkstra en tiempo total aunque expanda menos nodos. Mide ambas cosas: expansiones y segundos.
• Consejo: las buenas heurísticas suelen salir de relajar el problema (quitar restricciones y resolver exacto lo relajado): Manhattan es "el problema sin obstáculos". Es la misma idea que las cotas optimistas de 02-03 — relajación = estimación optimista, y optimista = admisible.

Ejercicio 1 — Diseño de estado. La furgoneta de Rutalia reparte en la cuadrícula, pero ahora debe pasar primero por el punto de recogida R antes de ir al cliente C. Define formalmente el espacio de estados (estado, operadores, inicial, objetivo, coste) sin escribir código, y razona: ¿por qué no basta con el estado (fila, col)? ¿Cuántos estados tiene el nuevo espacio respecto al original?

Ejercicio 2 — Heurísticas admisibles. Para el problema del ejercicio 1 (pasar por R y luego llegar a C), se proponen tres heurísticas desde un estado en posición p que aún no ha recogido: (a) manhattan(p, C); (b) manhattan(p, R); (c) manhattan(p, R) + manhattan(R, C). Indica cuáles son admisibles y cuál domina a las demás (mayor información sin sobreestimar). Justifica cada una.

Ejercicio 3 — Experimento con A* ponderado. Modifica a_estrella para aceptar un peso w (f = g + w·h) y ejecuta sobre MAPA con w ∈ {0, 1, 1.5, 3}. Para cada w apunta longitud del camino y nodos expandidos, y explica el patrón que observes. ¿Qué w corresponde a Dijkstra? ¿Y a un voraz puro tipo "mejor primero por heurística"?

Solución 1: el estado debe ser (fila, col, recogido) con recogido ∈ {False, True}: la posición sola no determina los movimientos legales hacia el objetivo, porque estar en C solo es objetivo si ya se pasó por R. Operadores: los cuatro movimientos de siempre; al entrar en la casilla R, el sucesor tiene recogido=True. Inicial: (D_f, D_c, False). Objetivo: (C_f, C_c, True). Coste: 1 por movimiento. El espacio se duplica (cada casilla existe en dos "capas", antes y después de recoger): de 66 casillas libres a 132 estados. Es el patrón general: cada bit de memoria relevante para el futuro multiplica el espacio — por eso diseñar el estado mínimo suficiente es tan importante.

Solución 2:

• (a) manhattan(p, C): admisible — el camino real debe acabar en C, y ningún camino a C es más corto que la Manhattan directa; pero es poco informada: ignora el desvío obligatorio por R.
• (b) manhattan(p, R): admisible — todo camino válido debe pasar antes por R, y llegar a R cuesta al menos eso; también ignora parte del trabajo (de R a C).
• (c) manhattan(p, R) + manhattan(R, C): admisible y dominante — el camino real se descompone en "llegar a R" (≥ manhattan(p, R)) más "de R a C" (≥ manhattan(R, C)); la suma de dos cotas inferiores de tramos obligatorios y disjuntos es cota inferior del total. Como (c) ≥ (a) y (c) ≥ (b) en todo estado sin sobreestimar, domina: A* con (c) expande un subconjunto de los nodos que expandiría con las otras. En la capa recogido=True, la heurística correcta es directamente manhattan(p, C).

Solución 3:

Interpretación: w=0 anula la heurística — es exactamente Dijkstra. w=1 es A* óptimo. Al crecer w, el término h domina sobre g y el algoritmo tiende al voraz por heurística (greedy best-first: f = h, el límite w→∞), que corre hacia lo que parece cerca sin contabilizar lo ya gastado — rapidísimo y sin garantías, el mismo carácter que los voraces con contraejemplo de 02-02. Los valores exactos dependen del mapa y de los desempates; el patrón cualitativo (expansiones ↓, calidad ↓ a partir de w > 1) es lo que debe salirte.

Con esta lección se cierra el módulo 4 y, con él, un arco completo del curso. Un espacio de estados es un grafo implícito — estado, operadores, objetivo, coste — demasiado grande para materializarlo, y sobre él hemos reutilizado todo el arsenal del módulo 3 en versión "al vuelo": BFS cuando los pasos cuestan igual, UCS/Dijkstra cuando no, y A* cuando además sabemos estimar lo que falta, con la admisibilidad como contrato de optimalidad y la consistencia como salvaguarda del invariante del heap. El experimento de los nodos expandidos deja la moraleja del módulo: la información es rendimiento — una heurística honesta (nacida de relajar el problema, como las cotas de 02-03) convierte la exploración de un círculo ciego en un pasillo dirigido, y el peso w permite comprar velocidad pagando con garantías, de forma medible. También ha quedado trazada la frontera mental entre buscar el mejor camino (esta lección) y buscar la mejor configuración (backtracking y B&B del módulo 2): mismo ADN, distinta pregunta.

Miremos ahora el conjunto: en el módulo 2 optimizamos con reglas que nosotros diseñamos; en el 3 modelamos la ciudad como grafo con pesos que nosotros medimos; en este módulo buscamos, ordenamos y planificamos con invariantes y heurísticas que nosotros justificamos. Todo el conocimiento del problema lo hemos aportado a mano. Pero Rutalia tiene algo que aún no hemos explotado: millones de registros históricos — entregas con su hora, zona, peso, retraso, incidencias — que contienen patrones que nadie ha escrito como regla. ¿Cuánto tardará de verdad esta entrega? ¿Qué clientes generarán una incidencia? ¿Qué zonas se comportan igual? En el módulo 5 cambiamos de paradigma: en lugar de escribir las reglas, dejaremos que los algoritmos las aprendan de los datos. Empezamos en 05-01 con los fundamentos del aprendizaje automático.