A la lliçó anterior vam aprendre a trossejar problemes amb divideix i venceràs. La segona gran estratègia del mòdul és de temperament oposat: en lloc de resoldre-ho tot i després decidir, un algorisme greedy (voraç) construeix la solució pas a pas prenent a cada moment la decisió que sembla millor ara mateix, sense mirar enrere i sense calcular les conseqüències futures. Aquesta impaciència produeix algorismes senzills i rapidíssims... que unes vegades són òptims demostrables i d'altres fallen estrepitosament sense avisar. A RutaBus ja vam topar amb un greedy sense saber-ho: el recorregut_supervisor de 01-02, aquella heurística del veí més proper. En aquesta lliçó aprendrem l'anatomia d'un greedy, resoldrem un problema real d'assignació de trajectes, veurem amb els nostres propis ulls un greedy fallant, i — el més important — aprendrem a distingir quan es pot confiar en un.

1. La idea: decisió localment òptima i irrevocable
2. Anatomia d'un algorisme greedy
3. Exemple RutaBus: màxim nombre de trajectes per a un autobús
4. Per què funciona: una demostració informal
5. Quan greedy falla: dos contraexemples
6. Com reconèixer si un problema admet greedy
7. Algorismes greedy cèlebres

Un algorisme greedy es caracteritza per dos trets:

• Elecció localment òptima: a cada pas escull el candidat que maximitza (o minimitza) un criteri immediat, sense simular el futur.
• Irrevocabilitat: una decisió presa no es revisa mai. No hi ha tornada enrere — just el contrari del backtracking que veurem a 03-04.

Aquesta combinació explica les seves dues cares:

Gairebé tots els greedy comparteixen quatre peces. Convé identificar-les explícitament abans d'escriure codi:

1. Conjunt de candidats: els elements entre els quals es tria (trajectes, monedes, parades...).
2. Funció de selecció: el criteri voraç que decideix quin candidat prendre a continuació ("el que acaba abans", "la moneda més grossa", "la parada més propera").
3. Test de factibilitat: puc afegir aquest candidat a la solució parcial sense violar les restriccions?
4. Solució: la construcció acaba quan s'esgoten els candidats o la solució és completa.

En pseudocodi, l'esquelet universal:

Tot l'enginy és al pas d'ordenar: triar bé la funció de selecció és dissenyar l'algorisme. Amb la funció correcta, greedy és òptim; amb una de plausible però incorrecta, és només una heurística (recorda la distinció exactes vs heurístics de 01-02).

El problema. RutaBus té un únic autobús de reforç i una llista de trajectes sol·licitats per a demà, cadascun amb hora d'inici i hora de fi (en minuts des de mitjanit). L'autobús només pot fer un trajecte alhora. Objectiu: assignar-li el màxim nombre de trajectes sense solapaments. (És la versió RutaBus del clàssic problema de selecció d'activitats.)

Abans de veure la solució, pensa-hi: quina funció de selecció faries servir? Candidates raonables: el trajecte més curt primer, el que comença abans, el que té menys conflictes... Totes sonen bé i totes fallen en algun cas. La correcta és menys intuïtiva: el que acaba abans.

Explicació línia a línia:

• sorted(..., key=lambda t: t[2]): materialitza la funció de selecció. Cost O(n log n), que dominarà el total (02-01).
• fi_ultim: l'estat mínim que necessitem recordar — quan queda lliure l'autobús. Fixa't en l'ús d'una sola variable: espai auxiliar O(1) més la sortida (02-02).
• if inici >= fi_ultim: el test de factibilitat. Un trajecte és compatible si comença quan l'autobús ja està lliure.
• L'append és la decisió irrevocable: mai no reconsiderem un trajecte acceptat ni recuperem un de rebutjat.
• El bucle recorre els candidats una vegada: O(n). Total: O(n log n), davant del cost exponencial de provar tots els subconjunts de trajectes.

Resultat: 3 trajectes. Cap combinació no n'aconsegueix 4 — i això no és casualitat, com argumentarem tot seguit.

L'argument clàssic s'anomena argument d'intercanvi (exchange argument) i convé interioritzar-lo, perquè és l'eina estàndard per justificar un greedy:

1. Sigui g el primer trajecte que tria el greedy: el que acaba abans de tots.
2. Pren qualsevol solució òptima OPT. Si OPT no conté g, mira el primer trajecte d'OPT (anomenem-lo x). Com que g acaba abans o igual que qualsevol trajecte — també abans que x —, podem substituir x per g dins d'OPT sense crear solapaments: g deixa lliure l'autobús fins i tot abans que x, així que tot el que cabia després de x continua cabent després de g.
3. La solució modificada té la mateixa mida que OPT, per tant continua sent òptima i comença com el greedy.
4. Eliminat g i els trajectes incompatibles amb ell, queda un subproblema idèntic però més petit ("màxim de trajectes que comencen després de fi_ultim"), al qual s'aplica el mateix raonament una vegada i una altra.

Conclusió: l'elecció voraç mai no ens allunya d'un òptim. Fixa't en la lògica: no diem que greedy sigui l'única solució òptima, sinó que sempre existeix un òptim que pren la decisió voraç — amb això n'hi ha prou.

Aquest argument explica també per què "el que acaba abans" és la clau: acabar aviat deixa el màxim marge possible al futur. Els criteris rivals no tenen aquesta propietat: el trajecte més curt pot estar "travessat" bloquejant dos de llargs compatibles, i el que comença abans pot ser llarguíssim i menjar-se el matí sencer.

Els bitllets de recàrrega de la targeta RutaBus valen 1, 3 i 4 euros (un sistema deliberadament exòtic). Volem abonar una quantitat amb el mínim nombre de bitllets. El greedy natural — "pren sempre el bitllet més gros que hi càpiga" — falla:

Per a 6 €, el greedy pren el 4 (localment òptim) i es condemna a completar amb dues monedes d'1. La decisió irrevocable d'agafar el 4 destrueix la possibilitat de fer servir 3+3. Amb el sistema de l'euro (1, 2, 5, 10, 20, 50...) el greedy sí que és òptim — es diu que el sistema és canònic —, cosa que il·lustra una veritat incòmoda: el mateix algorisme és exacte o incorrecte segons les dades del problema. Per això un greedy sense argument d'optimalitat és una aposta. (La versió general del canvi de monedes es resol amb garanties amb programació dinàmica, l'estratègia de 03-03.)

A 01-02 vam escriure recorregut_supervisor: el supervisor visita totes les parades anant sempre a la més propera no visitada. Ara tenim vocabulari per diagnosticar-lo: és un greedy de manual — candidats: parades no visitades; selecció: mínima distancia; factibilitat: no repetir parada. I ja vam dir llavors que és una heurística: dona rutes raonables, no la ruta més curta.

Veure'l fallar és fàcil amb parades en línia recta (posicions en km): el supervisor surt del km 0 i ha de visitar les parades dels km 1, 2 i −1,5.

• Greedy (veí més proper): la més propera al 0 és la del km 1 → després la del 2 (a 1 km) → i finalment la del −1,5 (a 3,5 km). Total: 1 + 1 + 3,5 = 5,5 km.
• Òptim: anar primer "a contracorrent": 0 → −1,5 (1,5 km) → 1 (2,5 km) → 2 (1 km). Total: 5 km.

El greedy perd per anar primer al més còmode i deixar per al final el desplaçament llarg de tornada: cada elecció local va ser impecable i el total, subòptim.

La moralitat és doble. Primera: greedy falla quan una decisió còmoda ara crea un sobrecost inevitable després. Segona: un greedy no òptim no és cap escombraria — com a heurística, recorregut_supervisor dona solucions decents en O(n²) per a un problema (el del viatjant) la solució exacta del qual és exponencial. Saber que no és òptim, i decidir si ens serveix, és exactament la mena de judici professional que aquest curs entrena.

No hi ha recepta infal·lible, però sí dues propietats que els problemes "greedy-compatibles" exhibeixen (les enunciem de manera informal; el seu tractament rigorós pertany a textos avançats):

• Propietat d'elecció voraç: existeix una elecció localment òptima que forma part d'alguna solució global òptima — és a dir, decidir ja, sense mirar el futur, no tanca la porta a l'òptim. Es comprova típicament amb un argument d'intercanvi com el de la secció anterior.
• Subestructura òptima: després de prendre la decisió voraç, el que queda és un subproblema del mateix tipus la solució òptima del qual, unida a la decisió presa, dona l'òptim global. (Aquesta propietat reapareixerà a 03-03: la programació dinàmica també l'exigeix. La diferència: la PD explora diverses decisions possibles i el greedy s'ho juga tot a una.)

Llista de comprovació pràctica abans de confiar en un greedy:

1. Puc formular una funció de selecció clara?
2. Tinc un argument d'intercanvi, encara que sigui informal, que l'elecció voraç no descarta l'òptim?
3. He buscat activament contraexemples petits (3-6 elements, casos extrems)?
4. Si no aconsegueixo 2 i 3: em serveix com a heurística, o el problema exigeix l'òptim exacte (→ PD a 03-03 o backtracking a 03-04)?

Dijkstra mereix una nota: és la prova que "greedy" no vol dir "aproximat". Triar sempre la parada no processada més propera a l'origen és òptim per a camins mínims — ho demostrarem i implementarem a 04-05, quan la xarxa de RutaBus sigui per fi un graf amb pesos.

• Assumir optimalitat sense argument. "Sona raonable" no és una demostració. El canvi de monedes amb (1, 3, 4) sona igual de raonable i falla. Exigeix sempre un argument d'intercanvi o contraexemples esgotats.
• Triar la funció de selecció equivocada. En el problema de trajectes, tres criteris plausibles fallen i només "acaba abans" funciona. Prova cada criteri candidat contra exemples petits dissenyats amb mala idea.
• Oblidar l'ordenació en l'anàlisi. El bucle greedy és O(n), però el sorted previ el fa O(n log n). No anunciïs costos que el teu propi codi desmenteix (02-01).
• Confondre "greedy falla" amb "greedy inútil". Una heurística voraç amb garanties empíriques pot ser la millor opció d'enginyeria quan l'exacte és exponencial. Documenta que és heurística i llestos.
• Modificar la solució ja construïda. Si et descobreixes "traient" elements acceptats, ja no estàs escrivint un greedy: estàs improvisant un backtracking sense control. Replanteja l'estratègia (03-04).

RutaBus vol instal·lar el mínim nombre de punts de recàrrega en una avinguda de manera que tota parada tingui un punt a menys de 500 m. Les posicions de les parades (en metres) són en una llista ordenada, p. ex. [100, 300, 850, 900, 1800]. Dissenya un greedy: indica candidats, funció de selecció i test de factibilitat, i implementa'l. Pista: processa les parades d'esquerra a dreta i col·loca cada punt tan a la dreta com sigui possible.

Per al problema dels trajectes, demostra amb un contraexemple concret (3-4 trajectes amb hores) que la funció de selecció "el trajecte més curt primer" no és òptima.

L'autobús de reforç té un dipòsit per a 300 km. A la ruta hi ha benzineres als km [90, 150, 230, 350, 480] i la ruta fa 520 km. Escriu un greedy que calculi el mínim nombre de repostatges (sortint amb el dipòsit ple) i raona informalment per què la seva elecció voraç és segura.

Solució 1

• Candidats: posicions possibles de punts de recàrrega. Selecció: per a la parada descoberta més a l'esquerra, col·locar el punt a parada + 500 (tan a la dreta com sigui possible sense deixar-la de cobrir). Factibilitat: cada parada ha de quedar a ≤ 500 m d'algun punt.

Amb [100, 300, 850, 900, 1800]: el punt a 600 cobreix 100, 300, 850 i 900 (totes a ≤ 500 de 600... 100 és a 500 justos, dins); el punt a 2300 cobreix 1800. Total: 2 punts. Argument d'intercanvi: qualsevol solució òptima necessita algun punt que cobreixi la primera parada; moure'l fins a parades[0] + 500 no descobreix ningú de l'esquerra (no hi ha ningú) i només pot cobrir més parades a la dreta. Cost: O(n).

Solució 2

Trajectes: A = (10:00-12:00), B = (11:45-12:15), C = (12:10-14:00). El més curt és B (30 min); el greedy "curt primer" el tria, i B se solapa tant amb A (11:45 < 12:00) com amb C (12:10 < 12:15): queden tots dos descartats i el total és 1 trajecte. Tanmateix, A i C són compatibles entre si (A acaba a les 12:00 ≤ 12:10): l'òptim és 2. B està "travessat" bloquejant dos trajectes compatibles — exactament el defecte que vam anticipar a la lliçó. Comprova que el criteri correcte, "acaba abans", tria A i després C i assoleix l'òptim.

Solució 3

Selecció voraç: no repostar fins que sigui imprescindible i, llavors, fer-ho a la benzinera assolible més llunyana que hàgim deixat enrere.

Traça amb autonomia 300: des del km 0 s'arriba fins al 300, així que 90, 150 i 230 es passen de llarg; el 350 ja no s'assoleix → repostatge imprescindible, i de les assolibles (90, 150, 230) es tria la més llunyana: 230. Des de 230 s'arriba al km 530 ≥ 520, així que s'arriba a la destinació passant de llarg 350 i 480. Resultat: 1 repostatge. Argument d'intercanvi: quan repostar és inevitable, qualsevol pla òptim reposta en alguna benzinera assolible; substituir-la per la més llunyana no ens pot deixar tirats (també era assolible) i deixa el dipòsit ple més endavant, cobrint un tram posterior igual o més gran. L'elecció voraç mai no allunya de l'òptim. (La cerca d'assolibles dins del bucle és O(n); amb dos índexs es deixa en O(n) total — bon refinament opcional.)

Els algorismes greedy construeixen la solució amb decisions locals i irrevocables: candidats + funció de selecció + test de factibilitat, gairebé sempre amb una ordenació O(n log n) com a únic cost rellevant. Hem vist l'estratègia brillar en l'assignació de trajectes — amb el seu argument d'intercanvi: triar el que acaba abans mai no tanca la porta a l'òptim — i fracassar en el canvi de monedes (1, 3, 4) i en el nostre vell conegut recorregut_supervisor, que avui hem rebatejat com el que sempre va ser: un greedy heurístic. La lliçó de fons: greedy exigeix demostrar (o almenys argumentar i buscar contraexemples), perquè la seva fallada és silenciosa. I què fem quan el problema té subestructura òptima però l'elecció voraç falla — quan 6 € es paguen millor amb 3+3 que començant pel 4? Necessitem una estratègia que, en lloc d'apostar-ho tot a una decisió, explori totes les decisions possibles reutilitzant els càlculs repetits — la idea de gastar memòria per no repetir feina que vam deixar apuntada a 02-02 amb construeix_index. Aquesta estratègia té nom propi i és la protagonista de la propera lliçó: la programació dinàmica.