La fuerza bruta de la lección anterior evaluó las 362.880 rutas posibles del repartidor de Rutalia para quedarse con una. Es un derroche monumental: la mayoría de esas rutas estaban condenadas desde sus primeros tramos, y aun así las construimos enteras. Esta lección enseña a explorar el espacio de soluciones sin enumerarlo: backtracking, que abandona una rama en cuanto viola una restricción, y branch and bound, que además la abandona en cuanto una cota optimista demuestra que ya no puede mejorar lo mejor encontrado. Son técnicas exactas — conservan la garantía de óptimo — y constituyen el motor real de los solvers de programación entera que mencionamos en 02-01. Al final resolveremos el mismo TSP de 10 puntos de 02-02 y contaremos, con números, cuántos nodos nos hemos ahorrado.

1. Explorar sin enumerar: la idea de podar
2. El esquema general de backtracking
3. Ejemplo guiado: subconjuntos que caben en la furgoneta
4. Mochila 0/1 por backtracking
5. Branch and bound: podar también por calidad
6. Mejor-primero con un heap
7. B&B para el TSP de Rutalia: contando podas
8. Los límites de la exactitud

Toda solución combinatoria se puede construir por decisiones parciales: cargo o no el envío E1, luego el E2… o bien: la primera parada es D, la segunda es A… Esas decisiones forman un árbol: la raíz es "nada decidido", cada nivel añade una decisión, y las hojas son soluciones completas. La fuerza bruta visita todas las hojas. La observación clave es que muchas veces podemos condenar un subárbol entero mirando solo su raíz:

• Poda de factibilidad (backtracking): si la carga parcial ya pesa 16 con capacidad 15, ninguna extensión será válida. No hace falta mirar ninguna de sus hojas.
• Poda de optimalidad (branch and bound): si lo mejor que esta rama podría llegar a dar — calculado con una cota optimista — es peor que la mejor solución completa que ya tengo, la rama es inútil aunque sea factible.

Cortar un nodo a profundidad k en un árbol de decisiones binarias elimina de golpe 2^(n−k) hojas. Podar pronto es exponencialmente rentable: toda la ingeniería de esta lección consiste en ganarse el derecho a podar pronto.

Backtracking es una plantilla recursiva — reconoce la estructura de 01-03: caso base, avance, y aquí además deshacer:

Los cuatro huecos a rellenar en cada problema:

El deshacer es lo que da nombre a la técnica: al agotar un subárbol, retrocedemos al estado anterior y probamos la siguiente opción. La pila de llamadas (01-03) mantiene el camino desde la raíz hasta el nodo actual; la memoria usada es solo la profundidad del árbol, Θ(n), aunque el árbol tenga millones de nodos.

Un apunte cultural: el ejemplo pedagógico clásico de backtracking son las N-reinas (colocar N reinas en un tablero N×N sin que se ataquen), donde la poda "esta reina ya está atacada" elimina ramas enormes. El esquema es idéntico al de arriba; nosotros seguiremos con paquetes y furgonetas, que es lo que le pagan a Rutalia.

Empecemos con la versión más simple: listar todos los subconjuntos válidos. Tres envíos de pesos [6, 5, 4] y una furgoneta de capacidad 10. Cada nivel del árbol decide sobre un envío: rama izquierda "lo cargo", rama derecha "no lo cargo":

La rama {E1, E2} muere a profundidad 2: pesa 11 > 10, así que sus dos descendientes (con y sin E3) ni se generan. De las 2³ = 8 hojas posibles, el backtracking visita 6. En un ejemplo de juguete el ahorro es anecdótico; con 30 envíos y cargas ajustadas, la misma poda elimina la mayor parte de los 2³⁰ subconjuntos.

Detalles finos: seleccion es una sola lista que se modifica y restaura (append/pop) — mucho más barato que copiar la lista en cada llamada; y la poda está en el if de la opción A: el subárbol infactible jamás se genera.

Para optimizar (no solo listar), añadimos el valor acumulado y recordamos el mejor completo visto. Usamos la instancia de 02-02: capacidad 15, pesos [12, 7, 11, 8, 9], valores [40, 24, 35, 26, 30], cuyo óptimo conocido es 50 (E2+E4):

Funciona y poda lo infactible, pero tiene un punto ciego: explora ramas factibles pero inútiles — combinaciones ligeras que jamás alcanzarán 50 €. La poda de factibilidad no sabe nada de calidad. Para eso necesitamos la segunda idea.

Branch and bound (B&B) enriquece el árbol con dos números:

• El incumbente (cota inferior en maximización): la mejor solución completa encontrada hasta ahora. Es un logro real: cualquier cosa peor no interesa.
• La cota optimista de cada nodo (cota superior en maximización): un cálculo rápido de lo máximo que podría llegar a valer la mejor hoja de su subárbol. Debe ser optimista de verdad — nunca subestimar — o podaremos ramas que contenían el óptimo, perdiendo la exactitud.

Regla de poda: si cota_optimista(nodo) ≤ incumbente, el subárbol entero se descarta. La garantía de óptimo se conserva porque solo tiramos ramas demostradamente incapaces de mejorar.

¿De dónde salen las cotas optimistas? De relajar el problema: resolver una versión más fácil cuyo óptimo sea siempre ≥ el real. Para la mochila 0/1, la relajación perfecta la conocemos de 02-02: la mochila fraccionaria (permitir partir envíos). Se resuelve en Θ(n log n) con el voraz por densidad, y su valor siempre iguala o supera al de la 0/1 — es el mismo problema con menos restricciones.

Con esta cota, el nodo "no cargué nada de valor y ya voy por el envío 4" se poda al instante: ni relleno fraccionario llega al incumbente. Ese es el patrón general de B&B: ramificar (branch) generando hijos y acotar (bound) para matarlos pronto. Y aquí se cierra un círculo con 02-01: los solvers de programación lineal entera hacen exactamente esto, usando como cota optimista la relajación continua del PL — por eso vimos que el óptimo continuo (62,5) siempre superaba al entero (58).

Queda una decisión de diseño: ¿en qué orden explorar los nodos vivos? El backtracking recursivo va en profundidad (DFS implícito en la pila de llamadas). Pero si exploramos primero los nodos de mejor cota optimista, encontramos antes soluciones buenas, el incumbente mejora antes, y las podas llegan antes. Es la estrategia mejor-primero (best-first), y la estructura para implementarla la sembramos en 01-04: un heap (heapq), que extrae el mínimo en Θ(log n).

En la práctica se combinan (profundidad con buen orden de hijos, o mejor-primero con límite de memoria). Nosotros usaremos mejor-primero puro para ver el mecanismo con claridad.

Vamos a por el plato fuerte: la instancia de 10 puntos de 02-02 (reutiliza PUNTOS, NOMBRES, D y longitud_ruta de esa lección). Ahora minimizamos, así que los papeles se invierten: el incumbente es una cota superior (la mejor ruta completa conocida) y la cota de cada nodo es inferior y optimista: nunca puede sobrestimar los km que faltan.

Nuestra cota, sencilla pero honesta: km recorridos + la arista más barata que sale de cada punto aún pendiente (incluido el punto actual, que aún debe salir hacia alguien). Ninguna ruta real puede gastar menos que eso en salir de cada punto, así que jamás sobrestima. Cotas más finas (como la del árbol de expansión mínimo sobre los pendientes — concepto que formalizaremos en 03-04) podan aún más a cambio de más cálculo por nodo: es el eterno equilibrio de B&B.

Lectura del código, pieza a pieza:

• Cada nodo vivo es una tupla (cota, km, ruta, visitados). Como heapq ordena por el primer elemento, el heap siempre entrega el nodo de menor cota inferior — mejor-primero, tal cual.
• La poda actúa dos veces: al sacar un nodo del heap (su cota pudo quedar obsoleta si el incumbente mejoró mientras esperaba) y antes de encolar hijos (no malgastamos memoria en condenados).
• Cuando una ruta se completa y mejora el incumbente, todas las ramas pendientes con cota ≥ ese valor mueren en cadena. Por eso encontrar pronto una buena ruta acelera tanto: si arrancas el incumbente con los 43,1 km del vecino más cercano (ejercicio 3 de 02-02) en lugar de infinito, la poda muerde desde el primer nodo.

Los números. En nuestra ejecución, el algoritmo devuelve el óptimo exacto — 35,22 km, la misma ruta que la fuerza bruta — tras expandir unos 1.200 nodos y ejecutar unas 2.800 podas (la cifra exacta varía ligeramente según cómo se desempaten cotas iguales). Pongámoslo en perspectiva:

Tres órdenes de magnitud menos trabajo, misma garantía matemática. Fíjate además en la fila del medio: en el TSP puro el backtracking de factibilidad no poda nada, porque cualquier permutación parcial puede completarse. La poda por cota es la que hace todo el trabajo — cada problema dicta qué tipo de poda tiene sentido.

¿Hemos vencido a la explosión combinatoria? No: la hemos retrasado. B&B sigue siendo exponencial en el peor caso; solo recorta el factor con inteligencia. Con buenas cotas, el estado del arte resuelve TSP de cientos o miles de nodos, pero cada instancia difícil puede dispararse, y problemas como la planificación conjunta de toda la flota de Rutalia (decenas de furgonetas × cientos de paradas × ventanas horarias) quedan fuera del alcance exacto con cualquier presupuesto de cómputo razonable. Cuando eso ocurre, el ingeniero cambia el contrato: renuncia a la garantía de óptimo a cambio de soluciones muy buenas en tiempo predecible. Ese es el territorio de las metaheurísticas, y es exactamente a donde vamos.

• Cotas "optimistas" que no lo son. Si tu cota inferior puede sobrestimar (p. ej., usar la arista media en vez de la mínima), podarás ramas que contenían el óptimo y el algoritmo devolverá basura con cara de resultado exacto. Verifica la propiedad en papel: ¿es imposible que una solución real cueste menos que mi cota?
• Olvidar el deshacer. Si tras la llamada recursiva no restauras el estado (seleccion.pop()), las ramas siguientes heredan decisiones fantasma. Síntoma típico: resultados que dependen del orden de exploración.
• Copiar estado en cada nodo sin necesidad. ruta + [j] crea listas nuevas — cómodo y correcto, pero en instancias grandes el coste de copia domina. La alternativa aplicar/deshacer sobre una estructura única es más rápida (y más delicada). Empieza claro, optimiza después midiendo (01-02).
• No sembrar el incumbente. Arrancar con mejor = infinito desperdicia las podas iniciales. Un voraz barato (vecino más cercano, FFD…) da un incumbente inicial que activa la poda desde el minuto cero. Es la sinergia voraz + B&B: el voraz no garantiza nada, pero acelera al que sí garantiza.
• Cota cara que no compensa. Una cota que poda un 5 % más pero cuesta 10 veces más por nodo empeora el total. Mide nodos expandidos × coste por nodo, no solo nodos.
• Consejo: instrumenta siempre tu B&B con contadores (nodos_expandidos, podas) como hicimos aquí. Son tu tablero de mandos: si las podas no crecen al mejorar la cota, la cota nueva no está aportando.

1. Traza en papel. Con capacidad 10 y envíos (peso, valor): P1 (6, 48), P2 (5, 35), P3 (5, 35) — el contraejemplo del voraz de 02-02 —, dibuja el árbol de backtracking (8 hojas potenciales) y márca: (a) qué ramas corta la poda de factibilidad; (b) cuál es el óptimo. Después calcula la cota fraccionaria del nodo raíz y del nodo "descarté P1": ¿qué te dicen?

2. Sembrar el incumbente. Modifica tsp_branch_and_bound para aceptar un parámetro km_inicial (cota superior de arranque) y ejecútalo con (a) infinito y (b) los 43,1 km del vecino más cercano. Compara nodos_expandidos y podas en ambos casos. ¿Por qué mejora?

3. Cota más fina. La cota min_salida ignora que las aristas elegidas deben formar una ruta. Una mejora barata: para cada punto pendiente, usar la media de sus dos aristas más baratas en lugar de una sola (cada punto de un ciclo tiene una entrada y una salida). Argumenta por qué sigue siendo una cota inferior válida e impleméntala. ¿Expande menos nodos?

Ejercicio 1. (a) La poda de factibilidad corta: {P1,P2} (peso 11 > 10) antes de decidir P3, y {P1,P3} (11). Sobreviven como hojas: {P1} (48), {P2,P3} (70), {P2} (35), {P3} (35), {} (0) — el óptimo es {P2,P3} = 70. (b) Cota fraccionaria de la raíz: densidades 8, 7, 7 → P1 entero (48) + P2 entero (35, peso 11 > 10: solo caben 4 de sus 5 unidades) → 48 + 35·(4/5) = 76. Del nodo "descarté P1": P2 + P3 = 10 de peso justo → cota 70, que además es alcanzable. Lectura: la raíz promete ≤ 76 (optimista, como debe ser). Sigamos la rama "cargué P1": con 4 unidades libres y P2 pendiente, su cota es 48 + 35·(4/5) = 76; tras descartar P2, con P3 pendiente sigue siendo 48 + 28 = 76; y al descartar también P3, cae a 48. Si exploramos primero la rama "descarté P1" (mejor-primero lo haría al estrecharse las cotas), el incumbente llega enseguida a 70… y aun así la rama de P1 sobrevive mientras prometa 76. El patrón que hay que retener: las cotas se estrechan al bajar por el árbol, y el incumbente mata todo lo que promete un valor menor o igual que él — aquí acaba muriendo todo lo que promete ≤ 70.

Ejercicio 2.

Con km_inicial = 43.1, los nodos cuya cota inferior supere 43,1 mueren antes de que exista ningún incumbente propio: la poda funciona desde la raíz. En nuestras pruebas, la cifra de nodos expandidos baja de forma apreciable (y la de podas tempranas sube); el efecto es mucho más dramático en instancias mayores, donde sin semilla el heap engorda con miles de nodos mediocres antes de la primera ruta completa. La combinación "heurística barata para el incumbente + B&B para el certificado" es un patrón profesional estándar.

Ejercicio 3. Validez: en un ciclo, cada punto tiene exactamente una arista de entrada y una de salida. La suma de costes del ciclo puede escribirse como Σ (entrada + salida)/2 sobre todos los puntos. Como para cada punto usamos la media de sus dos aristas más baratas, ninguna asignación real de entrada/salida puede costar menos: la cota nunca sobrestima. Implementación: precalcula dos_min[i] = (d1 + d2) / 2 con las dos menores distancias de la fila D[i], y suma dos_min[j] para cada pendiente (ajustando los puntos ya conectados parcialmente). Al ser más ajustada (mayor o igual que la de una sola arista), poda estrictamente más: en nuestra instancia, la reducción de nodos expandidos es notable con un sobrecoste por nodo mínimo. Este juego — invertir en cotas más finas para podar más — es, llevado al extremo con relajaciones de PL, lo que hace competitivos a los solvers industriales de PLE.

Hemos convertido la enumeración ciega en una búsqueda con criterio: el backtracking descarta lo infactible en cuanto asoma (esquema recursivo con aplicar/explorar/deshacer, memoria lineal), y el branch and bound descarta también lo factible-pero-condenado usando cotas optimistas — la relajación fraccionaria en la mochila, las aristas mínimas en el TSP — con la estrategia mejor-primero servida por el heap que aprendimos en 01-04. El resultado en el TSP de Rutalia es elocuente: el mismo óptimo de 35,22 km que costó 362.880 evaluaciones a la fuerza bruta cayó expandiendo unos 1.200 nodos, sin ceder un milímetro en la garantía. Pero también hemos sido honestos con el límite: la explosión combinatoria está retrasada, no vencida, y la flota completa de Rutalia sigue fuera del alcance de cualquier método exacto. En la próxima lección cruzaremos esa frontera de forma deliberada: los algoritmos genéticos renuncian al certificado de optimalidad y, a cambio, encuentran soluciones excelentes donde B&B ni siquiera puede empezar. Veremos qué se siente al operar sin red — y cómo hacerlo con criterio profesional.