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

Backtracking i Branch and Bound

Següent ►
►

La força bruta de la lliçó anterior va avaluar les 362.880 rutes possibles del repartidor de Rutalia per quedar-se'n una. És un malbaratament monumental: la majoria d'aquelles rutes estaven condemnades des dels primers trams, i tot i així les vam construir senceres. Aquesta lliçó ensenya a explorar l'espai de solucions sense enumerar-lo: el backtracking, que abandona una branca tan bon punt viola una restricció, i el branch and bound, que a més l'abandona quan una fita optimista demostra que ja no pot millorar el millor trobat. Són tècniques exactes — conserven la garantia d'òptim — i constitueixen el motor real dels solvers de programació entera que vam esmentar a 02-01. Al final resoldrem el mateix TSP de 10 punts de 02-02 i comptarem, amb números, quants nodes ens hem estalviat.

Contingut

  1. Explorar sense enumerar: la idea de podar
  2. L'esquema general de backtracking
  3. Exemple guiat: subconjunts que caben a la furgoneta
  4. Motxilla 0/1 per backtracking
  5. Branch and bound: podar també per qualitat
  6. Millor-primer amb un heap
  7. B&B per al TSP de Rutalia: comptant podes
  8. Els límits de l'exactitud

Explorar sense enumerar: la idea de podar

Tota solució combinatòria es pot construir per decisions parcials: carrego o no l'enviament E1, després l'E2… o bé: la primera parada és D, la segona és A… Aquestes decisions formen un arbre: l'arrel és "res decidit", cada nivell afegeix una decisió, i les fulles són solucions completes. La força bruta visita totes les fulles. L'observació clau és que sovint podem condemnar un subarbre sencer mirant-ne només l'arrel:

  • Poda de factibilitat (backtracking): si la càrrega parcial ja pesa 16 amb capacitat 15, cap extensió no serà vàlida. No cal mirar cap de les seves fulles.
  • Poda d'optimalitat (branch and bound): si el millor que aquesta branca podria arribar a donar — calculat amb una fita optimista — és pitjor que la millor solució completa que ja tinc, la branca és inútil encara que sigui factible.

Tallar un node a profunditat k en un arbre de decisions binàries elimina de cop 2^(n−k) fulles. Podar aviat és exponencialment rendible: tota l'enginyeria d'aquesta lliçó consisteix a guanyar-se el dret a podar aviat.

L'esquema general de backtracking

El backtracking és una plantilla recursiva — reconeix l'estructura de 01-03: cas base, avanç, i aquí a més desfer:

def backtracking(solucio_parcial):
    if es_completa(solucio_parcial):
        registrar(solucio_parcial)           # cas base: hem arribat a una fulla vàlida
        return
    for opcio in opcions_disponibles(solucio_parcial):
        if es_prometedora(solucio_parcial, opcio):     # ← LA PODA
            aplicar(solucio_parcial, opcio)            # decidir
            backtracking(solucio_parcial)              # explorar el subarbre
            desfer(solucio_parcial, opcio)             # retrocedir (backtrack)

Els quatre buits a omplir en cada problema:

Buit Pregunta A "carregar furgoneta" Al TSP
es_completa Ja ho he decidit tot? He considerat els n enviaments La ruta té les n parades
opcions_disponibles Què puc decidir ara? Carregar / no carregar el següent Qualsevol parada no visitada
es_prometedora Val la pena continuar? El pes no excedeix la capacitat (En B&B: la fita no supera la millor ruta)
aplicar / desfer Com avanço i retrocedeixo? Afegir/treure l'enviament Afegir/treure la parada

El desfer és el que dona nom a la tècnica: en esgotar un subarbre, retrocedim a l'estat anterior i provem l'opció següent. La pila de crides (01-03) manté el camí des de l'arrel fins al node actual; la memòria usada és només la profunditat de l'arbre, Θ(n), encara que l'arbre tingui milions de nodes.

Un apunt cultural: l'exemple pedagògic clàssic de backtracking són les N reines (col·locar N reines en un tauler N×N sense que s'ataquin), on la poda "aquesta reina ja està atacada" elimina branques enormes. L'esquema és idèntic al de dalt; nosaltres continuarem amb paquets i furgonetes, que és el que li paguen a Rutalia.

Exemple guiat: subconjunts que caben a la furgoneta

Comencem amb la versió més simple: llistar tots els subconjunts vàlids. Tres enviaments de pesos [6, 5, 4] i una furgoneta de capacitat 10. Cada nivell de l'arbre decideix sobre un enviament: branca esquerra "el carrego", branca dreta "no el carrego":

flowchart TD
    R["{ } pes 0"] -->|"carregar E1(6)"| A["{E1} pes 6"]
    R -->|"no"| B["{ } pes 0"]
    A -->|"carregar E2(5)"| C["{E1,E2} pes 11 ✂ PODA"]
    A -->|"no"| D["{E1} pes 6"]
    B -->|"carregar E2(5)"| E["{E2} pes 5"]
    B -->|"no"| F["{ } pes 0"]
    D -->|"carregar E3(4)"| G["{E1,E3} pes 10 ✔"]
    D -->|"no"| H["{E1} ✔"]
    E -->|"carregar E3(4)"| I["{E2,E3} pes 9 ✔"]
    E -->|"no"| J["{E2} ✔"]
    F -->|"carregar E3(4)"| K["{E3} ✔"]
    F -->|"no"| L["{ } ✔"]

La branca {E1, E2} mor a profunditat 2: pesa 11 > 10, així que els seus dos descendents (amb i sense E3) ni es generen. De les 2³ = 8 fulles possibles, el backtracking en visita 6. En un exemple de joguina l'estalvi és anecdòtic; amb 30 enviaments i càrregues ajustades, la mateixa poda elimina la major part dels 2³⁰ subconjunts.

def subconjunts_valids(pesos, capacitat):
    resultats = []
    seleccio = []                        # índexs d'enviaments carregats (estat compartit)

    def explorar(i, pes_actual):
        if i == len(pesos):              # cas base: decidit sobre tots els enviaments
            resultats.append(list(seleccio))
            return
        # Opció A: carregar l'enviament i — només si continua sent factible (PODA)
        if pes_actual + pesos[i] <= capacitat:
            seleccio.append(i)                       # aplicar
            explorar(i + 1, pes_actual + pesos[i])   # explorar
            seleccio.pop()                           # desfer
        # Opció B: no carregar-lo — sempre factible
        explorar(i + 1, pes_actual)

    explorar(0, 0)
    return resultats

print(subconjunts_valids([6, 5, 4], 10))
# [[0, 2], [0], [1, 2], [1], [2], []]

Detalls fins: seleccio és una sola llista que es modifica i es restaura (append/pop) — molt més barat que copiar la llista a cada crida; i la poda és a l'if de l'opció A: el subarbre infactible mai no es genera.

Motxilla 0/1 per backtracking

Per optimitzar (no només llistar), afegim el valor acumulat i recordem el millor complet vist. Usem la instància de 02-02: capacitat 15, pesos [12, 7, 11, 8, 9], valors [40, 24, 35, 26, 30], l'òptim conegut de la qual és 50 (E2+E4):

def motxilla_backtracking(pesos, valors, capacitat):
    n = len(pesos)
    millor = {"valor": 0, "seleccio": []}
    seleccio = []

    def explorar(i, pes, valor):
        if i == n:
            if valor > millor["valor"]:                # fulla: rècord?
                millor["valor"], millor["seleccio"] = valor, list(seleccio)
            return
        if pes + pesos[i] <= capacitat:                # branca "carregar" (poda factibilitat)
            seleccio.append(i)
            explorar(i + 1, pes + pesos[i], valor + valors[i])
            seleccio.pop()
        explorar(i + 1, pes, valor)                    # branca "no carregar"

    explorar(0, 0, 0)
    return millor["valor"], millor["seleccio"]

print(motxilla_backtracking([12, 7, 11, 8, 9], [40, 24, 35, 26, 30], 15))
# (50, [1, 3])

Funciona i poda l'infactible, però té un punt cec: explora branques factibles però inútils — combinacions lleugeres que mai no arribaran als 50 €. La poda de factibilitat no sap res de qualitat. Per a això necessitem la segona idea.

Branch and bound: podar també per qualitat

El branch and bound (B&B) enriqueix l'arbre amb dos números:

  • L'incumbent (fita inferior en maximització): la millor solució completa trobada fins ara. És una fita real: qualsevol cosa pitjor no interessa.
  • La fita optimista de cada node (fita superior en maximització): un càlcul ràpid del màxim que podria arribar a valer la millor fulla del seu subarbre. Ha de ser optimista de debò — mai subestimar — o podarem branques que contenien l'òptim, perdent l'exactitud.

Regla de poda: si fita_optimista(node) ≤ incumbent, el subarbre sencer es descarta. La garantia d'òptim es conserva perquè només llencem branques demostradament incapaces de millorar.

D'on surten les fites optimistes? De relaxar el problema: resoldre una versió més fàcil l'òptim de la qual sigui sempre ≥ el real. Per a la motxilla 0/1, la relaxació perfecta la coneixem de 02-02: la motxilla fraccionària (permetre partir enviaments). Es resol en Θ(n log n) amb el voraç per densitat, i el seu valor sempre iguala o supera el de la 0/1 — és el mateix problema amb menys restriccions.

def fita_fraccionaria(i, pes, valor, pesos, valors, capacitat, ordre):
    """Fita optimista: valor actual + farciment fraccionari amb els enviaments i.. pendents."""
    lliure, fita = capacitat - pes, valor
    for j in ordre:                       # ordre = índexs per densitat descendent
        if j < i:                         # ja decidit (carregat o descartat)
            continue
        if pesos[j] <= lliure:
            fita += valors[j]; lliure -= pesos[j]
        else:
            fita += valors[j] * lliure / pesos[j]   # fracció del darrer
            break
    return fita

Amb aquesta fita, el node "no he carregat res de valor i ja vaig per l'enviament 4" es poda a l'instant: ni el farciment fraccionari no arriba a l'incumbent. Aquest és el patró general de B&B: ramificar (branch) generant fills i fitar (bound) per matar-los aviat. I aquí es tanca un cercle amb 02-01: els solvers de programació lineal entera fan exactament això, usant com a fita optimista la relaxació contínua del PL — per això vam veure que l'òptim continu (62,5) sempre superava l'enter (58).

Millor-primer amb un heap

Queda una decisió de disseny: en quin ordre explorar els nodes vius? El backtracking recursiu va en profunditat (DFS implícit a la pila de crides). Però si explorem primer els nodes de millor fita optimista, trobem abans solucions bones, l'incumbent millora abans, i les podes arriben abans. És l'estratègia millor-primer (best-first), i l'estructura per implementar-la la vam sembrar a 01-04: un heap (heapq), que extreu el mínim en Θ(log n).

Estratègia Estructura Avantatge Risc
En profunditat (DFS) Pila / recursió Memòria Θ(n); arriba ràpid a fulles (incumbent primerenc) Pot cavar en branques mediocres
Millor-primer Heap de nodes per fita Explora abans el prometedor; sol expandir menys nodes Memòria: el heap pot créixer molt

A la pràctica es combinen (profunditat amb bon ordre de fills, o millor-primer amb límit de memòria). Nosaltres usarem millor-primer pur per veure el mecanisme amb claredat.

B&B per al TSP de Rutalia: comptant podes

Anem al plat fort: la instància de 10 punts de 02-02 (reutilitza PUNTS, NOMS, D i longitud_ruta d'aquella lliçó). Ara minimitzem, així que els papers s'inverteixen: l'incumbent és una fita superior (la millor ruta completa coneguda) i la fita de cada node és inferior i optimista: mai no pot sobreestimar els km que falten.

La nostra fita, senzilla però honesta: km recorreguts + l'aresta més barata que surt de cada punt encara pendent (inclòs el punt actual, que encara ha de sortir cap a algú). Cap ruta real no pot gastar menys que això a sortir de cada punt, així que mai no sobreestima. Fites més fines (com la de l'arbre d'expansió mínim sobre els pendents — concepte que formalitzarem a 03-04) poden encara més a canvi de més càlcul per node: és l'etern equilibri de B&B.

import heapq

N = len(NOMS)
# Aresta mínima sortint de cada punt (precalculada una vegada)
min_sortida = [min(D[i][j] for j in range(N) if j != i) for i in range(N)]

def fita_inferior(ruta, visitats, km):
    fita = km + min_sortida[ruta[-1]]             # el punt actual encara ha de sortir
    for j in range(N):
        if j not in visitats:
            fita += min_sortida[j]                # cada pendent sortirà almenys així
    return fita

def tsp_branch_and_bound():
    millor_km, millor_ruta = float("inf"), None
    nodes_expandits = podes = 0

    arrel = (fita_inferior([0], {0}, 0.0), 0.0, [0], frozenset({0}))
    vius = [arrel]                                 # heap ordenat per fita

    while vius:
        fita, km, ruta, visitats = heapq.heappop(vius)
        if fita >= millor_km:                      # PODA: ja no pot guanyar
            podes += 1
            continue
        nodes_expandits += 1
        if len(ruta) == N:                         # ruta completa: tancar el cicle
            total = km + D[ruta[-1]][0]
            if total < millor_km:
                millor_km, millor_ruta = total, ruta # nou incumbent → podes futures
            continue
        for j in range(N):                         # RAMIFICAR: parada següent
            if j not in visitats:
                km2 = km + D[ruta[-1]][j]
                v2 = visitats | {j}
                c2 = fita_inferior(ruta + [j], v2, km2)
                if c2 < millor_km:                 # ni encuem el condemnat
                    heapq.heappush(vius, (c2, km2, ruta + [j], v2))
                else:
                    podes += 1

    return millor_km, [NOMS[i] for i in millor_ruta], nodes_expandits, podes

print(tsp_branch_and_bound())
# (35.22, ['DEP', 'D', 'A', 'F', 'I', 'C', 'G', 'E', 'B', 'H'], ~1200, ~2800)

Lectura del codi, peça a peça:

  • Cada node viu és una tupla (fita, km, ruta, visitats). Com que heapq ordena pel primer element, el heap sempre lliura el node de menor fita inferior — millor-primer, tal qual.
  • La poda actua dues vegades: en treure un node del heap (la seva fita pot haver quedat obsoleta si l'incumbent va millorar mentre esperava) i abans d'encuar fills (no malgastem memòria en condemnats).
  • Quan una ruta es completa i millora l'incumbent, totes les branques pendents amb fita ≥ aquell valor moren en cadena. Per això trobar aviat una bona ruta accelera tant: si arrenques l'incumbent amb els 43,1 km del veí més proper (exercici 3 de 02-02) en lloc d'infinit, la poda mossega des del primer node.

Els números. En la nostra execució, l'algorisme retorna l'òptim exacte — 35,22 km, la mateixa ruta que la força bruta — després d'expandir uns 1.200 nodes i executar unes 2.800 podes (la xifra exacta varia lleugerament segons com es desempatin fites iguals). Posem-ho en perspectiva:

Mètode Nodes considerats Garantia
Força bruta (02-02) 362.880 rutes completes (≈ 986.000 nodes si comptem l'arbre sencer) Òptim
Backtracking només factibilitat ≈ 986.000 (al TSP tota ruta parcial és factible: no hi ha res a podar) Òptim
B&B millor-primer ≈ 1.200 nodes expandits Òptim

Tres ordres de magnitud menys feina, la mateixa garantia matemàtica. Fixa't a més en la fila del mig: al TSP pur el backtracking de factibilitat no poda res, perquè qualsevol permutació parcial es pot completar. La poda per fita és la que fa tota la feina — cada problema dicta quin tipus de poda té sentit.

Els límits de l'exactitud

Hem vençut l'explosió combinatòria? No: l'hem retardada. B&B continua sent exponencial en el pitjor cas; només retalla el factor amb intel·ligència. Amb bones fites, l'estat de l'art resol TSP de centenars o milers de nodes, però cada instància difícil es pot disparar, i problemes com la planificació conjunta de tota la flota de Rutalia (desenes de furgonetes × centenars de parades × finestres horàries) queden fora de l'abast exacte amb qualsevol pressupost de còmput raonable. Quan això passa, l'enginyer canvia el contracte: renuncia a la garantia d'òptim a canvi de solucions molt bones en temps predictible. Aquest és el territori de les metaheurístiques, i és exactament on anem.

Errors Comuns i Consells

  • Fites "optimistes" que no ho són. Si la teva fita inferior pot sobreestimar (p. ex., usar l'aresta mitjana en lloc de la mínima), podaràs branques que contenien l'òptim i l'algorisme retornarà brossa amb cara de resultat exacte. Verifica la propietat en paper: és impossible que una solució real costi menys que la meva fita?
  • Oblidar el desfer. Si després de la crida recursiva no restaures l'estat (seleccio.pop()), les branques següents hereten decisions fantasma. Símptoma típic: resultats que depenen de l'ordre d'exploració.
  • Copiar estat a cada node sense necessitat. ruta + [j] crea llistes noves — còmode i correcte, però en instàncies grans el cost de còpia domina. L'alternativa aplicar/desfer sobre una estructura única és més ràpida (i més delicada). Comença clar, optimitza després mesurant (01-02).
  • No sembrar l'incumbent. Arrencar amb millor = infinit malgasta les podes inicials. Un voraç barat (veí més proper, FFD…) dona un incumbent inicial que activa la poda des del minut zero. És la sinergia voraç + B&B: el voraç no garanteix res, però accelera el que sí que garanteix.
  • Fita cara que no compensa. Una fita que poda un 5 % més però costa 10 vegades més per node empitjora el total. Mesura nodes expandits × cost per node, no només nodes.
  • Consell: instrumenta sempre el teu B&B amb comptadors (nodes_expandits, podes) com hem fet aquí. Són el teu tauler de comandament: si les podes no creixen en millorar la fita, la fita nova no està aportant.

Exercicis

  1. Traça en paper. Amb capacitat 10 i enviaments (pes, valor): P1 (6, 48), P2 (5, 35), P3 (5, 35) — el contraexemple del voraç de 02-02 —, dibuixa l'arbre de backtracking (8 fulles potencials) i marca: (a) quines branques talla la poda de factibilitat; (b) quin és l'òptim. Després calcula la fita fraccionària del node arrel i del node "he descartat P1": què et diuen?

  2. Sembrar l'incumbent. Modifica tsp_branch_and_bound perquè accepti un paràmetre km_inicial (fita superior d'arrencada) i executa'l amb (a) infinit i (b) els 43,1 km del veí més proper. Compara nodes_expandits i podes en tots dos casos. Per què millora?

  3. Fita més fina. La fita min_sortida ignora que les arestes triades han de formar una ruta. Una millora barata: per a cada punt pendent, usar la mitjana de les seves dues arestes més barates en lloc d'una de sola (cada punt d'un cicle té una entrada i una sortida). Argumenta per què continua sent una fita inferior vàlida i implementa-la. Expandeix menys nodes?

Solucions

Exercici 1. (a) La poda de factibilitat talla: {P1,P2} (pes 11 > 10) abans de decidir P3, i {P1,P3} (11). Sobreviuen com a fulles: {P1} (48), {P2,P3} (70), {P2} (35), {P3} (35), {} (0) — l'òptim és {P2,P3} = 70. (b) Fita fraccionària de l'arrel: densitats 8, 7, 7 → P1 sencer (48) + P2 sencer (35, pes 11 > 10: només hi caben 4 de les seves 5 unitats) → 48 + 35·(4/5) = 76. Del node "he descartat P1": P2 + P3 = 10 de pes just → fita 70, que a més és assolible. Lectura: l'arrel promet ≤ 76 (optimista, com ha de ser). Seguim la branca "he carregat P1": amb 4 unitats lliures i P2 pendent, la seva fita és 48 + 35·(4/5) = 76; després de descartar P2, amb P3 pendent continua sent 48 + 28 = 76; i en descartar també P3, cau a 48. Si explorem primer la branca "he descartat P1" (millor-primer ho faria en estrènyer-se les fites), l'incumbent arriba de seguida a 70… i tot i així la branca de P1 sobreviu mentre prometi 76. El patró que cal retenir: les fites s'estrenyen en baixar per l'arbre, i l'incumbent mata tot el que promet un valor menor o igual que ell — aquí acaba morint tot el que promet ≤ 70.

Exercici 2.

def tsp_branch_and_bound(km_inicial=float("inf")):
    millor_km, millor_ruta = km_inicial, None
    # ... resta idèntica ...

Amb km_inicial = 43.1, els nodes la fita inferior dels quals superi 43,1 moren abans que existeixi cap incumbent propi: la poda funciona des de l'arrel. En les nostres proves, la xifra de nodes expandits baixa de manera apreciable (i la de podes primerenques puja); l'efecte és molt més dramàtic en instàncies més grans, on sense llavor el heap s'engreixa amb milers de nodes mediocres abans de la primera ruta completa. La combinació "heurística barata per a l'incumbent + B&B per al certificat" és un patró professional estàndard.

Exercici 3. Validesa: en un cicle, cada punt té exactament una aresta d'entrada i una de sortida. La suma de costos del cicle es pot escriure com Σ (entrada + sortida)/2 sobre tots els punts. Com que per a cada punt usem la mitjana de les seves dues arestes més barates, cap assignació real d'entrada/sortida no pot costar menys: la fita mai no sobreestima. Implementació: precalcula dos_min[i] = (d1 + d2) / 2 amb les dues menors distàncies de la fila D[i], i suma dos_min[j] per a cada pendent (ajustant els punts ja connectats parcialment). En ser més ajustada (més gran o igual que la d'una sola aresta), poda estrictament més: en la nostra instància, la reducció de nodes expandits és notable amb un sobrecost per node mínim. Aquest joc — invertir en fites més fines per podar més — és, portat a l'extrem amb relaxacions de PL, el que fa competitius els solvers industrials de PLE.

Conclusió

Hem convertit l'enumeració cega en una cerca amb criteri: el backtracking descarta l'infactible tan bon punt treu el cap (esquema recursiu amb aplicar/explorar/desfer, memòria lineal), i el branch and bound descarta també el factible-però-condemnat usant fites optimistes — la relaxació fraccionària a la motxilla, les arestes mínimes al TSP — amb l'estratègia millor-primer servida pel heap que vam aprendre a 01-04. El resultat al TSP de Rutalia és eloqüent: el mateix òptim de 35,22 km que va costar 362.880 avaluacions a la força bruta va caure expandint uns 1.200 nodes, sense cedir ni un mil·límetre en la garantia. Però també hem estat honestos amb el límit: l'explosió combinatòria està retardada, no vençuda, i la flota completa de Rutalia continua fora de l'abast de qualsevol mètode exacte. A la propera lliçó creuarem aquesta frontera de manera deliberada: els algorismes genètics renuncien al certificat d'optimalitat i, a canvi, troben solucions excel·lents on B&B ni tan sols pot començar. Veurem què se sent en operar sense xarxa — i com fer-ho amb criteri professional.

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