Divideix i venceràs trosseja, greedy aposta, la programació dinàmica recorda. Però hi ha problemes on res d'això no basta: problemes de restriccions, on la solució és una combinació de decisions que han de ser compatibles entre si — assignar conductors a torns, quadrar horaris, generar rutes d'inspecció vàlides — i on no hi ha recurrència ni criteri voraç que hi valgui. Per a aquests problemes existeix la quarta estratègia del mòdul: el backtracking (tornada enrere), una exploració sistemàtica de l'espai de solucions que avança decisió a decisió i, tan bon punt detecta un carreró sense sortida, desfà l'últim pas i prova una altra alternativa. És la més costosa de les quatre estratègies — el seu cost és exponencial en el pitjor cas — però, ben podada, resol problemes davant dels quals les altres arronsen les espatlles. Amb ella tancarem el mòdul comparant cara a cara les quatre estratègies de disseny.

1. La idea: explorar un arbre de decisions amb marxa enrere
2. L'esquema general: triar, explorar, desfer
3. Exemple RutaBus: assignar conductors a torns amb incompatibilitats
4. La poda: per què importa tant
5. N-Reines: el clàssic compacte
6. Backtracking vs força bruta vs PD — i les quatre estratègies cara a cara
7. El cost exponencial

Imagina que construeixes la solució per etapes: primera decisió, segona decisió, tercera... Cada seqüència possible de decisions és una branca d'un arbre de decisions; les fulles són solucions candidates completes. La força bruta genera totes les fulles i comprova quines valen. El backtracking és més llest:

• Recorre l'arbre en profunditat, prenent una decisió cada vegada (la pila de recursió de 01-02 i 02-02 porta el compte del camí actual).
• A cada node comprova si la solució parcial encara pot dur a una solució vàlida. Si no pot, poda: abandona aquella branca sencera sense generar-la.
• En esgotar les alternatives d'un node, retrocedeix (backtrack) al node anterior i prova l'opció següent.

La diferència amb greedy és radical: greedy pren una decisió i no torna mai; el backtracking es reserva sempre el dret a penedir-se. La diferència amb la força bruta és la poda: no s'examinen combinacions el fracàs de les quals ja està garantit a mitja construcció.

Gairebé tot backtracking s'escriu amb la mateixa plantilla de tres temps. Val la pena memoritzar-la:

Comentem les peces clau:

• es_completa: l'equivalent al cas base de la recursió (01-02). Aquí una solució completa no talla l'algorisme: es registra i se'n continuen buscant d'altres (llevat que només en vulguem una: llavors es pot retornar True i propagar el tall).
• es_valid: la funció de poda. Comprova restriccions sobre la solució parcial; com més aviat detecti la inviabilitat, més arbre s'estalvia.
• append / pop: la parella sagrada. Tot allò que el pas "triar" modifiqui, el pas "desfer" ho ha de restaurar exactament. Treballem sobre una única estructura compartida (referència, no còpia — recorda 02-02) que es va teixint i desteixint.
• L'estat del camí viu a la pila de crides: en retornar de la recursió som, automàticament, un nivell més amunt de l'arbre.

El problema. RutaBus ha de cobrir demà els tres torns de la línia L1 — Matí, Tarda i Nit — amb els seus tres conductors de plantilla: Anna, Bruno i Carla. Cada conductor fa exactament un torn, però hi ha restriccions de disponibilitat:

• L'Anna no pot fer el torn de nit (cura familiar).
• En Bruno no pot fer el de matí (acaba avui a les 23:00: descans legal).
• La Carla no pot fer el de tarda (formació obligatòria).

Volem totes les assignacions vàlides (planificació necessita alternatives per si algú es posa malalt).

Detalls d'implementació que separen un backtracking correcte d'un de traïdor:

• solucions.append(dict(assignacio)): guardem una còpia. Si guardéssim la referència, el del posterior la buidaria — el clàssic error de còpies vs referències de 02-02.
• La decisió de cada nivell és "quin conductor fa el torn k": l'arbre té profunditat 3 (una per torn) i fins a 3 branques per node.
• La poda és doble: conductor ja ocupat (lliure) i restricció de disponibilitat (compatible).

L'arbre de cerca complet, amb les podes marcades:

Segueix la branca dreta amb el dit: després d'assignar Matí=Carla i Tarda=Bruno, l'únic conductor lliure per a Nit és l'Anna — però l'Anna no fa nits. La branca mor, l'algorisme desfà Tarda=Bruno, prova l'alternativa següent (ja no n'hi ha), desfà Matí=Carla... i com que tampoc no queden opcions a l'arrel, acaba amb les 2 solucions trobades. Aquest moviment de retrocés és literalment l'execució del del assignacio[torn] en tornar de la recursió.

Sense podes, hauríem generat les 3! = 6 permutacions completes i descartat 4. Aquí l'estalvi és modest; amb 20 torns i 20 conductors, 20! ≈ 2,4 × 10¹⁸ permutacions fan la diferència entre "impossible" i "a l'instant" — si les podes tallen aviat.

La poda és la diferència entre backtracking i suïcidi combinatori. Dos principis:

• Podar com més aviat millor. Una restricció comprovada al nivell 2 elimina subarbres sencers; la mateixa restricció comprovada a la fulla només elimina una fulla. Per això es_valid opera sobre la solució parcial, no sobre la completa.
• Ordenar les decisions per fallar aviat. Convé decidir primer la variable més restringida (el torn amb menys conductors possibles): els fracassos afloren a dalt de l'arbre, on podar és barat. És una heurística d'ordre, no canvia la correcció.

Convé ser honestos: la poda no canvia el pitjor cas. Un adversari pot fabricar instàncies on gairebé res no es poda. El backtracking pertany a la família O(2ⁿ)/O(n!) de la jerarquia de 01-03, i cap poda no el treu d'allà en general; el que fa és tornar-lo practicable en les instàncies reals, que rarament són adversàries.

El problema de les N reines — col·locar N reines en un tauler N×N sense que cap no s'ataqui (mateixa fila, columna o diagonal) — és el "hola món" del backtracking, i ens el podem permetre aquí perquè no pertany a cap altre mòdul. Decisió per nivell: a quina columna va la reina de la fila k.

Fixa't en el truc de representació: guardar només la columna per fila elimina de soca-rel els conflictes de fila (cada fila té exactament una reina) — triar bé l'estructura de la solució parcial és, en si mateix, una forma de poda. Per a n = 8, la força bruta sobre les 8⁸ ≈ 16,7 milions de col·locacions (o les 8! = 40 320 permutacions, amb la representació bona) es queda en uns ~2 000 nodes explorats amb poda: aquest és l'ordre de magnitud de l'estalvi.

Primer el duel directe:

La regla del polze: si pots definir un subproblema i una recurrència, la PD converteix l'arbre exponencial en una taula polinòmica — fes-ho. El backtracking és per a quan els estats no es repeteixen o no es deixen resumir (cada solució parcial és única, com una assignació concreta de conductors): allà no hi ha res a memoïtzar i només queda buscar amb intel·ligència.

I el tancament del mòdul — les quatre estratègies cara a cara:

Davant d'un problema nou de RutaBus, aquest és l'ordre d'interrogatori recomanat: greedy demostrable? (el més barat); si no, hi ha recurrència amb solapament? (PD); es parteix en meitats independents? (divideix i venceràs); res de tot això però hi ha restriccions comprovables? (backtracking). I si ni tan sols això, potser toca una heurística assumida com a tal — com el nostre veterà recorregut_supervisor.

Analitzem el backtracking amb les eines del Mòdul 2. En el pitjor cas, l'arbre de decisions té ramificació b (alternatives per nivell) i profunditat n (decisions): fins a bⁿ nodes. Per a assignacions tipus permutació, l'arbre sense podar té n! fulles. És el cim de la jerarquia de 01-03, la zona on sumar un element multiplica el temps.

• Temps: O(bⁿ) o O(n!) en el pitjor cas, multiplicat pel cost d'es_valid a cada node (mantén-lo barat: idealment O(1) o O(n) com a N-Reines!).
• Espai: sorprenentment modest — O(n) per a la solució parcial més O(n) de pila de recursió (02-02). El backtracking no guarda l'arbre: el recorre. Per això pot atacar espais de cerca astronòmics amb memòria de butxaca.
• El millor cas i el cas mitjà (02-03) depenen brutalment de les podes i de l'ordre d'exploració: dues implementacions correctes del mateix problema poden diferir en factors de milers. En backtracking, l'enginyeria de la poda és el rendiment.

• Desfer a mitges. Si "triar" toca dues estructures (l'assignació i un conjunt d'ocupats), "desfer" ha de restaurar totes dues. Qualsevol asimetria corromp silenciosament les branques següents. Revisa que cada append/add/assignació tingui el seu pop/remove/del mirall.
• Guardar referències en lloc de còpies. solucions.append(assignacio) guarda un objecte que continuarà mutant; al final tindràs una llista de solucions buides o totes iguals. Copia (dict(assignacio), llista[:]) en registrar — el matís de 02-02 atacant de nou.
• Podar tard. Comprovar la validesa només a les fulles converteix el backtracking en força bruta amb passos extres. Pregunta't quines restriccions pots avaluar amb la solució a mitges.
• Oblidar el retorn després de registrar. Sense el return en completar la solució, el bucle continua "estenent" una solució ja completa, amb errors d'índex o solucions fantasma.
• Recalcular es_valid des de zero. A N-Reines, valida és O(n); mantenir conjunts de columnes i diagonals ocupades ho abaixa a O(1) per consulta a canvi d'una mica de memòria — el trade-off de 02-02, una altra vegada. (I afegeix dues estructures més que triar/desfer ha de mantenir en mirall.)
• Usar backtracking on hi ha recurrència. Si detectes subproblemes repetits, estàs pagant preu exponencial per una cosa que la PD resol en polinòmic. Repassa la taula comparativa abans d'escriure ni una línia.

S'incorpora un quart torn ("Reforç") i un quart conductor ("David"), amb aquestes restriccions addicionals: en David només pot fer Reforç o Nit, i en Bruno tampoc no pot fer Reforç. Adapta assigna_torns (n'hi ha prou d'actualitzar les constants) i calcula a mà, dibuixant l'arbre, quantes solucions vàlides hi ha. Comprova-ho després amb el codi.

Escriu rutes_inspeccio(xarxa, origen, k) que generi totes les rutes d'inspecció d'exactament k parades que comencin a origen, sense repetir parada, movent-se només entre parades connectades. La xarxa és un diccionari d'adjacència, per exemple:

A n_reines, la funció valida recorre les reines ja col·locades: O(n) per comprovació. Reescriu l'algorisme mantenint tres conjunts — columnes ocupades, diagonals fila − col i diagonals fila + col — perquè la comprovació sigui O(1). No oblidis el mirall triar/desfer sobre els tres conjunts.

Solució 1

Constants noves:

Arbre: per a Matí només hi caben l'Anna o la Carla. (a) Matí=Anna → Tarda ∈ {Bruno} (la Carla no fa tardes, en David tampoc) → Nit ∈ {Carla, David}: amb Nit=Carla queda Reforç=David ✔; amb Nit=David queda Reforç=Carla ✔. (b) Matí=Carla → Tarda ∈ {Anna, Bruno}. Amb Tarda=Anna → Nit ∈ {Bruno, David}: Nit=Bruno deixa Reforç=David ✔; Nit=David deixa Reforç=Bruno ✘ (en Bruno no fa reforços: poda i retrocés). Amb Tarda=Bruno → Nit ∈ {David} (l'Anna no fa nits) → Reforç=Anna ✔. Total: 4 solucions. Si el teu recompte manual difereix del codi, guanya el codi — i l'exercici passa a ser trobar la branca que vas comptar malament.

Solució 2

La plantilla de tres temps, intacta; només canvien els candidats (veïnes a la xarxa) i la poda (no repetir). El veina not in ruta és una cerca en llista O(k) (cost ocult de 02-01); amb un set paral·lel baixaria a O(1). Aquesta funció és, a més, la nostra primera exploració de la xarxa de RutaBus com a graf — una llavor del que ve al Mòdul 4.

Solució 3

Les diagonals "descendents" comparteixen el valor fila − col i les "ascendents" el valor fila + col; tres consultes a conjunts O(1) substitueixen el bucle O(n). El preu: quatre estructures que triar/desfer han de mantenir perfectament sincronitzades — comprova que cada add té el seu remove.

El backtracking completa el nostre repertori: construir la solució per etapes, podar les branques sense futur i desfer per explorar alternatives, amb la plantilla triar–explorar–desfer com a esquelet universal i la disciplina del mirall (tot el que es fa es desfà) com a regla d'or. L'hem aplicat a l'assignació de conductors de RutaBus, a les rutes d'inspecció sobre la xarxa — el nostre primer passeig per ella com a graf — i al clàssic N-Reines, i n'hem assumit la naturalesa: cost exponencial en el pitjor cas que només la qualitat de les podes torna practicable. Amb això, el Mòdul 3 queda complet: divideix i venceràs per a subproblemes independents, greedy per a decisions locals demostrablement segures, programació dinàmica per a subproblemes solapats amb recurrència, i backtracking per a restriccions que exigeixen buscar amb tornada enrere — quatre motlles, quatre preguntes de diagnòstic, i el judici del Mòdul 2 per sotmetre a anàlisi qualsevol disseny que en surti. Al Mòdul 4 recollirem la collita: els algorismes clàssics que van néixer d'aquestes estratègies — la cerca binària i les ordenacions merge sort i quick sort com a fills de divideix i venceràs, Dijkstra com el greedy que sí que és òptim, Floyd-Warshall com a programació dinàmica sobre grafs — implementats i analitzats peça a peça, començant per la joia de l'eficiència logarítmica: la cerca binària.