En la lección anterior formalizamos el mapa de reparto de NovaMarket como el grafo GRAFO_CIUDAD y comprobamos que la fuerza bruta se ahoga en cuanto crecen las entregas: evalúa n! rutas y la inmensa mayoría son físicamente imposibles. En esta lección vamos a resolver el problema de forma inteligente. Empezaremos por el caso más simple y más importante: llevar la furgoneta desde Almacen_Getafe hasta un barrio de destino por el mejor camino, construyendo la solución paso a paso, solo a través de carreteras reales, y sin enumerar nada que no haga falta. Presentaremos el vocabulario de la búsqueda (espacio de estados, nodo, frontera, explorados), los criterios con los que se juzga un algoritmo de búsqueda, y después implementaremos cinco algoritmos clásicos sobre el mismo grafo: tres no informados (anchura, profundidad y coste uniforme, que solo conocen el grafo) y dos informados (voraz y A*, que además usan una estimación de lo que falta hasta la meta). Verás con trazas y tablas por qué la búsqueda en anchura no siempre da el camino más corto en kilómetros, por qué la profundidad puede devolver caminos malos, y cómo una heurística tan sencilla como la distancia en línea recta permite a A* encontrar el óptimo explorando menos. Estos algoritmos son el corazón de cualquier planificador de rutas y los reutilizaremos en el proyecto de ejercicios del módulo 9 (09-01).

1. Vocabulario de la búsqueda: espacio de estados, nodo, frontera, explorados, camino y coste
2. Árbol de búsqueda frente a grafo: el problema de los estados repetidos
3. Cómo se evalúa un algoritmo de búsqueda: completitud, optimalidad, complejidad
4. El esquema general y el grafo de trabajo
5. Búsqueda en anchura (BFS) con deque, con traza paso a paso
6. Búsqueda en profundidad (DFS): la misma idea con una pila
7. Búsqueda de coste uniforme (Dijkstra) con heapq
8. Búsqueda informada: heurísticas, admisibilidad y consistencia
9. Búsqueda voraz (greedy best-first)
10. A*: lo mejor de ambos mundos, con traza
11. Tabla comparativa y cuándo usar cada uno

Recuerda la formulación de problemas de 02-01 y 03-01: estado inicial, acciones, modelo de transición, test de objetivo y coste. Sobre esa formulación, los algoritmos de búsqueda manejan unos pocos conceptos que conviene fijar con precisión, porque aparecen en el código de todos ellos:

Toda búsqueda funciona repitiendo el mismo bucle: sacar un nodo de la frontera, comprobar si es objetivo, y si no, expandirlo añadiendo sus sucesores a la frontera. La única diferencia entre los algoritmos de esta lección es qué nodo se saca de la frontera en cada paso. Esa elección es la "estrategia de búsqueda", y determina si se encuentra solución, si es la mejor y cuánto cuesta encontrarla.

Es importante no confundir dos cosas: el grafo del espacio de estados (el mapa: 8 nodos, 12 aristas, fijo) y el árbol de búsqueda que el algoritmo va construyendo mientras explora (raíz = estado inicial; hijos = sucesores; cada rama es un camino). El mismo estado puede aparecer en varios lugares del árbol: desde Getafe se puede llegar a Villaverde directamente o pasando por Leganés, y ambos serían nodos distintos del árbol con el mismo estado.

Si no controlamos esos estados repetidos, el árbol crece sin límite (Getafe → Leganés → Getafe → Leganés…) aunque el grafo sea diminuto. La solución estándar es la búsqueda en grafo: recordar los estados ya explorados (y los que ya están en la frontera) y no volver a generarlos. Es lo que hace el conjunto/diccionario padres en nuestras implementaciones: además de recordar de dónde venimos (para reconstruir el camino al final), sirve de "ya lo he visto". La variante sin memoria se llama búsqueda en árbol y solo tiene sentido en espacios sin ciclos, como los árboles de juego de 03-03.

Cuatro criterios, que usaremos en la tabla final:

• Completitud: ¿garantiza encontrar una solución si existe?
• Optimalidad: ¿garantiza que la solución encontrada es la de menor coste?
• Complejidad temporal: ¿cuántos nodos genera o expande? Se expresa en función del factor de ramificación b (número medio de sucesores por nodo; en nuestro grafo, unos 3) y la profundidad d de la solución (número de pasos). Un árbol de ramificación b y profundidad d tiene del orden de bᵈ nodos, así que casi todas las complejidades son de la forma O(bᵈ): exponenciales, como anticipó 03-01.
• Complejidad espacial: ¿cuántos nodos guarda en memoria a la vez? Aquí es donde más se diferencian anchura y profundidad.

Trabajaremos siempre con el GRAFO_CIUDAD de 03-01, que reproducimos como recordatorio, más dos funciones auxiliares que todos los algoritmos comparten: reconstruir_camino, que sigue la cadena de padres desde el objetivo hasta el inicio, y coste_camino, que suma los kilómetros de un camino.

El diccionario padres es la pieza clave de todas las implementaciones: padres[X] = Y significa "a X se llegó desde Y". El nodo inicial tiene padre None, y eso es lo que detiene el bucle de reconstruir_camino. El problema que resolveremos en todas las secciones será ir de Almacen_Getafe a Retiro, el barrio más alejado del almacén, para el que existen varios caminos razonables.

Estrategia: expandir primero los nodos menos profundos. La frontera es una cola FIFO (deque): los nodos se sacan en el mismo orden en que entraron, así que primero se expanden todos los que están a un paso del inicio, luego los que están a dos, etc. Va explorando el mapa "en ondas concéntricas" desde el almacén.

La traza (frontera y explorados después de expandir cada nodo) es esta:

Léela con calma: en el paso 6, al expandir Vallecas, se genera Retiro por primera vez y se anota padres["Retiro"] = "Vallecas". Cuando en el paso 7 se expande Arganzuela, Retiro ya está en padres y no se actualiza, aunque el camino por Arganzuela sea más corto en kilómetros. BFS encuentra el camino con menos tramos (3), no el de menos kilómetros: 18,5 km, cuando el óptimo son 17,0 km por Villaverde–Usera–Arganzuela (4 tramos). Ese es el límite fundamental de BFS: es óptimo solo si todas las acciones cuestan lo mismo. Es completo (si hay solución, la encuentra), y su coste temporal y espacial es O(bᵈ): guarda en la frontera toda la "onda" actual, lo que en mapas grandes ocupa mucha memoria.

Estrategia: expandir siempre el nodo más profundo, es decir, seguir un camino hasta el final antes de probar alternativas. El código es literalmente el de BFS cambiando la cola por una pila (append/pop de una lista): tal como anunciamos en 03-01, la estructura de datos define el algoritmo.

DFS ha explorado menos nodos (6 frente a 8), pero devuelve un camino claramente peor: 25 km, 5 tramos. Se ha "metido" por Leganés, ha seguido hacia Carabanchel y Usera, y desde ahí ha continuado por la primera salida no visitada hasta tropezar con Retiro. Características:

• No es óptimo: devuelve el primer camino que encuentra, no el mejor.
• Puede no ser completo: en espacios infinitos o con ciclos sin control de repetidos, puede seguir un camino sin fin y no volver nunca. Con nuestro padres como control de visitados y un grafo finito, sí termina.
• Su gran ventaja es la memoria: solo guarda el camino actual y los hermanos pendientes, O(b·m) donde m es la profundidad máxima, frente al O(bᵈ) de BFS. Por eso se usa en problemas con muchísimos estados donde cualquier solución vale (y en la recursión de minimax de 03-03, que es una búsqueda en profundidad).

Una variante habitual, la búsqueda en profundidad limitada (cortar a una profundidad máxima) y su versión iterativa (profundizar 1, 2, 3… hasta encontrar solución), combina la poca memoria de DFS con la completitud de BFS; la mencionamos por completitud, no la implementaremos.

Estrategia: expandir siempre el nodo de la frontera con menor coste acumulado g. La frontera es una cola de prioridad que implementamos con heapq, un montículo binario en el que heappop devuelve siempre la tupla más pequeña. Es el algoritmo de Dijkstra visto como búsqueda, y a diferencia de BFS sí tiene en cuenta los kilómetros.

Fíjate en tres detalles que explican por qué funciona:

• En el paso 5, al expandir Usera, se descubre que Arganzuela está a 13,0 km (por Usera) en lugar de 14,0 (por Carabanchel). Se reasigna el padre de Arganzuela y se inserta una nueva entrada en el montículo. La antigua (14,0) queda obsoleta; cuando salga, el if nodo in explorados: continue la descarta. Es más simple que borrarla del montículo y es la técnica habitual ("borrado perezoso").
• En el paso 6 se genera Retiro con 18,5 km (por Vallecas), pero no se declara solución al generarlo: se espera a que salga del montículo. En el paso 7 aparece Retiro con 17,0 km y, como es menor, sale antes. Si hubiéramos comprobado el objetivo al generar, habríamos devuelto 18,5 km. Esta diferencia con BFS (que sí puede comprobar al generar) es sutil pero decisiva.
• El resultado es óptimo: 17,0 km. La búsqueda de coste uniforme es completa y óptima siempre que los costes sean positivos, a cambio de explorar en todas direcciones sin ninguna idea de dónde está la meta (aquí ha expandido los 8 nodos, incluido Leganés, que está en dirección contraria).

Los tres algoritmos anteriores son no informados: solo saben lo que dice el grafo. Un conductor humano, en cambio, sabe que Retiro "queda hacia el norte" y no se plantea salir hacia Leganés. Esa intuición se formaliza como una función heurística h(n): una estimación barata del coste que falta desde el nodo n hasta el objetivo. La heurística más natural en mapas es la distancia en línea recta: nunca hay una carretera más corta que la recta, y se calcula al instante a partir de coordenadas.

Fijamos las coordenadas (en kilómetros, sobre un plano ficticio con el almacén en el origen) de los nodos de GRAFO_CIUDAD, y la heurística euclídea:

Dos propiedades de una heurística determinan si A* será óptimo:

• Admisible: nunca sobreestima el coste real que falta, h(n) ≤ coste real mínimo de n al objetivo. La distancia en línea recta es admisible por construcción: la carretera siempre es igual o más larga que la recta. Puedes comprobarlo arista por arista en nuestro grafo (por ejemplo, Usera–Arganzuela: 3,5 km de carretera frente a 3,16 km en línea recta).
• Consistente (o monótona): para todo tramo n → n' de coste c, se cumple h(n) ≤ c + h(n'). Intuitivamente, "la estimación no puede bajar más de lo que cuesta el tramo"; equivale a la desigualdad triangular, que la distancia euclídea cumple siempre. Toda heurística consistente es admisible; en la práctica, casi todas las heurísticas naturales lo son. Con una heurística consistente, la primera vez que A* extrae un nodo de la frontera ya lo hace con su coste óptimo, y por eso podemos cerrar nodos (explorados) sin volver a abrirlos.

Una heurística que sobreestime puede llevar a A* a descartar el camino óptimo por parecer caro (lo verás en el ejercicio 2). Una heurística que subestime demasiado (en el extremo, h = 0) sigue siendo admisible pero no ayuda: A* con h = 0 es exactamente la búsqueda de coste uniforme.

Estrategia: expandir siempre el nodo que parece más cercano a la meta, es decir, el de menor h(n), ignorando por completo lo que ya se ha recorrido (g). Es la traducción directa de "tirar siempre hacia donde está Retiro".

Es rapidísima (solo 4 nodos explorados: nunca mira hacia Leganés ni Carabanchel), pero no es óptima: desde Villaverde, Vallecas (h = 5,00) parece más cerca de Retiro que Usera (h = 5,39), así que se va por Vallecas, sin darse cuenta de que el tramo Villaverde–Vallecas cuesta 7,5 km y el desvío total sale a 18,5 km. Ha caído en la trampa de mirar solo el futuro estimado y no el pasado real. Además, sin control de repetidos, la voraz puede entrar en bucles (no es completa en general). Su utilidad real es como componente de otros métodos y como algoritmo "de emergencia" cuando el tiempo de respuesta lo es todo.

Estrategia: expandir el nodo con menor f(n) = g(n) + h(n): coste real recorrido más coste estimado restante. Combina la garantía de coste uniforme (que mira g) con la dirección de la voraz (que mira h). El código es el de coste uniforme cambiando la prioridad:

A* devuelve el óptimo (17,0 km), como coste uniforme, pero orientado por la heurística: sale directamente hacia Villaverde (f = 14,06 < 15,90 de Leganés), sigue por Usera y Arganzuela, y solo cuando esas opciones tienen f mayor que Leganés vuelve atrás a comprobarlo. Vallecas, la trampa de la voraz, tiene f = 17,50 y nunca llega a expandirse. En un grafo tan pequeño el ahorro es modesto (7 nodos frente a 8), pero en un mapa real de miles de cruces la diferencia entre coste uniforme y A* es de órdenes de magnitud: A* explora una "elipse" alrededor de la línea recta entre origen y destino, mientras coste uniforme explora un círculo completo alrededor del origen.

Propiedades: A* es completo y óptimo si h es admisible (en búsqueda en árbol) o consistente (en búsqueda en grafo, como la nuestra). Su complejidad sigue siendo exponencial en el peor caso, pero se reduce drásticamente cuanto mejor sea la heurística; y su punto débil es la memoria, porque guarda toda la frontera igual que BFS.

Resultados sobre GRAFO_CIUDAD para tres destinos distintos (kilómetros del camino devuelto / nodos explorados):

Y el resumen teórico (b = factor de ramificación, d = profundidad de la solución, m = profundidad máxima):

Regla práctica de Marta para el planificador de NovaMarket: A* con distancia en línea recta para calcular el mejor camino entre dos puntos; coste uniforme (Dijkstra) cuando se necesitan las distancias desde un punto a todos los demás (que es justo lo que necesitaremos en 03-04 para construir la matriz de distancias entre paradas); BFS solo para preguntas de "cuántos saltos"; DFS y voraz como piezas auxiliares.

• Comprobar el objetivo al generar en lugar de al extraer en coste uniforme y A*: devuelve el primer camino que toca la meta, no el mejor (aquí habría dado 18,5 km en vez de 17,0). En BFS sí es correcto comprobar al generar, porque todos los caminos de la misma profundidad cuestan lo mismo.
• Usar list.pop(0) para la cola de BFS: es O(n) por extracción; deque.popleft() es O(1).
• Olvidar el control de repetidos: sin padres (o un conjunto de visitados), DFS y voraz pueden ciclar indefinidamente entre dos barrios conectados.
• No permitir reasignar el padre en coste uniforme/A*: si tratas padres como en BFS (solo se asigna la primera vez), pierdes la mejora Carabanchel→Usera para Arganzuela y dejas de ser óptimo. La condición correcta es nuevo_g < mejor_g[vecino].
• Poner en el montículo tuplas que no se pueden comparar: si dos entradas empatan en f y en g, Python compara el tercer elemento; con cadenas funciona, con objetos sin orden definido da error. Añade un contador como desempate si tus nodos no son comparables.
• Heurística en unidades distintas al coste: si el coste está en minutos y h en kilómetros, A* deja de tener garantías. Convierte h a la misma unidad (por ejemplo, km / velocidad máxima → minutos), lo que además la mantiene admisible.
• Confundir "explora menos nodos" con "mejor": DFS y voraz exploran menos y devuelven caminos peores. Elige según lo que necesites garantizar (optimalidad, memoria, tiempo de respuesta), no por el contador de nodos.

Sin ejecutar código, construye la tabla de traza de A* desde Almacen_Getafe hasta Carabanchel (usa la tabla de coordenadas para calcular h con math.hypot o a mano). ¿Cuántos nodos expande y qué camino devuelve? Compáralo con lo que expandiría coste uniforme para el mismo destino. Después verifica tu tabla con a_estrella(..., traza=True).

Supón que alguien introduce mal las coordenadas de Arganzuela en COORDENADAS y pone (10, 16) en lugar de (1, 10). Calcula la nueva h(Arganzuela, Retiro), comprueba si sigue siendo admisible (compárala con el coste real Arganzuela → Retiro, que es 4,0 km) y ejecuta a_estrella hacia Retiro. ¿Qué camino devuelve y por qué? Restaura las coordenadas al terminar.

Escribe un bucle que, para cada nodo del grafo como destino, ejecute bfs y coste_uniforme desde Almacen_Getafe e imprima el número de tramos y los kilómetros de cada camino. ¿En qué destinos discrepan y por qué precisamente en esos?

Solución 1. h hacia Carabanchel (−2, 7): Getafe 7,28; Leganés 4,12; Villaverde 6,40; Carabanchel 0.

A* expande solo 3 nodos y devuelve Almacen_Getafe -> Leganes -> Carabanchel (9,0 km). Coste uniforme llega al mismo camino, pero expande 4 (Getafe, Leganés, Villaverde y Carabanchel), porque Villaverde con g = 5,0 sale del montículo antes que Carabanchel con g = 9,0: sin heurística no tiene forma de saber que Villaverde queda en dirección contraria.

Solución 2. Con (10, 16), h(Arganzuela, Retiro) = √(6² + 4²) = 7,21 km, mayor que el coste real de 4,0 km: la heurística ya no es admisible. Al ejecutar A* hacia Retiro, Arganzuela pasa a tener f = 13,0 + 7,21 = 20,21, mayor que el f de Retiro vía Vallecas (12,5 + 6,0 + 0 = 18,50), así que A* extrae Retiro por Vallecas antes de expandir Arganzuela y devuelve Almacen_Getafe -> Villaverde -> Vallecas -> Retiro con 18,5 km: ha perdido la optimalidad (17,0 km) por culpa de una sobreestimación. Es la demostración práctica de la sección 8: la admisibilidad no es un tecnicismo, sino la condición que hace fiable a A*.

Solución 3.

Discrepan en Arganzuela (BFS: 3 tramos por Leganés–Carabanchel, 14,0 km; UCS: 3 tramos por Villaverde–Usera, 13,0 km) y en Retiro (BFS: 3 tramos, 18,5 km; UCS: 4 tramos, 17,0 km). En Arganzuela ambos usan 3 tramos, pero BFS se queda con el primero que descubre (por orden de expansión, el de Carabanchel) sin mirar kilómetros; en Retiro, el camino de menos tramos no es el de menos kilómetros. En los demás destinos el camino de menos tramos coincide con el de menos kilómetros, y por eso ambos algoritmos concuerdan; pero es una coincidencia del mapa, no una garantía.

Hemos convertido la formulación de problemas en algoritmos que funcionan. Todos comparten el mismo esqueleto (frontera, explorados, padres, bucle de extraer-comprobar-expandir) y se diferencian únicamente en qué nodo sale primero de la frontera: el más antiguo (anchura, con deque), el más reciente (profundidad, con una pila), el de menor coste acumulado g (coste uniforme, con heapq), el de menor estimación h (voraz) o el de menor g + h (A*). Hemos visto con trazas sobre GRAFO_CIUDAD que BFS minimiza tramos y no kilómetros, que DFS ahorra memoria pero devuelve caminos malos, que coste uniforme es óptimo pero explora en todas direcciones, que la voraz es rápida pero cae en trampas, y que A* con una heurística admisible y consistente (la distancia en línea recta calculada a partir de COORDENADAS) obtiene el óptimo explorando menos. También hemos aprendido a evaluar cualquier algoritmo de búsqueda por su completitud, optimalidad y complejidad temporal y espacial.

Hasta ahora la furgoneta buscaba su camino en un mundo que no reacciona: el mapa no cambia porque ella se mueva. En la siguiente lección, Búsqueda con Adversario: Juegos y Minimax, introduciremos un segundo agente con objetivos opuestos, que responde a cada decisión nuestra con la suya. Veremos cómo se representa esa situación como un árbol de juego, cómo el algoritmo minimax elige la mejor jugada suponiendo que el rival también juega lo mejor posible, y cómo la poda alfa-beta permite hacerlo explorando una fracción del árbol; lo probaremos con el tres en raya y lo llevaremos a una situación de NovaMarket con competidor.