El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

Segona bateria d'entrenament: disseny. Aquí exercitem les quatre estratègies del Mòdul 3 —divideix i venceràs (03-01), greedy (03-02), programació dinàmica (03-03) i backtracking (03-04)— sobre problemes nous de RutaBus, diferents dels que vam resoldre al curs. Els clàssics del Mòdul 4 et serviran de referència (veuràs que més d'un hi reapareix disfressat).

Com treballar aquesta lliçó: en disseny, mirar la solució abans d'hora és especialment nociu, perquè el valor de l'exercici és a l'estona d'exploració: provar un enfocament, veure que falla, canviar. Dedica a cada problema com a mínim 20–30 minuts amb paper i editor abans de llegir la solució. I quan la llegeixis, no et limitis a validar el codi: compara el teu raonament amb el raonament exposat.

Contingut

Divideix i venceràs: mesurar el desordre de les arribades.
Greedy: reforços en franges de saturació (amb justificació) i bons de transbordament (amb contraexemple).
Programació dinàmica: la tarifa òptima de l'inspector, amb taula i reconstrucció.
Backtracking amb poda: comitès de revisió de línies.
Diagnòstic: tres miniproblemes, quina estratègia encaixa amb cadascun?

Exercici 1: Mesurar el desordre de les arribades (divideix i venceràs)

Dificultat: mitjana

Els autobusos de L1 surten de cotxera en ordre: el bus 0 primer, després l'1, etc. La llista arribades conté l'instant (en minuts) en què cada bus va arribar a Estació Nord: arribades[i] és l'arribada del bus que va sortir en posició i. Un avançament és un parell i < j tal que arribades[i] > arribades[j] (un bus que va sortir abans va arribar després). El nombre d'avançaments mesura el "desordre" de la línia i es fa servir com a indicador de qualitat.

arribades = [12, 9, 21, 14, 30, 18]
# avancaments: (0,1) 12>9, (2,3) 21>14, (2,5) 21>18, (4,5) 30>18  -> 4

Escriu compta_avancaments(arribades) en Θ(n log n) fent servir divideix i venceràs. La versió de força bruta (comparar tots els parells) és Θ(n²), com ja saps per l'exercici 1 de 06-01.

Pista: és exactament l'estructura de merge_sort (04-03). Pregunta't quina informació sobre parells creuats pots obtenir gratis en el moment de la mescla, quan totes dues meitats ja estan ordenades.

Solució

La clau de divideix i venceràs (03-01) és trobar la descomposició: els avançaments són de tres tipus — tots dos índexs a la meitat esquerra, tots dos a la dreta, o creuats (i a l'esquerra, j a la dreta). Els dos primers els resol la recursió. Els creuats serien Θ(n²) de comptar a la brava... llevat que les meitats estiguin ordenades: aleshores, durant la mescla de merge (04-03), cada vegada que prenem un element de la meitat dreta abans que un de l'esquerra, aquell element dret és menor que tots els que queden a l'esquerra, i cadascun d'ells forma un avançament amb ell.

def compta_avancaments(arribades):
    def ordena_i_compta(v):
        if len(v) <= 1:
            return v, 0
        mig = len(v) // 2
        esq, a_esq = ordena_i_compta(v[:mig])
        dret, a_dret = ordena_i_compta(v[mig:])
        # Mescla comptant parells creuats
        resultat, creuats = [], 0
        i = j = 0
        while i < len(esq) and j < len(dret):
            if esq[i] <= dret[j]:
                resultat.append(esq[i]); i += 1
            else:
                resultat.append(dret[j]); j += 1
                creuats += len(esq) - i   # tots els pendents d'esq l'avancen
        resultat.extend(esq[i:]); resultat.extend(dret[j:])
        return resultat, a_esq + a_dret + creuats
    return ordena_i_compta(arribades)[1]

print(compta_avancaments([12, 9, 21, 14, 30, 18]))  # 4

Per què funciona: quan dret[j] < esq[i], com que esq està ordenada, dret[j] també és menor que esq[i+1], ..., esq[-1]. Són len(esq) - i avançaments comptats de cop, en O(1). Cap parell no es compta dues vegades (cada parell creuat es detecta exactament quan el seu element dret surt de la mescla) i cap no s'escapa.

Complexitat: la recurrència és la mateixa de merge_sort, T(n) = 2T(n/2) + Θ(n), que ja vam resoldre a 04-03: Θ(n log n). L'espai auxiliar és Θ(n) per les llistes de mescla.

Errors típics: (1) comptar només parells adjacents desordenats — un vector pot tenir 1 desordre adjacent i n²/4 avançaments totals; (2) sumar len(esq) - i a la branca equivocada (quan surt l'esquerre no hi ha avançament); (3) comptar i no retornar la llista ordenada, amb la qual cosa les meitats no estan mai ordenades i el compte de creuats és incorrecte.

Exercici 2: Reforços i bons (greedy: quan sí i quan no)

Dificultat: mitjana

Dos problemes independents; en un greedy és correcte i cal justificar-ho, en l'altre és incorrecte i cal donar un contraexemple. Parteix que no saps quin és quin.

Part A — Franges de reforç. El sistema de monitoratge produeix la llista ordenada de minuts del dia en què L2 va estar saturada, p. ex. critics = [485, 490, 510, 545, 700, 715] (minuts des de mitjanit). Un bus de reforç cobreix exactament 30 minuts des de la seva hora d'incorporació: si s'incorpora al minut t, cobreix [t, t+30]. Dissenya un algorisme que calculi el mínim nombre de reforços (i les seves hores) perquè tot minut crític quedi cobert.

Part B — Bons de transbordament. Un usuari farà exactament 8 viatges aquest mes. Tarifes: bitllet senzill 2,00 €; bo de 5 viatges 6,00 € (1,20 €/viatge); bo de 8 viatges 10,40 € (1,30 €/viatge). Un company proposa aquest greedy: "compra sempre el títol amb menor preu per viatge d'entre els que no superin els viatges restants; completa amb senzills". És correcte? Justifica-ho o refuta-ho.

Solució

Part A — greedy correcte. Estratègia: recorre els minuts crítics en ordre; quan en trobis un de no cobert, incorpora un reforç exactament en aquell minut (el més tard possible que encara el cobreix), i salta tots els crítics que cauen dins de la seva finestra.

def planifica_reforcos(critics):
    reforcos = []
    fi_cobertura = float("-inf")
    for m in critics:                # critics ve ordenada
        if m > fi_cobertura:
            reforcos.append(m)       # bus incorporat al minut m
            fi_cobertura = m + 30
    return reforcos

print(planifica_reforcos([485, 490, 510, 545, 700, 715]))
# [485, 545, 700] -> 3 reforcos: cobreixen [485,515], [545,575], [700,730]

Justificació (argument d'intercanvi, com a 03-02): sigui m₁ el primer minut crític. Tota solució vàlida té algun bus amb inici t ≤ m₁ (algú ha de cobrir m₁). Si en aquesta solució substituïm aquest bus per un que comença exactament a m₁, la seva finestra [m₁, m₁+30] cobreix tot el que cobria [t, t+30] dins dels crítics (no hi ha crítics abans de m₁, i la finestra es desplaça cap a la dreta, on són els altres). La solució continua sent vàlida i de la mateixa mida. Repetint l'argument amb el següent crític no cobert, qualsevol solució òptima es transforma en la greedy sense afegir busos: la greedy és òptima. Cost: Θ(n) si la llista ve ordenada (Θ(n log n) si cal ordenar-la).

Part B — greedy incorrecte. Seguim la regla amb 8 viatges: el menor preu per viatge és el bo de 5 (1,20 €). El comprem (queden 3 viatges); ni el bo de 5 ni el de 8 no "caben" en 3 viatges restants, així que completem amb 3 senzills.

Estratègia	Compra	Cost
Greedy proposat	bo de 5 + 3 senzills	6,00 + 6,00 = 12,00 €
Òptim	bo de 8	10,40 €

Contraexemple trobat: el greedy paga 12,00 € quan l'òptim costa 10,40 €. L'error és el de sempre (recorda canvi_greedy a 03-02): el criteri local "millor preu per viatge" no veu que fraccionar la compra obliga a completar amb el títol més car. Aquest problema té subestructura òptima i decisions que se solapen: és terreny de programació dinàmica, que és just el que fem a l'exercici següent.

Error típic: "he provat el greedy amb dos exemples i ha funcionat, per tant és correcte". Greedy exigeix demostració (intercanvi) o contraexemple; els exemples favorables no demostren res.

Exercici 3: La tarifa òptima de l'inspector (programació dinàmica)

Dificultat: alta

Un inspector de RutaBus s'ha de desplaçar els dies dies = [1, 2, 4, 5, 6, 9, 10, 11, 12, 20, 21] del mes. Tarifes: bitllet de dia 2 € (cobreix 1 dia), abonament setmanal 9 € (cobreix 7 dies consecutius), abonament mensual 28 € (cobreix 30 dies consecutius). Dissenya amb programació dinàmica (tabulació, com cost_minim a 03-03) un algorisme que calculi el cost mínim per cobrir tots els dies de viatge, i reconstrueix quins títols comprar i quin dia. Dona la definició del subproblema, la recurrència, la taula i la complexitat.

Pista: defineix el subproblema per dia del calendari, no per índex de la llista de viatges: "cost mínim per cobrir tots els dies de viatge fins al dia d".

Solució

Subproblema: dp[d] = cost mínim per cobrir tots els dies de viatge ≤ d, amb d de 0 fins a l'últim dia de viatge.

Recurrència: si el dia d no es viatja, no cal comprar res de nou: dp[d] = dp[d-1]. Si es viatja, hi ha tres decisions possibles, i ens quedem amb la més barata:

bitllet de dia: dp[d-1] + 2
abonament setmanal que acabi en d (cobreix d−6..d): dp[max(0, d-7)] + 9
abonament mensual que acabi en d: dp[max(0, d-30)] + 28

def tarifa_optima(dies, preus=(2, 9, 28), durades=(1, 7, 30)):
    viatja = set(dies)
    ultim = max(dies)
    dp = [0] * (ultim + 1)
    eleccio = [None] * (ultim + 1)        # per reconstruir
    for d in range(1, ultim + 1):
        if d not in viatja:
            dp[d] = dp[d - 1]
            continue
        dp[d] = float("inf")
        for preu, dur in zip(preus, durades):
            cost = dp[max(0, d - dur)] + preu
            if cost < dp[d]:
                dp[d] = cost
                eleccio[d] = (preu, dur)
    # Reconstruccio cap enrere
    compres, d = [], ultim
    while d > 0:
        if d not in viatja:
            d -= 1
        else:
            preu, dur = eleccio[d]
            compres.append((max(1, d - dur + 1), preu, dur))
            d = max(0, d - dur)
    return dp[ultim], list(reversed(compres))

cost, compres = tarifa_optima([1, 2, 4, 5, 6, 9, 10, 11, 12, 20, 21])
print(cost)      # 21
print(compres)   # [(1, 9, 7), (9, 2, 1), (10, 2, 1), (11, 2, 1), (12, 2, 1),
                 #  (20, 2, 1), (21, 2, 1)]

Traça de la taula (només els dies interessants):

d	viatja?	dp[d]	millor decisió
1	sí	2	bitllet
2	sí	4	bitllet
4	sí	6	bitllet
5	sí	8	bitllet
6	sí	9	abonament setmanal (cobreix dies 1–7): dp[0]+9=9 < dp[5]+2=10
9	sí	11	bitllet: dp[8]+2
10–12	sí	13, 15, 17	bitllets
20	sí	19	bitllet (el setmanal donaria dp[13]+9=26)
21	sí	21	bitllet

Resultat: 21 € — un abonament setmanal que cobreix els dies 1–7 (9 €) més sis bitllets de dia (9, 10, 11, 12, 20, 21). Compara-ho amb les alternatives ingènues: 11 bitllets solts = 22 €, abonament mensual = 28 €. (Als dies 10–12 hi ha empats: quatre bitllets després del setmanal costen el mateix que altres combinacions; la taula es queda amb la primera opció mínima.)

Complexitat: Θ(D · 3) = Θ(D) en temps i Θ(D) en espai, amb D l'últim dia (aquí 21). Fixa't que depèn del calendari, no del nombre de viatges.

Errors típics: (1) plantejar el greedy "compra l'abonament si hi ha ≥ 5 viatges a la setmana" — falla en configuracions límit, com va demostrar l'exercici 2B; (2) oblidar el max(0, d - dur) i accedir a índexs negatius (que a Python no donen error: llegeixen pel final de la llista i corrompen el resultat en silenci!); (3) guardar només el cost i no l'elecció, amb la qual cosa la reconstrucció —que és el que l'app necessita mostrar a l'usuari— és impossible, com vam insistir amb motxilla_millores a 03-03.

Exercici 4: Comitès de revisió de línies (backtracking amb poda)

Dificultat: alta

Auditoria interna exigeix formar un comitè de revisió de 2 persones per cada línia (L1, L2, L3). Revisors disponibles: Anna, Bruno, Carla, Diego i Elena. Restriccions:

Ningú no pot revisar la línia en què condueix: l'Anna condueix L1; en Bruno i la Carla condueixen L2; en Diego condueix L3.
Cada revisor pot participar com a màxim en 2 comitès.
L'Elena i en Diego tenen torns incompatibles: no poden coincidir al mateix comitè.

Escriu forma_comites() amb backtracking (03-04) que retorni una assignació vàlida (o None), i inclou almenys una poda que talli branques sense futur abans d'explorar-les.

Solució

Espai d'estats: per a cada línia, triar un parell de revisors. Sense restriccions hi hauria C(5,2)³ = 10³ = 1000 combinacions; les restriccions i la poda ho redueixen dràsticament.

from itertools import combinations

REVISORS = ["Anna", "Bruno", "Carla", "Diego", "Elena"]
CONDUEIX = {"Anna": "L1", "Bruno": "L2", "Carla": "L2", "Diego": "L3"}
LINIES = ["L1", "L2", "L3"]
MAX_COMITES = 2

def forma_comites():
    us = {r: 0 for r in REVISORS}
    assignacio = {}

    def valid(linia, parell):
        for r in parell:
            if CONDUEIX.get(r) == linia:     # restriccio 1
                return False
            if us[r] >= MAX_COMITES:         # restriccio 2
                return False
        if "Elena" in parell and "Diego" in parell:  # restriccio 3
            return False
        return True

    def resol(i):
        if i == len(LINIES):
            return True                       # totes les linies cobertes
        # PODA de capacitat: places que falten vs. capacitat restant
        places_pendents = 2 * (len(LINIES) - i)
        capacitat = sum(MAX_COMITES - us[r] for r in REVISORS)
        if capacitat < places_pendents:
            return False                      # branca sense futur: tallar ja
        linia = LINIES[i]
        for parell in combinations(REVISORS, 2):
            if valid(linia, parell):
                assignacio[linia] = parell    # decidir
                for r in parell:
                    us[r] += 1
                if resol(i + 1):
                    return True
                for r in parell:              # desfer (backtrack)
                    us[r] -= 1
                del assignacio[linia]
        return False

    return dict(assignacio) if resol(0) else None

print(forma_comites())
# {'L1': ('Bruno', 'Carla'), 'L2': ('Anna', 'Diego'), 'L3': ('Anna', 'Bruno')}

Raonament: l'esquelet és el patró decidir → recursió → desfer de 03-04 (idèntic en esperit a assigna_torns). La comprovació valid és la poda per restriccions: descarta el parell abans de baixar un nivell. La poda de capacitat és més interessant: si queden 2 línies per cobrir (4 places) però entre tots els revisors només queda capacitat per a 3 participacions, cap combinació futura no pot funcionar — tallem sense enumerar els ~100 nodes d'aquell subarbre. És el mateix principi que la poda de N-Reines: detectar la impossibilitat com més aviat millor.

Una solució vàlida que troba l'algorisme: L1 = {Bruno, Carla} (tots dos condueixen L2, poden revisar L1), L2 = {Anna, Diego}, L3 = {Anna, Bruno} — l'Anna i en Bruno queden amb 2 comitès (límit just), en Diego no coincideix amb l'Elena en cap comitè, i ningú no revisa la seva pròpia línia.

Complexitat: el pitjor cas teòric continua sent exponencial en el nombre de línies — O(C(r,2)^L) —, com tot backtracking; les podes no canvien el pitjor cas, canvien el cas real. Per això a 03-04 vam insistir: backtracking sense poda és força bruta amb un altre nom.

Errors típics: (1) oblidar desfer us[r] -= 1 en retrocedir — l'estat queda corrupte i l'algorisme declara impossibles casos que tenen solució; (2) validar l'assignació completa només al final (a i == len(LINIES)) en lloc de podar a cada nivell: correcte però exponencialment més lent; (3) mutar assignacio i retornar-la sense copiar, amb la qual cosa el del posterior pot buidar el resultat.

Exercici 5: Diagnòstic — quina estratègia encaixa?

Dificultat: mitjana

Per a cada miniproblema, decideix quina estratègia de disseny faries servir (divideix i venceràs, greedy, programació dinàmica o backtracking) i justifica en 3–5 línies per què, recolzant-te en la taula comparativa del final de 03-04. No cal implementar res: aquest exercici entrena el diagnòstic, que a la pràctica professional és la part difícil.

A) RutaBus té 6 vehicles de reserva per repartir entre L1, L2 i L3. Una taula empírica diu quants passatgers extra capta cada línia segons quants vehicles rebi (els rendiments no són proporcionals: a L1, 1 vehicle aporta 300 passatgers però 2 n'aporten només 380; a L3, 1 n'aporta 100 i 3 n'aporten 900). Cal repartir els 6 vehicles maximitzant el total de passatgers extra.

B) El departament comercial té n sol·licituds de publicitat a la marquesina de Plaça Major, cadascuna amb data d'inici i fi, totes paguen el mateix. Cal acceptar el màxim nombre de sol·licituds sense que se solapin.

C) Cal planificar la visita trimestral de l'auditor a 8 parades concretes, respectant precedències ("Hospital Central abans que Parc del Riu") i finestres horàries per parada, i cal llistar totes les planificacions vàlides perquè direcció triï.

Solució

A) Programació dinàmica. Senyals: decisions seqüencials (quants vehicles dono a cada línia), un recurs acotat que es consumeix (els 6 vehicles: és el "pes" d'una motxilla), subestructura òptima (el millor repartiment entre L2 i L3 del que sobri no depèn de com he fet servir l'assignat a L1, només de quant) i subproblemes solapats (molts camins porten a "queden 3 vehicles per a 2 línies"). El greedy incremental ("dona cada vehicle a la línia que més millora") falla precisament perquè els rendiments no són còncaus: a L3 el tercer vehicle aporta més que el primer, i el greedy no arriba mai a veure-ho. És la motxilla de motxilla_millores (03-03) amb disfressa de repartiment.

B) Greedy. És la selecció d'activitats (03-02, assigna_trajectes): intervals, tots d'igual valor, maximitzar quants n'hi caben sense solapar-se. El criteri "accepta sempre la sol·licitud que acaba abans d'entre les compatibles" té demostració d'optimalitat per intercanvi. No cal PD (no hi ha pesos ni valors diferents que obliguin a comparar combinacions) ni backtracking (no volem totes les solucions, només una d'òptima, i el greedy la troba en Θ(n log n)).

C) Backtracking. Senyals inequívocs: restriccions combinades (precedències + finestres), i sobretot el requisit d'enumerar totes les solucions vàlides — greedy i PD produeixen una solució (òptima), no un catàleg. L'espai d'estats són les permutacions de 8 parades (8! = 40.320), inabordable amb força bruta pura si creix, però molt podable: tan bon punt una planificació parcial viola una precedència o una finestra, es talla la branca sencera, com a rutes_inspeccio (03-04).

Error típic en diagnòstic: triar estratègia pel domini del problema ("és d'intervals, per tant greedy") en lloc de per les seves propietats (elecció local segura? subproblemes solapats? cal enumerar?). B és greedy i A és PD, i tots dos es podrien descriure com "repartir recursos": el que decideix és l'estructura, no l'enunciat.

Conclusió

Has dissenyat des de zero amb les quatre estratègies: divideix i venceràs aprofitant la mescla de merge_sort per comptar avançaments en Θ(n log n); greedy amb les dues cares que sempre té —demostració per intercanvi quan funciona, contraexemple quan no—; programació dinàmica amb subproblema, recurrència, taula i reconstrucció per a les tarifes de l'inspector; i backtracking amb podes de restricció i de capacitat per als comitès. I, potser el més important, has practicat el diagnòstic: mirar un problema nou i reconèixer quina estratègia demana, que és l'habilitat que de debò es fa servir a la feina diària.

Amb l'anàlisi (06-01) i el disseny (aquesta lliçó) entrenats, queda el tercer múscul del curs: a la lliçó següent practicarem l'optimització — agafar codi RutaBus lent i realista i aplicar-li, amb disciplina, el mètode del Mòdul 5.

Exercicis de Disseny d'Algorismes

Contingut

Exercici 1: Mesurar el desordre de les arribades (divideix i venceràs)

Solució

Exercici 2: Reforços i bons (greedy: quan sí i quan no)

Solució

Exercici 3: La tarifa òptima de l'inspector (programació dinàmica)

Solució

Exercici 4: Comitès de revisió de línies (backtracking amb poda)

Solució

Exercici 5: Diagnòstic — quina estratègia encaixa?

Solució

Conclusió

Curs d'Anàlisi i Disseny d'Algorismes

Mòdul 1: Introducció als Algorismes

Mòdul 2: Anàlisi d'Algorismes

Mòdul 3: Estratègies de Disseny d'Algorismes

Mòdul 4: Algorismes Clàssics

Mòdul 5: Optimització d'Algorismes

Mòdul 6: Pràctiques i Exercicis