El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algorismes d'Optimització Combinatòria

Següent ►
►

A la lliçó anterior, Rutalia va decidir quantes hores de furgoneta i de bici contractar: variables contínues, regió factible suau, solver exacte en mil·lisegons. Però la majoria de les decisions diàries del magatzem no són així. Quins paquets carrego en aquesta furgoneta de 100 kg? En quin ordre visita el repartidor les seves 10 adreces? Quantes furgonetes necessito, com a mínim, per treure totes les comandes d'avui? Aquí no hi ha fraccions: cada paquet hi va o no hi va, cada adreça ocupa una posició o una altra a la ruta. L'espai de solucions és discret i, sobretot, explosiu. Aquesta lliçó presenta l'optimització combinatòria: els seus tres problemes canònics en versió Rutalia (motxilla, viatjant i bin packing), quan un algorisme voraç n'hi ha prou i quan ens enganya, i què significa a la pràctica que un problema sigui NP-dur.

Contingut

  1. Què fa "combinatòria" l'optimització
  2. L'explosió combinatòria, en números
  3. La motxilla 0/1: carregar una furgoneta
  4. El problema del viatjant (TSP): ordenar la ruta del repartidor
  5. Bin packing: quantes furgonetes necessito?
  6. Algorismes voraços: quan brillen i quan fallen
  7. NP-duresa per a enginyers: exacte o aproximat?

Què fa "combinatòria" l'optimització

Un problema d'optimització és combinatori quan les seves solucions són objectes discrets — subconjunts, permutacions, assignacions — en lloc de nombres reals. Les tres peces de 02-01 continuen aquí, però canvien de forma:

Peça En PL (02-01) En optimització combinatòria
Variables de decisió Nombres reals (x = 10,5 hores) Decisions sí/no, ordres, agrupacions
Espai de solucions Polígon continu (infinits punts, però "suau") Conjunt finit però gegantí de combinacions
Eina geomètrica L'òptim és en un vèrtex No hi ha geometria que ens salvi: cal cercar

La ironia és deliciosa: l'espai continu era infinit i el resolíem exacte en mil·lisegons; l'espai discret és finit i sovint no podem ni somiar a recórrer-lo. La raó és que "finit" i "abastable" no són el mateix.

L'explosió combinatòria, en números

Recuperem la taula de jerarquies de 01-01, ara aplicada a espais de solucions. Suposa una màquina capaç d'avaluar 100 milions de solucions per segon (10⁸, generosa per a Python):

n Subconjunts (2ⁿ) Temps Permutacions (n!) Temps
10 1.024 instantani 3.628.800 0,04 s
15 32.768 instantani ≈ 1,3 · 10¹² ≈ 3,6 hores
20 ≈ 10⁶ 0,01 s ≈ 2,4 · 10¹⁸ ≈ 770 anys
30 ≈ 10⁹ 10 s ≈ 2,7 · 10³² ≈ 8 · 10¹⁶ anys
50 ≈ 10¹⁵ 130 dies ≈ 3 · 10⁶⁴ edat de l'univers × 10⁴⁷

Dues lectures pràctiques:

  • Triar subconjunts (quins paquets carrego?) creix com 2ⁿ: brutal, però aguanta fins a n ≈ 25-30 per força bruta.
  • Triar ordres (en quina seqüència reparteixo?) creix com n!: es mor entre n = 12 i n = 15.

Això explica l'estructura de la resta del mòdul: força bruta avui (per entendre els problemes), poda intel·ligent a 02-03 (per arribar més lluny amb garantia d'òptim) i metaheurístiques a 02-04/02-05 (per a quan ni la poda no basta).

La motxilla 0/1: carregar una furgoneta

El problema a Rutalia. Una furgoneta admet 15 unitats de càrrega (pes normalitzat). Hi ha 5 enviaments pendents; cadascun té un pes i un valor (el que Rutalia factura per lliurar-lo avui). Quin subconjunt carrego per maximitzar la facturació sense excedir la capacitat?

Enviament Pes Valor (€)
E1 12 40
E2 7 24
E3 11 35
E4 8 26
E5 9 30

Formulació. Variables binàries xᵢ ∈ {0, 1} (carrego o no l'enviament i). Maximitzar Σ valorᵢ·xᵢ subjecte a Σ pesᵢ·xᵢ ≤ 15. És exactament una programació lineal entera com les de 02-01 — amb la restricció extra que les variables només valen 0 o 1. D'aquí el nom motxilla 0/1 (0/1 knapsack): cada objecte entra sencer o no entra.

Solució per programació dinàmica. Aquí collim el que vam sembrar a 01-03: el problema té subproblemes solapats i subestructura òptima. Definim millor[i][c] = valor màxim usant només els primers i enviaments amb capacitat c. Per a cada enviament només hi ha dues opcions — portar-lo o no — i totes dues remeten a subproblemes més petits:

def motxilla_01(pesos, valors, capacitat):
    n = len(pesos)
    # millor[i][c] = valor màxim amb els enviaments 0..i-1 i capacitat c
    millor = [[0] * (capacitat + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        pes, valor = pesos[i - 1], valors[i - 1]
        for c in range(capacitat + 1):
            millor[i][c] = millor[i - 1][c]        # opció A: no carregar l'enviament i
            if pes <= c:                            # opció B: carregar-lo (si hi cap)
                amb_ell = millor[i - 1][c - pes] + valor
                millor[i][c] = max(millor[i][c], amb_ell)

    # Reconstrucció de la solució (com a 01-03: recórrer la taula cap enrere)
    triats, c = [], capacitat
    for i in range(n, 0, -1):
        if millor[i][c] != millor[i - 1][c]:        # l'enviament i va marcar la diferència
            triats.append(i - 1)
            c -= pesos[i - 1]
    return millor[n][capacitat], sorted(triats)

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

Punts que convé pair a poc a poc:

  • La resposta òptima és E2 + E4 (pes 7+8 = 15, valor 50 €). Fixa't que no inclou E1, l'enviament individual més valuós: carregar-lo (pes 12) només deixaria 3 unitats lliures, insuficients per a cap altre.
  • El cost és Θ(n·C) en temps i espai (n enviaments, C de capacitat). Per a n = 5, C = 15 és una taula de 96 cel·les; per a n = 1.000 i C = 100.000 són 10⁸ cel·les — gran però polinòmic en aparença. Guardeu aquest matís: hi tornarem a l'apartat de NP-duresa.
  • La reconstrucció cap enrere és la mateixa tècnica que vam usar a 01-03 per recuperar la ruta de cost mínim a la quadrícula: la taula guarda valors, i les decisions es dedueixen comparant cel·les.

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

El problema a Rutalia. Un repartidor surt del dipòsit, visita 9 punts de lliurament exactament una vegada cadascun i torna al dipòsit. En quin ordre els ha de visitar per minimitzar els quilòmetres totals? Aquest és el Travelling Salesman Problem (TSP), probablement el problema combinatori més famós del món.

Definim la instància concreta que usarem durant la resta del mòdul (la resoldrem per força bruta avui, per branch and bound a 02-03 i amb metaheurístiques a 02-04 i 02-05, comparant resultats). Cada punt té coordenades en km sobre la quadrícula de la ciutat (la mateixa quadrícula de 01-03), i usem distància en línia recta com a simplificació:

import math

PUNTS = {
    "DEP": (0, 0),                     # dipòsit 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),
}
NOMS = list(PUNTS)                     # ["DEP", "A", ..., "I"]

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

# Matriu de distàncies: D[i][j] = km entre el punt i i el j
D = [[distancia(a, b) for b in NOMS] for a in NOMS]

Formulació. Una solució és una permutació dels 9 punts de lliurament (el dipòsit fixa l'inici i el final). El cost d'una ruta és la suma de distàncies consecutives, tancant el cicle de tornada al dipòsit. Hi ha 9! = 362.880 permutacions. Nota al marge: en un tour tancat cada ruta i la seva inversa mesuren el mateix, així que en realitat hi ha 9!/2 rutes diferents; no explotarem aquest detall al codi per mantenir-lo simple.

Força bruta. Amb 9 punts encara ens podem permetre el luxe de mirar-les totes:

from itertools import permutations

def longitud_ruta(ruta):
    """Ruta = tupla d'índexs començant per 0 (DEP). Suma el cicle complet."""
    total = 0.0
    for i in range(len(ruta)):
        j = (i + 1) % len(ruta)        # el darrer tram torna al dipòsit
        total += D[ruta[i]][ruta[j]]
    return total

def tsp_forca_bruta():
    millor_ruta, millor_km = None, float("inf")
    for perm in permutations(range(1, len(NOMS))):   # permuta els punts 1..9
        ruta = (0,) + perm                            # el dipòsit sempre primer
        km = longitud_ruta(ruta)
        if km < millor_km:
            millor_km, millor_ruta = km, ruta
    return millor_km, [NOMS[i] for i in millor_ruta]

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

L'òptim és 35,22 km, amb la ruta DEP → D → A → F → I → C → G → E → B → H → DEP (existeix una altra ruta empatada que intercanvia l'ordre d'A i F; els empats són habituals en instàncies geomètriques). En un portàtil corrent, Python avalua les 362.880 permutacions en uns pocs segons. Però repassa la taula de la secció 2: amb 15 punts de lliurament serien hores; amb 20, segles. I una furgoneta real de Rutalia fa 60-120 parades al dia. La força bruta ens serveix avui per a dues coses: entendre el problema i donar-nos la resposta correcta d'aquesta instància (35,22 km), que serà la vara de mesurar dels algorismes de les tres properes lliçons.

Bin packing: quantes furgonetes necessito?

El problema a Rutalia. Avui hi ha 12 comandes amb pesos [6, 5, 8, 3, 7, 4, 2, 9, 5, 4, 6, 3] i totes les furgonetes carreguen com a màxim 15. Quin és el mínim nombre de furgonetes per portar-ho tot? Això és el bin packing: empaquetar objectes en el mínim nombre de contenidors de capacitat fixa.

A diferència de la motxilla (un contenidor, maximitzar valor), aquí cal cobrir tots els objectes minimitzant contenidors. És NP-dur, però admet heurístiques voraces senzilles amb qualitat demostrable. La més usada és First Fit Decreasing (FFD): ordena les comandes de més gran a més petita i col·loca cadascuna a la primera furgoneta on càpiga (obrint-ne una de nova si no cap en cap):

def first_fit_decreasing(pesos, capacitat):
    furgonetes = []                          # cada furgoneta = llista de pesos carregats
    for pes in sorted(pesos, reverse=True):  # primer les comandes grans
        for carrega in furgonetes:
            if sum(carrega) + pes <= capacitat:
                carrega.append(pes)          # cap en una furgoneta ja oberta
                break
        else:                                # l'else del for: no cabia enlloc
            furgonetes.append([pes])         # obrim furgoneta nova
    return furgonetes

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

FFD usa 5 furgonetes. És òptim? La suma total de pesos és 62, i 62 / 15 = 4,13..., així que com a mínim calen 5 furgonetes (4 furgonetes carregarien com a molt 60). Aquest compte ràpid — cost de la solució ≥ suma/capacitat — és la nostra primera fita inferior, un concepte que serà protagonista absolut a 02-03. Aquí l'heurística coincideix amb la fita, i per tant sabem que és òptima sense haver explorat res. Quan no coincideixen, queda una franja d'incertesa; per a FFD està demostrat que mai no usa més d'11/9 · ÒPTIM + 6/9 contenidors, una garantia d'aproximació: potser no òptim, però mai un desastre.

Algorismes voraços: quan brillen i quan fallen

FFD és un exemple d'algorisme voraç (greedy): construeix la solució pas a pas prenent en cada moment la decisió localment més prometedora, sense reconsiderar-la mai. Barats (normalment Θ(n log n) per l'ordenació) i fàcils d'escriure, els voraços són la primera temptació davant de qualsevol problema combinatori. La pregunta crítica és: quan la millor decisió local porta a l'òptim global?

Quan funcionen: motxilla fraccionària

Si els enviaments es poguessin partir (mercaderia a granel: sorra, paqueteria consolidada per quilos), el voraç per densitat valor/pes és òptim demostrable: omple la furgoneta amb el millor €/kg, després el següent, i parteix el darrer que no hi càpiga sencer.

def motxilla_fraccionaria(pesos, valors, capacitat):
    ordre = sorted(range(len(pesos)),
                   key=lambda i: valors[i] / pesos[i], reverse=True)
    total, lliure = 0.0, capacitat
    for i in ordre:
        portar = min(pesos[i], lliure)       # sencer si hi cap; si no, la fracció
        total += valors[i] * (portar / pesos[i])
        lliure -= portar
        if lliure == 0:
            break
    return total

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

L'argument d'optimalitat (un argument d'intercanvi): si una solució òptima portés un quilo de mercaderia pitjor podent portar-ne un de millor, intercanviar-los la milloraria — contradicció. La divisibilitat fa que aquest intercanvi sempre sigui possible.

Quan funcionen: canvi de monedes canònic

Tornar 68 cèntims amb monedes d'euro {50, 20, 10, 5, 2, 1} de manera voraç (sempre la moneda més gran possible) dona 50+10+5+2+1 = 5 monedes, i és òptim. Els sistemes monetaris reals estan dissenyats perquè el voraç funcioni (s'anomenen sistemes canònics).

Quan fallen: motxilla 0/1

Tornem a la furgoneta indivisible, amb aquest contraexemple mínim (capacitat 10):

Enviament Pes Valor Densitat €/kg
X 6 48 8,0
Y 5 35 7,0
Z 5 35 7,0

El voraç per densitat carrega X (la millor densitat)… i ja no hi caben ni Y ni Z (queden 4 de capacitat). Resultat: 48 €. L'òptim és Y+Z: 70 €. La decisió localment perfecta va arruïnar el global, perquè en no poder partir enviaments, triar X bloqueja la capacitat restant. Curiosament, en la nostra instància de 5 enviaments el voraç per densitat encerta: pren E2 (densitat 3,43), descarta E1 i E5 perquè ja no hi caben, i remata amb E4 → E2+E4 = 50 €, l'òptim. Moralitat: que el voraç encerti en una instància no demostra res; que falli en una (com X/Y/Z) demostra que no és correcte en general.

Quan fallen: monedes no canòniques

Amb el sistema {1, 3, 4} i quantitat 6, el voraç dona 4+1+1 (3 monedes); l'òptim és 3+3 (2 monedes). Mateix algorisme, un altre sistema, resultat subòptim — la correcció d'un voraç depèn finament de l'estructura del problema, no de la idea general.

Resum operatiu: un voraç és un candidat a solució, no una solució. Usa'l si (a) pots demostrar que és òptim (intercanvi, matroides), (b) té garantia d'aproximació coneguda (com FFD), o (c) només necessites una solució inicial decent — de fet, així el farem servir a 02-03 per engegar branch and bound amb una bona fita.

NP-duresa per a enginyers: exacte o aproximat?

Motxilla 0/1, TSP i bin packing són NP-durs. Sense entrar en el formalisme (classes NP, reduccions — no ens cal aquí), el que significa per a tu com a enginyer és això:

  • Ningú no coneix un algorisme que resolgui totes les seves instàncies en temps polinòmic, i la conjectura dominant (P ≠ NP) és que no existeix. No és que "encara no se'ns hagi acudit": hi ha un premi d'un milió de dòlars esperant des de fa dècades.
  • No significa que tota instància sigui intractable. La nostra motxilla es va resoldre exacta amb PD en Θ(n·C) — el truc és que aquest cost depèn del valor numèric de la capacitat, no només del nombre d'objectes (se'n diu cost pseudopolinòmic: si C té 15 dígits, estàs perdut, però amb capacitats moderades la PD vola). I el TSP de 10 nodes va caure per força bruta.
  • La decisió pràctica davant d'un problema NP-dur segueix més o menys aquest arbre:
flowchart TD
    A["Problema combinatori NP-dur"] --> B{"Instància petita?<br/>(segons el problema:<br/>TSP ≲ 15-20, subconjunts ≲ 25)"}
    B -- "Sí" --> C["Exacte per enumeració<br/>o millor: amb poda (02-03)"]
    B -- "No" --> D{"Té estructura explotable?<br/>(capacitats petites,<br/>casos particulars)"}
    D -- "Sí" --> E["Exacte especialitzat:<br/>PD pseudopolinòmica,<br/>solvers de PLE"]
    D -- "No" --> F{"Necessites garantia<br/>de qualitat?"}
    F -- "Sí" --> G["Algorisme d'aproximació<br/>amb fita demostrada (p. ex. FFD)"]
    F -- "No" --> H["Metaheurístiques:<br/>genètics (02-04), ACO (02-05)"]
  • Les fites són la teva xarxa de seguretat. Encara que renunciïs a l'òptim, calcula sempre una fita (com suma/capacitat al bin packing): et diu quant pots estar perdent. "La meva heurística dona 5 i la fita inferior és 5" és un certificat d'optimalitat gratis; "dona 9 i la fita és 5" és una invitació a continuar treballant.

Errors Comuns i Consells

  • Subestimar el factorial. "Només són 20 parades" sona innocent; són 2,4 · 10¹⁸ ordres possibles. Abans d'escriure itertools.permutations, calcula math.factorial(n) i mira quants dígits té.
  • Confiar en un voraç sense contraexemple buscat. Provar-lo en 3 instàncies i que encerti no és una demostració. Dedica cinc minuts a intentar trencar-lo (instàncies petites, valors extrems); si no ho aconsegueixes, busca si el problema té resultat teòric conegut.
  • Oblidar el retorn al dipòsit al TSP. L'error clàssic és sumar només els trams d'anada i triar una ruta que acaba lluníssim del dipòsit. El nostre longitud_ruta tanca el cicle amb l'índex (i + 1) % len(ruta).
  • Confondre motxilla amb bin packing. Motxilla: un contenidor, triar què hi entra, maximitzar valor. Bin packing: tots els objectes hi entren, minimitzar contenidors. Aplicar la PD de la motxilla al bin packing no té sentit.
  • Ignorar que la PD de la motxilla és pseudopolinòmica. Amb capacitat 10⁹ la taula no cap a la memòria. En aquest cas: reescalar unitats (de debò necessites precisió de grams?), o canviar de tècnica.
  • Consell: guarda sempre la millor solució coneguda i la seva fita. Tot el que farem a les tres properes lliçons gira al voltant d'estrènyer la distància entre totes dues.

Exercicis

  1. Motxilla a mà. Furgoneta de capacitat 10; enviaments amb (pes, valor): E1 (5, 21), E2 (4, 16), E3 (3, 12), E4 (6, 22). (a) Construeix la taula de PD millor[i][c] a mà (5 files × 11 columnes) i troba el valor òptim i els enviaments triats. (b) Què hauria fet el voraç per densitat? Encerta?

  2. Fita inferior de bin packing. Comandes de pesos [9, 8, 8, 7, 6, 6, 5, 5, 4, 2], capacitat 15. (a) Calcula la fita inferior ⌈suma/capacitat⌉. (b) Executa FFD a mà. (c) Pots certificar que FFD és òptim aquí? Si FFD no arriba a la fita, significa això que FFD ha fallat?

  3. Trencar el voraç del TSP. El voraç natural del TSP és "veí més proper": des de cada punt, anar sempre al punt no visitat més pròxim. Programa'l per a la nostra instància de 10 punts (usa PUNTS i D de la lliçó, començant a DEP) i compara els seus km amb l'òptim de 35,22 km. Quin percentatge de sobrecost té?

Solucions

Exercici 1. (a) La darrera cel·la de la taula dona millor[4][10] = 38, i la reconstrucció cap enrere selecciona E4 i E2. Pots verificar-ho enumerant les combinacions factibles (pes ≤ 10): E1+E2 → (9, 37 €), E1+E3 → (8, 33 €), E2+E3 → (7, 28 €), E2+E4 → (10, 38 €), E3+E4 → (9, 34 €); E1+E4 i qualsevol trio excedeixen la capacitat. Òptim: E2+E4, valor 38 € (omple la furgoneta exactament). (b) Densitats: E1 = 4,2; E2 = 4,0; E3 = 4,0; E4 ≈ 3,67. El voraç carrega E1 (queden 5 de capacitat), després E2 (en queda 1), i ja no hi cap res més → E1+E2 = 37 €. Falla per 1 €: va preferir la densitat d'E1 i va perdre la combinació E2+E4 que aprofita la capacitat al 100 %. Un error petit, però error: el voraç no és correcte per a la motxilla 0/1.

Exercici 2. (a) Suma = 60; ⌈60/15⌉ = 4. (b) FFD (ja ordenats de més gran a més petit): 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 hi cap)→F3 (14+2=16 no hi cap)→F1, F2 plenes→ F5: [2]. Resultat: 5 furgonetes. (c) La fita diu ≥ 4 i FFD dona 5: no podem certificar optimalitat amb aquesta fita. I no, tampoc no significa que FFD hagi fallat: pot ser que no existeixi cap solució amb 4 furgonetes (la fita inferior no sempre és assolible). De fet aquí sí que existeix: [9,6] [8,7] [8,5,2] [6,5,4] = 4 furgonetes omplint 15+15+15+15 = 60. Així que FFD sí que va quedar una furgoneta per sobre de l'òptim — coherent amb la seva garantia 11/9·OPT+6/9 ≈ 5,55. Lliçó doble: les fites fiten, no decideixen; i les heurístiques amb garantia poden tot i així deixar-se marge.

Exercici 3.

def vei_mes_proper(inici=0):
    ruta, visitats = [inici], {inici}
    while len(ruta) < len(NOMS):
        actual = ruta[-1]
        seguent = min((j for j in range(len(NOMS)) if j not in visitats),
                      key=lambda j: D[actual][j])
        ruta.append(seguent)
        visitats.add(seguent)
    return ruta, longitud_ruta(tuple(ruta))

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

Des de DEP el més proper és H (3,2 km), després B (3,6), després F (3,2), després A (2,8)… El voraç construeix un principi excel·lent i un final car: els darrers punts queden "orfes" i obliguen a trams llargs (D→C de 6,7 km) més un retorn al dipòsit de 8,2 km. Total: 43,1 km, un 22 % per sobre de l'òptim de 35,22 km. És el patró general del veí més proper: raonable com a solució inicial (el reutilitzarem com a fita superior d'arrencada a 02-03), inacceptable com a resposta final quan els quilòmetres costen diners.

Conclusió

Hem posat nom i cognoms a les decisions discretes de Rutalia: motxilla 0/1 (què carregar — resolta exacta amb la PD de 01-03), TSP (en quin ordre repartir — resolt per força bruta en la nostra instància de 10 punts, amb òptim de 35,22 km que ja no oblidarem) i bin packing (quantes furgonetes — atacat amb l'heurística FFD i certificat amb una fita inferior). Pel camí hem après que l'espai combinatori explota (2ⁿ, n!), que els voraços són òptims només quan l'estructura del problema ho permet i traïdors quan no, i que la NP-duresa no és una sentència de mort sinó una instrucció d'ús: exacte quan es pugui, aproximat amb fites quan no. La força bruta del TSP va mirar 362.880 rutes per quedar-se'n una; a la propera lliçó aprendrem a no mirar la immensa majoria sense perdre la garantia d'òptim: backtracking per descartar l'infactible i branch and bound per descartar el que ja no pot guanyar. Les fites que avui usem per avaluar solucions passaran a dirigir la cerca.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats