El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Algoritmos de Optimización Combinatoria

Siguiente ►
►

En la lección anterior, Rutalia decidió cuántas horas de furgoneta y de bici contratar: variables continuas, región factible suave, solver exacto en milisegundos. Pero la mayoría de las decisiones diarias del almacén no son así. ¿Qué paquetes cargo en esta furgoneta de 100 kg? ¿En qué orden visita el repartidor sus 10 direcciones? ¿Cuántas furgonetas necesito, como mínimo, para sacar todos los pedidos de hoy? Aquí no hay fracciones: cada paquete va o no va, cada dirección ocupa una posición u otra en la ruta. El espacio de soluciones es discreto y, sobre todo, explosivo. Esta lección presenta la optimización combinatoria: sus tres problemas canónicos en versión Rutalia (mochila, viajante y bin packing), cuándo un algoritmo voraz basta y cuándo nos engaña, y qué significa en la práctica que un problema sea NP-duro.

Contenido

  1. Qué hace "combinatoria" a la optimización
  2. La explosión combinatoria, en números
  3. La mochila 0/1: cargar una furgoneta
  4. El problema del viajante (TSP): ordenar la ruta del repartidor
  5. Bin packing: ¿cuántas furgonetas necesito?
  6. Algoritmos voraces: cuándo brillan y cuándo fallan
  7. NP-dureza para ingenieros: ¿exacto o aproximado?

Qué hace "combinatoria" a la optimización

Un problema de optimización es combinatorio cuando sus soluciones son objetos discretos — subconjuntos, permutaciones, asignaciones — en lugar de números reales. Las tres piezas de 02-01 siguen ahí, pero cambian de forma:

Pieza En PL (02-01) En optimización combinatoria
Variables de decisión Números reales (x = 10,5 horas) Decisiones sí/no, órdenes, agrupaciones
Espacio de soluciones Polígono continuo (infinitos puntos, pero "suave") Conjunto finito pero gigantesco de combinaciones
Herramienta geométrica El óptimo está en un vértice No hay geometría que nos salve: hay que buscar

La ironía es deliciosa: el espacio continuo era infinito y lo resolvíamos exacto en milisegundos; el espacio discreto es finito y a menudo no podemos ni soñar con recorrerlo. La razón es que "finito" y "abarcable" no son lo mismo.

La explosión combinatoria, en números

Recuperemos la tabla de jerarquías de 01-01, ahora aplicada a espacios de soluciones. Supón una máquina capaz de evaluar 100 millones de soluciones por segundo (10⁸, generosa para Python):

n Subconjuntos (2ⁿ) Tiempo Permutaciones (n!) Tiempo
10 1.024 instantáneo 3.628.800 0,04 s
15 32.768 instantáneo ≈ 1,3 · 10¹² ≈ 3,6 horas
20 ≈ 10⁶ 0,01 s ≈ 2,4 · 10¹⁸ ≈ 770 años
30 ≈ 10⁹ 10 s ≈ 2,7 · 10³² ≈ 8 · 10¹⁶ años
50 ≈ 10¹⁵ 130 días ≈ 3 · 10⁶⁴ edad del universo × 10⁴⁷

Dos lecturas prácticas:

  • Elegir subconjuntos (¿qué paquetes cargo?) crece como 2ⁿ: brutal, pero aguanta hasta n ≈ 25-30 por fuerza bruta.
  • Elegir órdenes (¿en qué secuencia reparto?) crece como n!: se muere entre n = 12 y n = 15.

Esto explica la estructura del resto del módulo: fuerza bruta hoy (para entender los problemas), poda inteligente en 02-03 (para llegar más lejos con garantía de óptimo) y metaheurísticas en 02-04/02-05 (para cuando ni la poda basta).

La mochila 0/1: cargar una furgoneta

El problema en Rutalia. Una furgoneta admite 15 unidades de carga (peso normalizado). Hay 5 envíos pendientes; cada uno tiene un peso y un valor (lo que Rutalia factura por entregarlo hoy). ¿Qué subconjunto cargo para maximizar la facturación sin exceder la capacidad?

Envío Peso Valor (€)
E1 12 40
E2 7 24
E3 11 35
E4 8 26
E5 9 30

Formulación. Variables binarias xᵢ ∈ {0, 1} (cargo o no el envío i). Maximizar Σ valorᵢ·xᵢ sujeto a Σ pesoᵢ·xᵢ ≤ 15. Es exactamente una programación lineal entera como las de 02-01 — con la restricción extra de que las variables solo valen 0 o 1. De ahí el nombre mochila 0/1 (0/1 knapsack): cada objeto entra entero o no entra.

Solución por programación dinámica. Aquí cosechamos lo sembrado en 01-03: el problema tiene subproblemas solapados y subestructura óptima. Definimos mejor[i][c] = valor máximo usando solo los primeros i envíos con capacidad c. Para cada envío solo hay dos opciones — llevarlo o no — y ambas remiten a subproblemas más pequeños:

def mochila_01(pesos, valores, capacidad):
    n = len(pesos)
    # mejor[i][c] = valor máximo con los envíos 0..i-1 y capacidad c
    mejor = [[0] * (capacidad + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        peso, valor = pesos[i - 1], valores[i - 1]
        for c in range(capacidad + 1):
            mejor[i][c] = mejor[i - 1][c]          # opción A: no cargar el envío i
            if peso <= c:                           # opción B: cargarlo (si cabe)
                con_el = mejor[i - 1][c - peso] + valor
                mejor[i][c] = max(mejor[i][c], con_el)

    # Reconstrucción de la solución (como en 01-03: recorrer la tabla hacia atrás)
    elegidos, c = [], capacidad
    for i in range(n, 0, -1):
        if mejor[i][c] != mejor[i - 1][c]:          # el envío i marcó la diferencia
            elegidos.append(i - 1)
            c -= pesos[i - 1]
    return mejor[n][capacidad], sorted(elegidos)

pesos   = [12, 7, 11, 8, 9]
valores = [40, 24, 35, 26, 30]
print(mochila_01(pesos, valores, 15))   # (50, [1, 3])  → E2 + E4: peso 15, valor 50 €

Puntos que conviene digerir despacio:

  • La respuesta óptima es E2 + E4 (peso 7+8 = 15, valor 50 €). Fíjate en que no incluye E1, el envío individual más valioso: cargarlo (peso 12) solo dejaría 3 unidades libres, insuficientes para cualquier otro.
  • El coste es Θ(n·C) en tiempo y espacio (n envíos, C de capacidad). Para n = 5, C = 15 es una tabla de 96 celdas; para n = 1.000 y C = 100.000 son 10⁸ celdas — grande pero polinómico en apariencia. Guardad este matiz: volveremos a él en el apartado de NP-dureza.
  • La reconstrucción hacia atrás es la misma técnica que usamos en 01-03 para recuperar la ruta de coste mínimo en la cuadrícula: la tabla guarda valores, y las decisiones se deducen comparando celdas.

El problema del viajante (TSP): ordenar la ruta del repartidor

El problema en Rutalia. Un repartidor sale del depósito, visita 9 puntos de entrega exactamente una vez cada uno y regresa al depósito. ¿En qué orden debe visitarlos para minimizar los kilómetros totales? Este es el Travelling Salesman Problem (TSP), probablemente el problema combinatorio más famoso del mundo.

Definamos la instancia concreta que usaremos durante el resto del módulo (la resolveremos por fuerza bruta hoy, por branch and bound en 02-03 y con metaheurísticas en 02-04 y 02-05, comparando resultados). Cada punto tiene coordenadas en km sobre la cuadrícula de la ciudad (la misma cuadrícula de 01-03), y usamos distancia en línea recta como simplificación:

import math

PUNTOS = {
    "DEP": (0, 0),                     # depósito central de Rutalia
    "A": (2, 9), "B": (5, 4), "C": (7, 8), "D": (1, 5),
    "E": (8, 2), "F": (4, 7), "G": (9, 6), "H": (3, 1), "I": (6, 10),
}
NOMBRES = list(PUNTOS)                 # ["DEP", "A", ..., "I"]

def distancia(a, b):
    (x1, y1), (x2, y2) = PUNTOS[a], PUNTOS[b]
    return math.hypot(x1 - x2, y1 - y2)

# Matriz de distancias: D[i][j] = km entre el punto i y el j
D = [[distancia(a, b) for b in NOMBRES] for a in NOMBRES]

Formulación. Una solución es una permutación de los 9 puntos de entrega (el depósito fija el inicio y el final). El coste de una ruta es la suma de distancias consecutivas, cerrando el ciclo de vuelta al depósito. Hay 9! = 362.880 permutaciones. Nota al margen: en un tour cerrado cada ruta y su inversa miden lo mismo, así que en realidad hay 9!/2 rutas distintas; no explotaremos ese detalle en el código para mantenerlo simple.

Fuerza bruta. Con 9 puntos aún podemos permitirnos el lujo de mirarlas todas:

from itertools import permutations

def longitud_ruta(ruta):
    """Ruta = tupla de índices empezando por 0 (DEP). Suma el ciclo completo."""
    total = 0.0
    for i in range(len(ruta)):
        j = (i + 1) % len(ruta)        # el último tramo vuelve al depósito
        total += D[ruta[i]][ruta[j]]
    return total

def tsp_fuerza_bruta():
    mejor_ruta, mejor_km = None, float("inf")
    for perm in permutations(range(1, len(NOMBRES))):   # permuta los puntos 1..9
        ruta = (0,) + perm                               # el depósito siempre primero
        km = longitud_ruta(ruta)
        if km < mejor_km:
            mejor_km, mejor_ruta = km, ruta
    return mejor_km, [NOMBRES[i] for i in mejor_ruta]

print(tsp_fuerza_bruta())
# (35.22, ['DEP', 'D', 'A', 'F', 'I', 'C', 'G', 'E', 'B', 'H'])

El óptimo es 35,22 km, con la ruta DEP → D → A → F → I → C → G → E → B → H → DEP (existe otra ruta empatada que intercambia el orden de A y F; los empates son habituales en instancias geométricas). En un portátil corriente, Python evalúa las 362.880 permutaciones en unos pocos segundos. Pero repasa la tabla de la sección 2: con 15 puntos de entrega serían horas; con 20, siglos. Y una furgoneta real de Rutalia hace 60-120 paradas al día. La fuerza bruta nos sirve hoy para dos cosas: entender el problema y darnos la respuesta correcta de esta instancia (35,22 km), que será la vara de medir de los algoritmos de las tres próximas lecciones.

Bin packing: ¿cuántas furgonetas necesito?

El problema en Rutalia. Hoy hay 12 pedidos con pesos [6, 5, 8, 3, 7, 4, 2, 9, 5, 4, 6, 3] y todas las furgonetas cargan como máximo 15. ¿Cuál es el mínimo número de furgonetas para llevarlo todo? Esto es bin packing: empaquetar objetos en el mínimo número de contenedores de capacidad fija.

A diferencia de la mochila (un contenedor, maximizar valor), aquí hay que cubrir todos los objetos minimizando contenedores. Es NP-duro, pero admite heurísticas voraces sencillas con calidad demostrable. La más usada es First Fit Decreasing (FFD): ordena los pedidos de mayor a menor y coloca cada uno en la primera furgoneta donde quepa (abriendo una nueva si no cabe en ninguna):

def first_fit_decreasing(pesos, capacidad):
    furgonetas = []                          # cada furgoneta = lista de pesos cargados
    for peso in sorted(pesos, reverse=True): # primero los pedidos grandes
        for carga in furgonetas:
            if sum(carga) + peso <= capacidad:
                carga.append(peso)           # cabe en una furgoneta ya abierta
                break
        else:                                # el else del for: no cupo en ninguna
            furgonetas.append([peso])        # abrimos furgoneta nueva
    return furgonetas

pedidos = [6, 5, 8, 3, 7, 4, 2, 9, 5, 4, 6, 3]
for i, f in enumerate(first_fit_decreasing(pedidos, 15), 1):
    print(f"Furgoneta {i}: {f}  (carga {sum(f)}/15)")
# Furgoneta 1: [9, 6]           (carga 15/15)
# Furgoneta 2: [8, 7]           (carga 15/15)
# Furgoneta 3: [6, 5, 4]        (carga 15/15)
# Furgoneta 4: [5, 4, 3, 3]     (carga 15/15)
# Furgoneta 5: [2]              (carga 2/15)

FFD usa 5 furgonetas. ¿Es óptimo? La suma total de pesos es 62, y 62 / 15 = 4,13..., así que como mínimo hacen falta 5 furgonetas (4 furgonetas cargarían a lo sumo 60). Esa cuenta rápida — coste de la solución ≥ suma/capacidad — es nuestra primera cota inferior, un concepto que será protagonista absoluto en 02-03. Aquí la heurística coincide con la cota, y por tanto sabemos que es óptima sin haber explorado nada. Cuando no coinciden, queda una franja de incertidumbre; para FFD está demostrado que nunca usa más de 11/9 · ÓPTIMO + 6/9 contenedores, una garantía de aproximación: quizá no óptimo, pero nunca un desastre.

Algoritmos voraces: cuándo brillan y cuándo fallan

FFD es un ejemplo de algoritmo voraz (greedy): construye la solución paso a paso tomando en cada momento la decisión localmente más prometedora, sin reconsiderarla jamás. Baratos (normalmente Θ(n log n) por la ordenación) y fáciles de escribir, los voraces son la primera tentación ante cualquier problema combinatorio. La pregunta crítica es: ¿cuándo la mejor decisión local lleva al óptimo global?

Cuándo funcionan: mochila fraccionaria

Si los envíos se pudieran partir (mercancía a granel: arena, paquetería consolidada por kilos), el voraz por densidad valor/peso es óptimo demostrable: llena la furgoneta con el mejor €/kg, luego el siguiente, y parte el último que no quepa entero.

def mochila_fraccionaria(pesos, valores, capacidad):
    orden = sorted(range(len(pesos)),
                   key=lambda i: valores[i] / pesos[i], reverse=True)
    total, libre = 0.0, capacidad
    for i in orden:
        llevar = min(pesos[i], libre)        # entero si cabe; si no, la fracción
        total += valores[i] * (llevar / pesos[i])
        libre -= llevar
        if libre == 0:
            break
    return total

print(mochila_fraccionaria([12, 7, 11, 8, 9], [40, 24, 35, 26, 30], 15))  # 51.0

El argumento de optimalidad (un argumento de intercambio): si una solución óptima llevara un kilo de mercancía peor pudiendo llevar uno mejor, intercambiarlos la mejoraría — contradicción. La divisibilidad hace que ese intercambio siempre sea posible.

Cuándo funcionan: cambio de monedas canónico

Devolver 68 céntimos con monedas de euro {50, 20, 10, 5, 2, 1} de forma voraz (siempre la moneda más grande posible) da 50+10+5+2+1 = 5 monedas, y es óptimo. Los sistemas monetarios reales están diseñados para que el voraz funcione (se llaman sistemas canónicos).

Cuándo fallan: mochila 0/1

Volvamos a la furgoneta indivisible, con este contraejemplo mínimo (capacidad 10):

Envío Peso Valor Densidad €/kg
X 6 48 8,0
Y 5 35 7,0
Z 5 35 7,0

El voraz por densidad carga X (la mejor densidad)… y ya no caben ni Y ni Z (quedan 4 de capacidad). Resultado: 48 €. El óptimo es Y+Z: 70 €. La decisión localmente perfecta arruinó el global, porque al no poder partir envíos, elegir X bloquea la capacidad restante. Curiosamente, en nuestra instancia de 5 envíos el voraz por densidad acierta: toma E2 (densidad 3,43), descarta E1 y E5 porque ya no caben, y remata con E4 → E2+E4 = 50 €, el óptimo. Moraleja: que el voraz acierte en una instancia no demuestra nada; que falle en una (como X/Y/Z) demuestra que no es correcto en general.

Cuándo fallan: monedas no canónicas

Con el sistema {1, 3, 4} y cantidad 6, el voraz da 4+1+1 (3 monedas); el óptimo es 3+3 (2 monedas). Mismo algoritmo, otro sistema, resultado subóptimo — la corrección de un voraz depende finamente de la estructura del problema, no de la idea general.

Resumen operativo: un voraz es un candidato a solución, no una solución. Úsalo si (a) puedes demostrar que es óptimo (intercambio, matroides), (b) tiene garantía de aproximación conocida (como FFD), o (c) solo necesitas una solución inicial decente — de hecho, así lo usaremos en 02-03 para arrancar branch and bound con una buena cota.

NP-dureza para ingenieros: ¿exacto o aproximado?

Mochila 0/1, TSP y bin packing son NP-duros. Sin entrar en el formalismo (clases NP, reducciones — no lo necesitamos aquí), lo que significa para ti como ingeniero es esto:

  • Nadie conoce un algoritmo que resuelva todas sus instancias en tiempo polinómico, y la conjetura dominante (P ≠ NP) es que no existe. No es que "aún no se nos haya ocurrido": hay un premio de un millón de dólares esperando desde hace décadas.
  • No significa que toda instancia sea intratable. Nuestra mochila se resolvió exacta con PD en Θ(n·C) — el truco es que ese coste depende del valor numérico de la capacidad, no solo del número de objetos (se llama coste pseudopolinómico: si C tiene 15 dígitos, estás perdido, pero con capacidades moderadas la PD vuela). Y el TSP de 10 nodos cayó por fuerza bruta.
  • La decisión práctica ante un problema NP-duro sigue más o menos este árbol:
flowchart TD
    A["Problema combinatorio NP-duro"] --> B{"¿Instancia pequeña?<br/>(según el problema:<br/>TSP ≲ 15-20, subconjuntos ≲ 25)"}
    B -- "Sí" --> C["Exacto por enumeración<br/>o mejor: con poda (02-03)"]
    B -- "No" --> D{"¿Tiene estructura explotable?<br/>(capacidades pequeñas,<br/>casos particulares)"}
    D -- "Sí" --> E["Exacto especializado:<br/>PD pseudopolinómica,<br/>solvers de PLE"]
    D -- "No" --> F{"¿Necesitas garantía<br/>de calidad?"}
    F -- "Sí" --> G["Algoritmo de aproximación<br/>con cota demostrada (p. ej. FFD)"]
    F -- "No" --> H["Metaheurísticas:<br/>genéticos (02-04), ACO (02-05)"]
  • Las cotas son tu red de seguridad. Aunque renuncies al óptimo, calcula siempre una cota (como suma/capacidad en bin packing): te dice cuánto puedes estar perdiendo. "Mi heurística da 5 y la cota inferior es 5" es un certificado de optimalidad gratis; "da 9 y la cota es 5" es una invitación a seguir trabajando.

Errores Comunes y Consejos

  • Subestimar el factorial. "Solo son 20 paradas" suena inocente; son 2,4 · 10¹⁸ órdenes posibles. Antes de escribir itertools.permutations, calcula math.factorial(n) y mira cuántos dígitos tiene.
  • Confiar en un voraz sin contraejemplo buscado. Probarlo en 3 instancias y que acierte no es una demostración. Dedica cinco minutos a intentar romperlo (instancias pequeñas, valores extremos); si no lo consigues, busca si el problema tiene resultado teórico conocido.
  • Olvidar el retorno al depósito en el TSP. El error clásico es sumar solo los tramos de ida y elegir una ruta que acaba lejísimos del depósito. Nuestro longitud_ruta cierra el ciclo con el índice (i + 1) % len(ruta).
  • Confundir mochila con bin packing. Mochila: un contenedor, elegir qué entra, maximizar valor. Bin packing: todos los objetos entran, minimizar contenedores. Aplicar la PD de la mochila al bin packing no tiene sentido.
  • Ignorar que la PD de la mochila es pseudopolinómica. Con capacidad 10⁹ la tabla no cabe en memoria. En ese caso: reescalar unidades (¿de verdad necesitas precisión de gramos?), o cambiar de técnica.
  • Consejo: guarda siempre la mejor solución conocida y su cota. Todo lo que haremos en las próximas tres lecciones gira en torno a estrechar la distancia entre ambas.

Ejercicios

  1. Mochila a mano. Furgoneta de capacidad 10; envíos con (peso, valor): E1 (5, 21), E2 (4, 16), E3 (3, 12), E4 (6, 22). (a) Construye la tabla de PD mejor[i][c] a mano (5 filas × 11 columnas) y encuentra el valor óptimo y los envíos elegidos. (b) ¿Qué habría hecho el voraz por densidad? ¿Acierta?

  2. Cota inferior de bin packing. Pedidos de pesos [9, 8, 8, 7, 6, 6, 5, 5, 4, 2], capacidad 15. (a) Calcula la cota inferior ⌈suma/capacidad⌉. (b) Ejecuta FFD a mano. (c) ¿Puedes certificar que FFD es óptimo aquí? Si FFD no alcanza la cota, ¿significa eso que FFD falló?

  3. Romper al voraz del TSP. El voraz natural del TSP es "vecino más cercano": desde cada punto, ir siempre al punto no visitado más próximo. Prográmalo para nuestra instancia de 10 puntos (usa PUNTOS y D de la lección, empezando en DEP) y compara sus km con el óptimo de 35,22 km. ¿Qué porcentaje de sobrecoste tiene?

Soluciones

Ejercicio 1. (a) La última celda de la tabla da mejor[4][10] = 38, y la reconstrucción hacia atrás selecciona E4 y E2. Puedes verificarlo enumerando las combinaciones factibles (peso ≤ 10): E1+E2 → (9, 37 €), E1+E3 → (8, 33 €), E2+E3 → (7, 28 €), E2+E4 → (10, 38 €), E3+E4 → (9, 34 €); E1+E4 y cualquier trío exceden la capacidad. Óptimo: E2+E4, valor 38 € (llena la furgoneta exactamente). (b) Densidades: E1 = 4,2; E2 = 4,0; E3 = 4,0; E4 ≈ 3,67. El voraz carga E1 (quedan 5 de capacidad), después E2 (quedan 1), y ya no cabe nada más → E1+E2 = 37 €. Falla por 1 €: prefirió la densidad de E1 y perdió la combinación E2+E4 que aprovecha la capacidad al 100 %. Un fallo pequeño, pero fallo: el voraz no es correcto para la mochila 0/1.

Ejercicio 2. (a) Suma = 60; ⌈60/15⌉ = 4. (b) FFD (ya ordenados de mayor a menor): 9→F1; 8→F2; 8→F3; 7→F2 (8+7=15); 6→F1 (9+6=15); 6→F3 (8+6=14); 5→F4; 5→F4 (10); 4→F4 (14); 2→F4 (16 no cabe)→F3 (14+2=16 no cabe)→F1, F2 llenas→ F5: [2]. Resultado: 5 furgonetas. (c) La cota dice ≥ 4 y FFD da 5: no podemos certificar optimalidad con esta cota. Y no, tampoco significa que FFD haya fallado: puede que ninguna solución con 4 furgonetas exista (la cota inferior no siempre es alcanzable). De hecho aquí sí existe: [9,6] [8,7] [8,5,2] [6,5,4] = 4 furgonetas llenando 15+15+15+15 = 60. Así que FFD sí quedó una furgoneta por encima del óptimo — coherente con su garantía 11/9·OPT+6/9 ≈ 5,55. Lección doble: las cotas acotan, no deciden; y las heurísticas con garantía pueden aun así dejarse margen.

Ejercicio 3.

def vecino_mas_cercano(inicio=0):
    ruta, visitados = [inicio], {inicio}
    while len(ruta) < len(NOMBRES):
        actual = ruta[-1]
        siguiente = min((j for j in range(len(NOMBRES)) if j not in visitados),
                        key=lambda j: D[actual][j])
        ruta.append(siguiente)
        visitados.add(siguiente)
    return ruta, longitud_ruta(tuple(ruta))

ruta, km = vecino_mas_cercano()
print([NOMBRES[i] for i in ruta], round(km, 2))
# ['DEP', 'H', 'B', 'F', 'A', 'D', 'C', 'I', 'G', 'E'] 43.1

Desde DEP el más cercano es H (3,2 km), luego B (3,6), luego F (3,2), luego A (2,8)… El voraz construye un principio excelente y un final caro: los últimos puntos quedan "huérfanos" y obligan a tramos largos (D→C de 6,7 km) más un retorno al depósito de 8,2 km. Total: 43,1 km, un 22 % por encima del óptimo de 35,22 km. Es el patrón general del vecino más cercano: razonable como solución inicial (lo reutilizaremos como cota superior de arranque en 02-03), inaceptable como respuesta final cuando los kilómetros cuestan dinero.

Conclusión

Hemos puesto nombre y apellidos a las decisiones discretas de Rutalia: mochila 0/1 (qué cargar — resuelta exacta con la PD de 01-03), TSP (en qué orden repartir — resuelto por fuerza bruta en nuestra instancia de 10 puntos, con óptimo de 35,22 km que ya no olvidaremos) y bin packing (cuántas furgonetas — atacado con la heurística FFD y certificado con una cota inferior). Por el camino aprendimos que el espacio combinatorio explota (2ⁿ, n!), que los voraces son óptimos solo cuando la estructura del problema lo permite y traicioneros cuando no, y que la NP-dureza no es una sentencia de muerte sino una instrucción de uso: exacto cuando se pueda, aproximado con cotas cuando no. La fuerza bruta del TSP miró 362.880 rutas para quedarse con una; en la próxima lección aprenderemos a no mirar la inmensa mayoría de ellas sin perder la garantía de óptimo: backtracking para descartar lo infactible y branch and bound para descartar lo que ya no puede ganar. Las cotas que hoy usamos para evaluar soluciones pasarán a dirigir la búsqueda.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados