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

HOME

El mòdul 8 va acabar amb una promesa: consolidar amb les mans el que els mòduls 3 a 8 van donar en teoria, codi i criteri. Comencem per on va començar el curs tècnic, els algorismes del mòdul 3: cerca no informada (BFS, DFS), cost uniforme, A* amb heurística, minimax amb poda alfa-beta i optimització amb cerca local, recuit simulat i algorismes genètics. Tots els exercicis fan servir el mapa de repartiment de NovaMarket (GRAF_CIUTAT i COORDENADES de 03-02) i l'assignació de comandes entre Getafe i Zaragoza de 03-04, de manera que les xifres que ja coneixes (17,0 km fins al Retiro, 39,0 km del viatjant, 257 € de l'assignació) et serviran de vara de mesurar. Tot és Python pur amb la biblioteca estàndard.

Com treballar la lliçó: llegeix l'enunciat i les pistes, intenta resoldre'l al teu editor (mitja hora per exercici és raonable; el repte final, una hora), i només aleshores compara amb la solució i llegeix la retroalimentació. Si t'encalles, torna a la lliçó de referència que s'indica a cada recordatori; copiar el codi de 03-02 o 03-04 i adaptar-lo és exactament el que faria un professional. La dificultat creix de l'exercici 1 al 6.

Contingut

Preparació comuna: graf, coordenades i utilitats
Exercici 1: BFS i DFS, barris assolibles i un carrer tallat
Exercici 2: Dijkstra des del magatzem, camins i el millor punt de repartiment
Exercici 3: A* amb un barri nou, admissibilitat i nodes expandits
Exercici 4: minimax i alfa-beta a la guerra de preus a dues setmanes
Exercici 5: viatjant amb finestres horàries, ascens de turó davant de recuit
Exercici 6 (repte): assignació amb capacitat i cost de ruta amb un algorisme genètic
Errors Comuns i Consells
Conclusió

Preparació comuna: graf, coordenades i utilitats

Desa això com a nm_graf.py (o enganxa-ho al principi de cada script): és el mapa de 03-02 amb les seves dues utilitats. Tota la resta es construeix a sobre.

from collections import deque
import heapq, math, random, itertools

GRAF_CIUTAT = {
    "Almacen_Getafe": [("Leganes", 4.5), ("Villaverde", 5.0)],
    "Leganes":        [("Almacen_Getafe", 4.5), ("Carabanchel", 4.5), ("Villaverde", 6.5)],
    "Villaverde":     [("Almacen_Getafe", 5.0), ("Leganes", 6.5), ("Usera", 4.5), ("Vallecas", 7.5)],
    "Carabanchel":    [("Leganes", 4.5), ("Usera", 4.5), ("Arganzuela", 5.0)],
    "Usera":          [("Villaverde", 4.5), ("Carabanchel", 4.5), ("Arganzuela", 3.5), ("Vallecas", 5.5)],
    "Vallecas":       [("Villaverde", 7.5), ("Usera", 5.5), ("Retiro", 6.0)],
    "Arganzuela":     [("Carabanchel", 5.0), ("Usera", 3.5), ("Retiro", 4.0)],
    "Retiro":         [("Arganzuela", 4.0), ("Vallecas", 6.0)],
}
COORDENADES = {"Almacen_Getafe": (0, 0), "Leganes": (-3, 3), "Villaverde": (3, 3), "Carabanchel": (-2, 7),
               "Usera": (2, 7), "Vallecas": (7, 8), "Arganzuela": (1, 10), "Retiro": (4, 12)}

def reconstruir_cami(pares, objectiu):
    cami = [objectiu]
    while pares[cami[-1]] is not None:
        cami.append(pares[cami[-1]])
    return cami[::-1]

def cost_cami(graf, cami):
    return sum(dict(graf[a])[b] for a, b in zip(cami, cami[1:]))

Exercici 1: BFS i DFS, barris assolibles i un carrer tallat

Recordatori (03-02, seccions 5 i 6). BFS fa servir una cua FIFO i troba el camí amb menys trams (no menys quilòmetres); DFS fa servir una pila i retorna el primer camí que troba, amb poca memòria i sense garantia de qualitat. Tots dos fan servir el diccionari pares com a registre de visitats.

Enunciat. El Diego vol saber, per al repartiment d'aquest matí des d'Almacen_Getafe:

Quins barris són assolibles i a quants trams és cadascun (una funció assolibles_bfs(graf, inici) que retorni {barri: nre. de trams}).
El camí amb menys trams fins a Vallecas amb BFS, i el que retorna DFS; compara trams i quilòmetres.
Unes obres a l'M-40 tallen el carrer Villaverde–Vallecas. Escriu sense_aresta(graf, a, b) que retorni una còpia del graf sense aquest carrer en tots dos sentits (sense modificar l'original) i repeteix les preguntes 1 i 2. Quants carrers cal tallar perquè Vallecas deixi de ser assolible?

Pistes: a la pregunta 1 n'hi ha prou amb el bucle de BFS anotant trams[vei] = trams[node] + 1; per copiar el graf fes servir una comprensió de diccionari que filtri l'aresta {n, v} == {a, b}.

Solució

def assolibles_bfs(graf, inici):
    frontera, trams = deque([inici]), {inici: 0}
    while frontera:
        node = frontera.popleft()
        for vei, _ in graf[node]:
            if vei not in trams:                      # primera vegada que es veu: profunditat minima
                trams[vei] = trams[node] + 1
                frontera.append(vei)
    return trams

def bfs(graf, inici, objectiu):
    frontera, pares, explorats = deque([inici]), {inici: None}, []
    while frontera:
        node = frontera.popleft(); explorats.append(node)
        if node == objectiu:
            return reconstruir_cami(pares, objectiu), explorats
        for vei, _ in graf[node]:
            if vei not in pares:
                pares[vei] = node; frontera.append(vei)
    return None, explorats

def dfs(graf, inici, objectiu):
    pila, pares, explorats = [inici], {inici: None}, []
    while pila:
        node = pila.pop(); explorats.append(node)
        if node == objectiu:
            return reconstruir_cami(pares, objectiu), explorats
        for vei, _ in reversed(graf[node]):           # reversed: expandir en l'ordre de la llista
            if vei not in pares:
                pares[vei] = node; pila.append(vei)
    return None, explorats

def sense_aresta(graf, a, b):
    """Copia del graf sense el carrer a-b (en tots dos sentits); l'original no es toca."""
    return {n: [(v, d) for v, d in ady if {n, v} != {a, b}] for n, ady in graf.items()}

print(assolibles_bfs(GRAF_CIUTAT, "Almacen_Getafe"))
for nom, f in (("BFS", bfs), ("DFS", dfs)):
    c, ex = f(GRAF_CIUTAT, "Almacen_Getafe", "Vallecas")
    print(f"{nom}: {' -> '.join(c)} | trams {len(c)-1} | km {cost_cami(GRAF_CIUTAT, c)} | explorats {len(ex)}")
G2 = sense_aresta(GRAF_CIUTAT, "Villaverde", "Vallecas")
print(assolibles_bfs(G2, "Almacen_Getafe"))
c, ex = bfs(G2, "Almacen_Getafe", "Vallecas")
print(f"BFS sense el carrer: {' -> '.join(c)} | trams {len(c)-1} | km {cost_cami(G2, c)}")
G4 = sense_aresta(sense_aresta(G2, "Usera", "Vallecas"), "Retiro", "Vallecas")
print(bfs(G4, "Almacen_Getafe", "Vallecas")[0], assolibles_bfs(G4, "Almacen_Getafe"))

{'Almacen_Getafe': 0, 'Leganes': 1, 'Villaverde': 1, 'Carabanchel': 2, 'Usera': 2, 'Vallecas': 2, 'Arganzuela': 3, 'Retiro': 3}
BFS: Almacen_Getafe -> Villaverde -> Vallecas | trams 2 | km 12.5 | explorats 6
DFS: Almacen_Getafe -> Leganes -> Carabanchel -> Usera -> Vallecas | trams 4 | km 19.0 | explorats 5
{'Almacen_Getafe': 0, 'Leganes': 1, 'Villaverde': 1, 'Carabanchel': 2, 'Usera': 2, 'Arganzuela': 3, 'Vallecas': 3, 'Retiro': 4}
BFS sense el carrer: Almacen_Getafe -> Villaverde -> Usera -> Vallecas | trams 3 | km 15.0
None {'Almacen_Getafe': 0, 'Leganes': 1, 'Villaverde': 1, 'Carabanchel': 2, 'Usera': 2, 'Arganzuela': 3, 'Retiro': 4}

Lectura: els 7 barris són assolibles (el graf és connex) i BFS dona la profunditat mínima de cadascun en una sola passada. A Vallecas s'hi arriba en 2 trams (12,5 km, que aquí coincideix amb l'òptim en km); DFS explora un node menys però retorna 4 trams i 19 km. Amb el carrer Villaverde–Vallecas tallat, Vallecas passa a 3 trams per Usera (15,0 km) i el Retiro a 4; i cal tallar els tres carrers de Vallecas (Villaverde, Usera i Retiro) per aïllar-la: bfs retorna None i assolibles_bfs ja no la llista.

Retroalimentació

Error típic: modificar GRAF_CIUTAT in situ amb remove i "arrossegar" el tall als exercicis següents; la còpia amb comprensió evita aquest estat ocult.
Un altre: treure l'aresta en un sol sentit; el graf és no dirigit i cal filtrar a les dues llistes (per això comparem conjunts {n, v}).
Variants: escriu dfs recursiu i comprova que retorna el mateix camí; calcula el nombre de talls mínim per aïllar cada barri (el grau del node és una cota superior); afegeix a bfs un límit de profunditat i observa quan deixa de trobar el Retiro.

Exercici 2: Dijkstra des del magatzem, camins i el millor punt de repartiment

Recordatori (03-02 secció 7 i 03-04 secció 3). La cerca de cost uniforme (Dijkstra) expandeix sempre el node de menor cost acumulat g amb un monticle (heapq), pot reassignar el pare d'un node si apareix un camí millor i descarta les entrades obsoletes del monticle. Executada sense objectiu, dona la distància mínima a tots els nodes.

Enunciat. Escriu dijkstra_complet(graf, origen) que retorni (dist, pares, ordre_de_tancament) per a tots els nodes i fes-la servir per a: (a) una taula amb la distància mínima des d'Almacen_Getafe a cada barri i el camí reconstruït; (b) les arestes del graf que no fa servir cap camí mínim des del magatzem; (c) la matriu completa de distàncies (executant des de cada node) i la comprovació que és simètrica; (d) la Marta es pregunta on hauria de ser un punt de repartiment urbà si es pogués triar lliurement entre els 8 nodes: el que minimitzi la suma de distàncies mínimes a tots els altres. Quin és i quant estalvia respecte del magatzem de Getafe?

Solució

def dijkstra_complet(graf, origen):
    dist, pares, frontera, tancats = {origen: 0.0}, {origen: None}, [(0.0, origen)], []
    while frontera:
        g, node = heapq.heappop(frontera)
        if node in tancats:                           # entrada obsoleta
            continue
        tancats.append(node)
        for vei, d in graf[node]:
            if vei not in dist or g + d < dist[vei]:
                dist[vei], pares[vei] = g + d, node
                heapq.heappush(frontera, (g + d, vei))
    return dist, pares, tancats

dist, pares, ordre = dijkstra_complet(GRAF_CIUTAT, "Almacen_Getafe")
for n in ordre:
    print(f"| {n} | {dist[n]:.1f} | {' -> '.join(reconstruir_cami(pares, n))} |")
usades = {frozenset((pares[n], n)) for n in pares if pares[n]}
totes = {frozenset((a, b)) for a in GRAF_CIUTAT for b, _ in GRAF_CIUTAT[a]}
print("Arestes no usades:", sorted(tuple(sorted(e)) for e in totes - usades))
MATRIU = {n: dijkstra_complet(GRAF_CIUTAT, n)[0] for n in GRAF_CIUTAT}
print("Simetrica:", all(MATRIU[a][b] == MATRIU[b][a] for a in MATRIU for b in MATRIU))
for n in MATRIU:
    print(f"{n:15s} suma {sum(MATRIU[n].values()):5.1f}  mes llunya: {max(MATRIU[n], key=MATRIU[n].get)}")

Barri (ordre de tancament)	km	Camí mínim
Almacen_Getafe	0,0	—
Leganes	4,5	Getafe → Leganes
Villaverde	5,0	Getafe → Villaverde
Carabanchel	9,0	Getafe → Leganes → Carabanchel
Usera	9,5	Getafe → Villaverde → Usera
Vallecas	12,5	Getafe → Villaverde → Vallecas
Arganzuela	13,0	Getafe → Villaverde → Usera → Arganzuela
Retiro	17,0	Getafe → Villaverde → Usera → Arganzuela → Retiro

Arestes no usades: [('Arganzuela', 'Carabanchel'), ('Carabanchel', 'Usera'), ('Leganes', 'Villaverde'), ('Retiro', 'Vallecas'), ('Usera', 'Vallecas')]
Simetrica: True
Almacen_Getafe  suma  70.5  mes llunya: Retiro
Leganes         suma  61.5  mes llunya: Vallecas
Villaverde      suma  52.5  mes llunya: Retiro
Carabanchel     suma  51.0  mes llunya: Vallecas
Usera           suma  44.0  mes llunya: Almacen_Getafe
Vallecas        suma  64.5  mes llunya: Leganes
Arganzuela      suma  52.0  mes llunya: Almacen_Getafe
Retiro          suma  69.0  mes llunya: Almacen_Getafe

Els camins mínims des del magatzem formen un arbre (7 arestes per a 7 barris; les altres 5 del graf no es fan servir). Els nodes es tanquen en ordre creixent de distància, la propietat que garanteix l'òptim amb costos positius. La matriu és la de 03-04 i és simètrica perquè el graf és no dirigit. I el millor punt de repartiment seria Usera (44,0 km de suma davant dels 70,5 del magatzem): és a menys de 10 km de qualsevol barri; a la pràctica és la lògica dels microhubs urbans d'última milla.

Retroalimentació

Error típic: comprovar l'objectiu o "tancar" en generar un node en lloc de fer-ho en treure'l del monticle; a 03-02 vam veure que això retorna 18,5 km al Retiro en lloc de 17,0. Aquí, a més, el pares s'ha de poder sobreescriure: si el protegeixes amb if vei not in pares com a BFS, Arganzuela es queda amb el camí per Carabanchel (14,0) en lloc del d'Usera (13,0).
Comparar amb l'exercici 1: BFS i Dijkstra coincideixen en trams tret del Retiro (3 trams per Vallecas, 18,5 km, davant de 4 trams i 17,0 km).
Variant: converteix els km en minuts amb velocitats diferents per carrer (per exemple, 3 min/km a Usera–Arganzuela per trànsit) i comprova si canvia l'arbre; l'algorisme no canvia, només els pesos.

Exercici 3: A* amb un barri nou, admissibilitat i nodes expandits

Recordatori (03-02, seccions 8 i 10). A* expandeix el node de menor f = g + h. Amb h admissible (mai no sobreestima) i consistent (h(n) ≤ c(n, n') + h(n'), la desigualtat triangular) és òptim i expandeix menys nodes que cost uniforme; h = 0 el converteix exactament en cost uniforme.

Enunciat. NovaMarket obre repartiment a Moratalaz, a les coordenades (8, 11), connectat per dos carrers nous: Vallecas–Moratalaz 3,5 km i Retiro–Moratalaz 4,5 km.

Escriu afegir_barri(graf, coords, nom, xy, arestes) que retorni còpies ampliades del graf i les coordenades.
Comprova que l'heurística euclidiana continua sent consistent: per a cada aresta a–b, la distància en línia recta no ha de superar els km del carrer. Comprova també l'admissibilitat cap a Moratalaz: h(n, Moratalaz) ≤ distància mínima real per a tots els n (fes servir dijkstra_complet des de Moratalaz).
Resol Getafe → Moratalaz amb cost uniforme i amb A*, i compara km i nodes expandits.
El Diego proposa registrar el carrer Vallecas–Moratalaz amb 3,0 km ("hi ha una drecera"). Què passa amb l'heurística? I si en lloc d'això multipliques h per 2 per "accelerar" A*? Busca un parell origen-destinació en què A* deixi de ser òptim.

Solució

def afegir_barri(graf, coords, nom, xy, arestes):
    g = {n: llista[:] for n, llista in graf.items()}; c = dict(coords)
    g[nom], c[nom] = [], xy
    for vei, km in arestes:
        g[nom].append((vei, km)); g[vei].append((nom, km))
    return g, c

def heuristica(coords, n, objectiu, w=1.0):
    (x1, y1), (x2, y2) = coords[n], coords[objectiu]
    return w * math.hypot(x2 - x1, y2 - y1)

def arestes_no_consistents(graf, coords):
    return [(a, b, km, round(heuristica(coords, a, b), 2)) for a in graf for b, km in graf[a]
            if heuristica(coords, a, b) > km + 1e-9]

def no_admissibles(graf, coords, objectiu):
    real = dijkstra_complet(graf, objectiu)[0]
    return [(n, round(heuristica(coords, n, objectiu), 2), real[n]) for n in graf
            if heuristica(coords, n, objectiu) > real[n] + 1e-9]

def a_estrella(graf, coords, inici, objectiu, w=1.0):
    h = lambda n: heuristica(coords, n, objectiu, w)          # w=0 -> cost uniforme
    frontera, pares, millor_g, tancats = [(h(inici), 0.0, inici)], {inici: None}, {inici: 0.0}, []
    while frontera:
        f, g, node = heapq.heappop(frontera)
        if node in tancats: continue
        tancats.append(node)
        if node == objectiu:
            return reconstruir_cami(pares, objectiu), g, tancats
        for vei, d in graf[node]:
            if vei not in millor_g or g + d < millor_g[vei]:
                millor_g[vei], pares[vei] = g + d, node
                heapq.heappush(frontera, (g + d + h(vei), g + d, vei))
    return None, math.inf, tancats

G_M, C_M = afegir_barri(GRAF_CIUTAT, COORDENADES, "Moratalaz", (8, 11), [("Vallecas", 3.5), ("Retiro", 4.5)])
print("No consistents:", arestes_no_consistents(G_M, C_M), "| no admissibles:", no_admissibles(G_M, C_M, "Moratalaz"))
for nom, w in (("Cost uniforme", 0.0), ("A*", 1.0)):
    c, g, ex = a_estrella(G_M, C_M, "Almacen_Getafe", "Moratalaz", w)
    print(f"{nom}: {' -> '.join(c)} | {g} km | expandits {len(ex)}: {ex}")
G_3, C_3 = afegir_barri(GRAF_CIUTAT, COORDENADES, "Moratalaz", (8, 11), [("Vallecas", 3.0), ("Retiro", 4.5)])
print("Amb 3,0 km:", arestes_no_consistents(G_3, C_3), no_admissibles(G_3, C_3, "Moratalaz"))
for a in G_M:                                                    # heuristica inflada (w=2): perd l'optim?
    for b in G_M:
        if a != b and a_estrella(G_M, C_M, a, b, 2.0)[1] > a_estrella(G_M, C_M, a, b, 0.0)[1]:
            print("w=2 NO optim:", a, "->", b, a_estrella(G_M, C_M, a, b, 2.0)[1], "davant de", a_estrella(G_M, C_M, a, b, 0.0)[1])

No consistents: [] | no admissibles: []
Cost uniforme: Almacen_Getafe -> Villaverde -> Vallecas -> Moratalaz | 16.0 km | expandits 8: ['Almacen_Getafe', 'Leganes', 'Villaverde', 'Carabanchel', 'Usera', 'Vallecas', 'Arganzuela', 'Moratalaz']
A*: Almacen_Getafe -> Villaverde -> Vallecas -> Moratalaz | 16.0 km | expandits 4: ['Almacen_Getafe', 'Villaverde', 'Vallecas', 'Moratalaz']
Amb 3,0 km: [('Vallecas', 'Moratalaz', 3.0, 3.16), ('Moratalaz', 'Vallecas', 3.0, 3.16)] [('Vallecas', 3.16, 3.0)]
w=2 NO optim: Vallecas -> Leganes 14.5 davant de 14.0
w=2 NO optim: Moratalaz -> Leganes 18.0 davant de 17.5

Node	h(n, Moratalaz)	Distància real	h ≤ real?
Almacen_Getafe	13,60	16,0	sí
Villaverde	9,43	11,0	sí
Usera	7,21	9,0	sí
Vallecas	3,16	3,5	sí
Retiro	4,12	4,5	sí

A* arriba a Moratalaz en 16,0 km expandint 4 nodes (va de dret per Villaverde i Vallecas) davant dels 8 de cost uniforme, que obre Leganés, Carabanchel, Usera i Arganzuela sense necessitat; sumant els 72 parells origen-destinació del graf ampliat, A* expandeix 223 nodes i cost uniforme 396. Amb la "drecera" de 3,0 km el carrer és més curt que la línia recta (3,16 km): l'heurística deixa de ser consistent i de ser admissible a Vallecas; en aquest graf A* continua encertant (perdre la garantia no obliga a fallar), però ja no està garantit. Amb h × 2 sí que falla: de Vallecas a Leganés retorna 14,5 km en lloc de 14,0, perquè l'heurística inflada li fa descartar el camí òptim per semblar car.

Retroalimentació

Error típic: desar al monticle (h, node) o (g, node) en lloc de (f, g, node); i oblidar que la comprovació d'admissibilitat necessita les distàncies reals (Dijkstra des de l'objectiu), no les rectes.
La comprovació per arestes (consistència) és la útil en producció: és local, barata i no depèn de l'objectiu. Si una dada de carrer viola la recta, gairebé sempre és un error de dades (com la "drecera" del Diego), no una carretera màgica.
Variants: fes servir la distància Manhattan |dx| + |dy| com a heurística i comprova si és admissible en aquest mapa (no ho és en general per a carrers en diagonal); mesura expandits amb w = 1,2 (A* "ponderat", que sacrifica garantia per velocitat i es fa servir en videojocs).

Exercici 4: minimax i alfa-beta a la guerra de preus a dues setmanes

Recordatori (03-03, seccions 4, 6 i 8). Minimax recorre l'arbre de joc en profunditat i retorna el valor que MAX es pot garantir amb un MIN perfecte. La poda alfa-beta dona el mateix resultat sense visitar branques que no poden canviar la decisió; el seu estalvi depèn de l'ordre dels fills. minimax_generic(arbre, utilitats, node, es_max) treballa sobre un arbre de diccionaris.

Enunciat. La Marta amplia la guerra de preus del televisor de 03-03 a dues setmanes: NovaMarket tria (mantenir, baixar 5 %, baixar 10 %); el competidor respon (manté, iguala/baixa 5 %, baixa encara més); i a la segona setmana NovaMarket pot mantenir el seu preu o ajustar (baixar un altre 5 %). Les fulles són el marge acumulat de les dues setmanes (milers d'euros):

NovaMarket	Competidor	mantenir / ajustar
mantenir	manté	24 / 21
mantenir	baixa 5 %	10 / 11
mantenir	baixa 10 %	5 / 9
baixar 5 %	manté	27 / 22
baixar 5 %	iguala	15 / 13
baixar 5 %	baixa 10 %	8 / 11
baixar 10 %	manté	25 / 18
baixar 10 %	iguala	11 / 9
baixar 10 %	baixa 15 %	7 / 6

Construeix l'arbre com a diccionaris, calcula el valor minimax de cada opció inicial i la recomanació; escriu alfabeta_generic amb un comptador de nodes visitats i compara: minimax, alfa-beta amb l'ordre de la taula, alfa-beta provant primer l'opció que va guanyar a 03-03 (baixar_5), i alfa-beta amb l'ordre perfecte (fills ordenats pel seu valor). Canvia la recomanació respecte del joc d'una setmana (3/5/4)?

Solució

ARBRE = {"inici": ["mantenir", "baixar_5", "baixar_10"],
         "mantenir": ["m/c_mante", "m/c_baixa5", "m/c_baixa10"],
         "baixar_5":  ["b5/c_mante", "b5/c_iguala", "b5/c_baixa10"],
         "baixar_10": ["b10/c_mante", "b10/c_iguala", "b10/c_baixa15"]}
MARGE = {"m/c_mante": (24, 21), "m/c_baixa5": (10, 11), "m/c_baixa10": (5, 9),
         "b5/c_mante": (27, 22), "b5/c_iguala": (15, 13), "b5/c_baixa10": (8, 11),
         "b10/c_mante": (25, 18), "b10/c_iguala": (11, 9), "b10/c_baixa15": (7, 6)}
UTIL = {}
for resp, (m, a) in MARGE.items():                     # tercer nivell: mantenir / ajustar
    ARBRE[resp] = [resp + "/mantenir", resp + "/ajustar"]
    UTIL[resp + "/mantenir"], UTIL[resp + "/ajustar"] = m, a

def minimax_generic(arbre, util, node, es_max, compt):
    compt[0] += 1
    if node in util: return util[node]
    valors = [minimax_generic(arbre, util, f, not es_max, compt) for f in arbre[node]]
    return max(valors) if es_max else min(valors)

def alfabeta_generic(arbre, util, node, es_max, compt, alfa=-math.inf, beta=math.inf):
    compt[0] += 1
    if node in util: return util[node]
    millor = -math.inf if es_max else math.inf
    for f in arbre[node]:
        v = alfabeta_generic(arbre, util, f, not es_max, compt, alfa, beta)
        if es_max: millor, alfa = max(millor, v), max(alfa, v)
        else:      millor, beta = min(millor, v), min(beta, v)
        if alfa >= beta: break                          # PODA
    return millor

def ordenar(arbre, util, node, es_max):
    """Ordre perfecte: fills de millor a pitjor per a qui mou (fa servir el mateix minimax, nomes per a l'experiment)."""
    if node in util: return util[node]
    vals = {f: ordenar(arbre, util, f, not es_max) for f in arbre[node]}
    arbre[node] = sorted(arbre[node], key=vals.get, reverse=es_max)
    return max(vals.values()) if es_max else min(vals.values())

for op in ARBRE["inici"]:
    print(f"{op:9s} -> garanteix {minimax_generic(ARBRE, UTIL, op, False, [0])}")
c = [0]; print("minimax:", minimax_generic(ARBRE, UTIL, "inici", True, c), "nodes", c[0])
c = [0]; print("alfa-beta ordre taula:", alfabeta_generic(ARBRE, UTIL, "inici", True, c), "nodes", c[0])
import copy
A2 = copy.deepcopy(ARBRE); A2["inici"] = ["baixar_5", "mantenir", "baixar_10"]
c = [0]; print("alfa-beta baixar_5 primer:", alfabeta_generic(A2, UTIL, "inici", True, c), "nodes", c[0])
A3 = copy.deepcopy(ARBRE); ordenar(A3, UTIL, "inici", True)
c = [0]; print("alfa-beta ordre perfecte:", alfabeta_generic(A3, UTIL, "inici", True, c), "nodes", c[0])

mantenir  -> garanteix 9
baixar_5  -> garanteix 11
baixar_10 -> garanteix 7
minimax: 11 nodes 31
alfa-beta ordre taula: 11 nodes 28
alfa-beta baixar_5 primer: 11 nodes 25
alfa-beta ordre perfecte: 11 nodes 17

La recomanació continua sent baixar un 5 % (garanteix 11.000 € en dues setmanes), però l'ordre de les altres dues canvia: mantenir (9) avança baixar 10 % (7), que al joc d'una setmana era la segona opció; amb més horitzó, la baixada agressiva deixa sense marge de maniobra a la segona setmana. Pel que fa a la poda: l'arbre té 31 nodes; alfa-beta amb l'ordre de la taula en poda 3 (a baixar_10, quan c_iguala val 11 ≤ α = 11 ja no cal mirar c_baixa15); provar primer la millor jugada coneguda puja l'estalvi a 6 nodes, i l'ordre perfecte gairebé el redueix a la meitat (17). És la regla de 03-03: la poda val el que valgui l'ordenació.

Retroalimentació

Error típic: fer servir > en lloc de >= a la condició de poda (poda menys del que cal) o actualitzar α en nodes MIN i β en nodes MAX (poda de més i retorna valors incorrectes). Comprova sempre que alfa-beta retorna el mateix valor que minimax.
ordenar fa trampa (fa servir el resultat per ordenar); en un motor real l'ordenació es basa en heurístiques barates o en cerques anteriors més superficials (aprofundiment iteratiu).
Variants: afegeix a l'arrel una quarta opció "pujar 5 %" amb fulles que t'inventis i observa quant poda alfa-beta segons on la col·loquis; converteix les fulles en valors esperats donant al competidor probabilitats (0,5 / 0,3 / 0,2) en lloc de suposar-lo perfecte (expectimax) i compara la recomanació.

Exercici 5: viatjant amb finestres horàries, ascens de turó davant de recuit

Recordatori (03-04, seccions 3-7). El viatjant es representa com una permutació dels lliuraments; la funció objectiu suma la ruta tancada amb la matriu de distàncies mínimes (MATRIU de l'exercici 2). L'ascens de turó per intercanvi s'encalla en òptims locals i es rescata amb reinicis; el recuit simulat accepta empitjoraments amb probabilitat e^(−Δ/T) i refreda a poc a poc. Amb 7 lliuraments la força bruta (5.040 permutacions) dona l'òptim exacte per validar.

Enunciat. La furgoneta surt de Getafe a les 8:00 i fa 30 km/h de mitjana (2 min/km). Dos clients tenen lliurament prioritari: Vallecas abans de les 8:30 (minut 30) i Carabanchel abans de les 8:50 (minut 50). Defineix el cost d'una ruta com a minuts de la ruta tancada + 3 × minuts totals de retard a les prioritàries (arribar tard costa el triple que conduir). (a) Calcula amb força bruta la ruta òptima i compara-la amb la de 39,0 km de 03-04: quant es retarda aquesta ruta i quant costa? (b) Resol amb ascens de turó simple, amb 1/5/10/20 reinicis i amb recuit simulat; per a cada mètode, repeteix amb 20 llavors i anota en quantes assoleix l'òptim i quantes avaluacions fa servir. (c) Si el recuit queda per sota de l'ascens amb reinicis, prova de refredar més a poc a poc.

Solució

MIN_PER_KM, FINESTRES, PES_RETARD = 2.0, {"Vallecas": 30, "Carabanchel": 50}, 3.0
LLIURAMENTS = [n for n in GRAF_CIUTAT if n != "Almacen_Getafe"]

def avaluar_ruta(ruta, dist=MATRIU, origen="Almacen_Getafe", detall=False):
    rellotge = retard = 0.0; arribades = {}; anterior = origen
    for parada in ruta:
        rellotge += dist[anterior][parada] * MIN_PER_KM; arribades[parada] = rellotge
        if parada in FINESTRES: retard += max(0.0, rellotge - FINESTRES[parada])
        anterior = parada
    rellotge += dist[anterior][origen] * MIN_PER_KM
    cost = rellotge + PES_RETARD * retard
    return (cost, rellotge, retard, arribades) if detall else cost

def forca_bruta(lliuraments):
    return min(((avaluar_ruta(list(o)), list(o)) for o in itertools.permutations(lliuraments)), key=lambda t: t[0])

def ascens_turo(ruta):
    actual, c_actual, avals = ruta[:], avaluar_ruta(ruta), 1
    while True:
        millor, c_millor = None, c_actual
        for i in range(len(actual)):
            for j in range(i + 1, len(actual)):
                v = actual[:]; v[i], v[j] = v[j], v[i]; c = avaluar_ruta(v); avals += 1
                if c < c_millor: millor, c_millor = v, c
        if millor is None: return actual, c_actual, avals
        actual, c_actual = millor, c_millor

def ascens_amb_reinicis(lliuraments, n, llavor=0):
    rng, millor, millor_c, total = random.Random(llavor), None, math.inf, 0
    for _ in range(n):
        ini = lliuraments[:]; rng.shuffle(ini); r, c, av = ascens_turo(ini); total += av
        if c < millor_c: millor, millor_c = r, c
    return millor, millor_c, total

def recuit_simulat(ruta, T0=20.0, refredament=0.995, T_min=0.05, llavor=0):
    rng = random.Random(llavor); actual, c_actual = ruta[:], avaluar_ruta(ruta)
    millor, millor_c, T, avals = actual[:], c_actual, T0, 1
    while T > T_min:
        i, j = sorted(rng.sample(range(len(actual)), 2))
        vei = actual[:]; vei[i:j + 1] = reversed(vei[i:j + 1])                # 2-opt
        c_v = avaluar_ruta(vei); avals += 1; delta = c_v - c_actual
        if delta < 0 or rng.random() < math.exp(-delta / T):
            actual, c_actual = vei, c_v
            if c_actual < millor_c: millor, millor_c = actual[:], c_actual
        T *= refredament
    return millor, millor_c, avals

opt_c, opt = forca_bruta(LLIURAMENTS)
print("Optim:", opt_c, opt, avaluar_ruta(opt, detall=True)[1:])
print("Ruta 39,0 km:", avaluar_ruta(["Leganes", "Carabanchel", "Arganzuela", "Retiro", "Vallecas", "Usera", "Villaverde"], detall=True))
rng = random.Random(7); ini = LLIURAMENTS[:]; rng.shuffle(ini)
print("Inicial:", avaluar_ruta(ini), "| ascens simple:", ascens_turo(ini)[1:])
for n in (1, 5, 10, 20):
    res = [ascens_amb_reinicis(LLIURAMENTS, n, s) for s in range(20)]
    print(f"ascens {n:2d} reinicis: {sum(r[1] == opt_c for r in res)}/20 optims, ~{sum(r[2] for r in res)//20} avaluacions")
for T0, refr in ((20, 0.995), (20, 0.998), (20, 0.999)):
    res = [recuit_simulat(ini, T0, refr, llavor=s) for s in range(20)]
    print(f"recuit T0={T0} refr={refr}: {sum(r[1] == opt_c for r in res)}/20 optims, ~{sum(r[2] for r in res)//20} avaluacions")

Optim: 99.0 ['Villaverde', 'Vallecas', 'Usera', 'Carabanchel', 'Arganzuela', 'Retiro', 'Leganes'] (99.0, 0.0, {'Villaverde': 10.0, 'Vallecas': 25.0, 'Usera': 36.0, 'Carabanchel': 45.0, 'Arganzuela': 55.0, 'Retiro': 63.0, 'Leganes': 90.0})
Ruta 39,0 km: (132.0, 78.0, 18.0, {'Leganes': 9.0, 'Carabanchel': 18.0, 'Arganzuela': 28.0, 'Retiro': 36.0, 'Vallecas': 48.0, ...})
Inicial: 392.0 | ascens simple: (109.0, 106)
ascens  1 reinicis: 3/20 optims, ~90 avaluacions
ascens  5 reinicis: 15/20 optims, ~449 avaluacions
ascens 10 reinicis: 20/20 optims, ~888 avaluacions
ascens 20 reinicis: 20/20 optims, ~1818 avaluacions
recuit T0=20 refr=0.995: 8/20 optims, ~1197 avaluacions
recuit T0=20 refr=0.998: 14/20 optims, ~2994 avaluacions
recuit T0=20 refr=0.999: 19/20 optims, ~5990 avaluacions

Les finestres canvien la ruta del tot: l'òptima (99 min = 49,5 km) surt cap a Villaverde i Vallecas (minut 25), segueix per Usera fins a Carabanchel (45), i només després puja a Arganzuela i el Retiro per tornar per Leganés; compleix les dues finestres amb retard zero i hi ha dues rutes empatades (Arganzuela/Retiro en qualsevol ordre). La ruta més curta en km (78 min) arriba a Vallecas al minut 48, 18 tard: 78 + 3 × 18 = 132. Un ascens simple des d'una ruta aleatòria (392) es queda a 109 (Vallecas–Carabanchel–Retiro…, un òptim local que ja compleix les finestres però fa una marrada); amb 10 reinicis encerta sempre amb menys de 900 avaluacions (davant de 5.040 de la força bruta). El recuit amb els paràmetres de 03-04 només encerta 8 de 20 vegades: la penalització crea un paisatge més "rugós" (un intercanvi pot sumar 3 × 20 minuts de cop) i cal refredar més a poc a poc: amb 0,999 encerta 19 de 20, a canvi de 6.000 avaluacions. En aquest problema petit, l'ascens amb reinicis és el mètode més eficient.

Retroalimentació

Error típic: comptar el retard només a l'última prioritària o no acumular-lo; i calcular la ruta oberta (oblidar la tornada al magatzem), cosa que canvia l'òptim.
Un altre: comparar mètodes amb una llavor. Amb una sola execució, el recuit de 0,995 pot encertar (la llavor 0 ho fa) i semblar igual de bo; la taula de 20 llavors és l'única comparació honesta, la mateixa disciplina que la validació creuada de 04-05.
Variants: penalitza també arribar massa d'hora (el client no hi és); afegeix una tercera finestra i observa quan deixa d'existir una ruta sense retard; fes servir la instància de 15 adreces de 03-04 (generar_adreces(15)) amb finestres per a dues d'elles, on la força bruta ja no serveix i només queda comparar mètodes entre si.

Exercici 6 (repte): assignació amb capacitat i cost de ruta amb un algorisme genètic

Recordatori (03-04, seccions 8 i 9). A l'assignació de comandes, cada solució és una llista d'etiquetes (un magatzem per comanda), la restricció de capacitat es converteix en penalització (20 € per caixa d'excés) i la cerca local canvia una comanda de magatzem cada vegada. Un algorisme genètic manté una població, selecciona per torneig, encreua i muta, i conserva els millors per elitisme. Validar en petit contra la força bruta és obligatori.

Enunciat. Sistemes ha afegit al model un cost de transport per zona: cada parella (magatzem, zona) amb almenys una comanda assignada obre una ruta amb un cost fix, segons la taula; els costos per caixa i les capacitats (Getafe 32, Zaragoza 30) són els de 03-04 (generar_comandes(20, llavor=11), 60 caixes). Representa cada solució com una llista de 20 bits (0 = Getafe, 1 = Zaragoza).

Cost fix de ruta (€)	centre	sud	nord-est	llevant
Getafe	20	20	60	55
Zaragoza	55	70	20	30

Escriu cost_total(gens, comandes) que retorni (cost penalitzat, enviament, rutes, exces).
Valida l'enfocament en petit: amb les comandes P007-P014 (8 comandes, 26 caixes) i capacitats 14/14, enumera les 2⁸ = 256 assignacions i compara amb la solució ingènua ("cada comanda al seu magatzem més barat").
Implementa algorisme_genetic(comandes, mida, generacions, elitisme, p_mut, k, llavor) amb encreuament d'un punt i mutació bit a bit; comprova en 20 llavors quantes vegades assoleix l'òptim de les 8 comandes.
Resol-ho per a les 20 comandes amb el genètic (10 llavors), amb ascens de turó (20 reinicis) i, com que les 2²⁰ ≈ 1 milió d'assignacions s'enumeren en uns segons, comprova l'òptim exacte. Interpreta la solució en termes de rutes obertes.

Solució

def generar_comandes(n, llavor=11):                       # el de 03-04
    rng = random.Random(llavor)
    tarifa = {"centre": (4, 7), "sud": (3, 9), "nord-est": (9, 4), "llevant": (8, 5)}   # €/caixa (Getafe, Zaragoza)
    comandes = []
    for i in range(1, n + 1):
        zona = rng.choice(list(tarifa)); caixes = rng.choice([1, 1, 2, 3, 5])
        comandes.append({"id": f"P{i:03d}", "zona": zona, "caixes": caixes,
                         "cost_getafe": tarifa[zona][0] * caixes, "cost_zaragoza": tarifa[zona][1] * caixes})
    return comandes

COMANDES = generar_comandes(20)
MAGATZEMS, CAPACITAT, PENALITZACIO = ["Getafe", "Zaragoza"], {"Getafe": 32, "Zaragoza": 30}, 20
COST_RUTA = {("Getafe", "centre"): 20, ("Getafe", "sud"): 20, ("Getafe", "nord-est"): 60, ("Getafe", "llevant"): 55,
             ("Zaragoza", "centre"): 55, ("Zaragoza", "sud"): 70, ("Zaragoza", "nord-est"): 20, ("Zaragoza", "llevant"): 30}

def cost_total(gens, comandes, capacitat=None):
    capacitat = capacitat or CAPACITAT
    enviament, carrega, rutes = 0, [0, 0], set()
    for g, p in zip(gens, comandes):
        enviament += p["cost_getafe"] if g == 0 else p["cost_zaragoza"]
        carrega[g] += p["caixes"]; rutes.add((MAGATZEMS[g], p["zona"]))
    exces = max(0, carrega[0] - capacitat["Getafe"]) + max(0, carrega[1] - capacitat["Zaragoza"])
    fix = sum(COST_RUTA[r] for r in rutes)
    return enviament + fix + PENALITZACIO * exces, enviament, fix, exces

def forca_bruta(comandes, capacitat=None):
    return min(((cost_total(g, comandes, capacitat)[0], list(g)) for g in itertools.product([0, 1], repeat=len(comandes))))

def rutes_de(gens, comandes):
    r = {}
    for g, p in zip(gens, comandes): r.setdefault((MAGATZEMS[g], p["zona"]), []).append(p["id"])
    return r

def algorisme_genetic(comandes, mida=40, generacions=60, elitisme=2, p_mut=0.05, k=3, llavor=0, capacitat=None):
    rng, n = random.Random(llavor), len(comandes)
    apt = lambda ind: cost_total(ind, comandes, capacitat)[0]           # menor cost = mes apte
    poblacio = [[rng.randint(0, 1) for _ in range(n)] for _ in range(mida)]
    historial = []
    for _ in range(generacions):
        poblacio.sort(key=apt); historial.append(apt(poblacio[0]))
        nova = [ind[:] for ind in poblacio[:elitisme]]                  # elitisme
        while len(nova) < mida:
            p1, p2 = (min(rng.sample(poblacio, k), key=apt) for _ in range(2))   # torneig
            tall = rng.randint(1, n - 1)
            fill = p1[:tall] + p2[tall:]                                # encreuament d'un punt
            nova.append([1 - g if rng.random() < p_mut else g for g in fill])   # mutacio bit a bit
        poblacio = nova
    millor = min(poblacio, key=apt)
    return millor, apt(millor), historial

def ascens(gens, comandes):
    actual, f = gens[:], cost_total(gens, comandes)[0]
    while True:
        veins = [actual[:i] + [1 - actual[i]] + actual[i + 1:] for i in range(len(actual))]
        millor = min(veins, key=lambda v: cost_total(v, comandes)[0])
        if cost_total(millor, comandes)[0] >= f: return actual, f
        actual, f = millor, cost_total(millor, comandes)[0]

# 2) validacio en petit
sub, cap8 = COMANDES[6:14], {"Getafe": 14, "Zaragoza": 14}
c8, opt8 = forca_bruta(sub, cap8)
ing8 = [0 if p["cost_getafe"] <= p["cost_zaragoza"] else 1 for p in sub]
print("8 comandes | forca bruta:", c8, opt8, cost_total(opt8, sub, cap8), rutes_de(opt8, sub))
print("8 comandes | ingenua:", cost_total(ing8, sub, cap8))
print("GA en 8:", sum(algorisme_genetic(sub, 20, 30, llavor=s, capacitat=cap8)[1] == c8 for s in range(20)), "/20 llavors")
# 4) les 20 comandes
g, c, h = algorisme_genetic(COMANDES, llavor=0)
print("GA 20 llavor 0:", c, cost_total(g, COMANDES), "| millor a la generacio", h.index(min(h)))
print("historial:", [(i, h[i]) for i in (0, 5, 10, 15, 20, 59)])
print("GA 10 llavors:", [algorisme_genetic(COMANDES, llavor=s)[1] for s in range(10)])
print("GA pobl. 80, 100 gen, mut 0,08:", [algorisme_genetic(COMANDES, 80, 100, p_mut=0.08, llavor=s)[1] for s in range(10)])
rng = random.Random(0)
print("Ascens 20 reinicis:", sorted(ascens([rng.randint(0, 1) for _ in range(20)], COMANDES)[1] for _ in range(20)))
c20, opt20 = forca_bruta(COMANDES)
print("Forca bruta 2^20:", c20, cost_total(opt20, COMANDES)); print(rutes_de(opt20, COMANDES))

8 comandes | forca bruta: 251 [0, 1, 1, 0, 1, 0, 0, 0] (251, 126, 125, 0) {('Getafe', 'sud'): ['P007', 'P010', 'P014'], ('Zaragoza', 'centre'): ['P008', 'P011'], ('Zaragoza', 'llevant'): ['P009'], ('Getafe', 'centre'): ['P012', 'P013']}
8 comandes | ingenua: (346, 96, 70, 9)
GA en 8: 16 /20 llavors
GA 20 llavor 0: 402 (402, 257, 145, 0) | millor a la generacio 15
historial: [(0, 517), (5, 496), (10, 435), (15, 402), (20, 402), (59, 402)]
GA 10 llavors: [402, 435, 402, 402, 402, 402, 402, 402, 402, 402]
GA pobl. 80, 100 gen, mut 0,08: [402, 402, 402, 402, 402, 402, 402, 402, 402, 402]
Ascens 20 reinicis: [402, 402, 402, 402, 402, 402, 402, 435, 435, 435, 435, 435, 493, 496, 506, 581, 590, 602, 608, 608]
Forca bruta 2^20: 402 (402, 257, 145, 0)
{('Zaragoza', 'llevant'): ['P001', 'P002', 'P004', 'P006', 'P009', 'P019'], ('Getafe', 'sud'): ['P003', 'P005', 'P007', 'P010', 'P014', 'P017', 'P018'], ('Getafe', 'centre'): ['P008', 'P011', 'P012', 'P013'], ('Zaragoza', 'centre'): ['P015', 'P020'], ('Zaragoza', 'nord-est'): ['P016']}

En petit, la ingènua és infactible (9 caixes d'excés, 346 €) i l'òptim (251 €) obre quatre rutes, inclosa una Zaragoza–centre cara (55 €) perquè moure P008 i P011 (10 caixes de centre) és l'única manera de respectar 14 caixes a Getafe; el genètic amb població 20 el troba en 16 de 20 llavors (amb 256 solucions, la població inicial ja cobreix el 8 % de l'espai, així que aquí és un martell gros per a un clau petit: serveix per validar la implementació, no per presumir). A les 20 comandes, l'òptim exacte és 402 € = 257 € d'enviament (la mateixa assignació factible de 03-04) + 145 € de les cinc rutes; el cost fix no canvia l'assignació perquè la capacitat ajustada ja obliga a obrir Zaragoza–centre, però sí que canvia el paisatge: l'ascens de turó només arriba a l'òptim en 7 de 20 reinicis (tancar o obrir una ruta exigeix moure diverses comandes alhora, i el veïnat d'un bit no ho veu), mentre que el genètic l'assoleix en 9 de 10 llavors amb la configuració bàsica i en 10 de 10 amb més població i mutació, amb unes 2.400-8.000 avaluacions davant del milió de la força bruta.

Retroalimentació

Error típic: mutar amb probabilitat p_mut l'individu (un bit) en lloc de cada bit; totes dues funcionen, però canvien el significat del paràmetre. Un altre: oblidar l'elitisme i veure com el millor cost puja d'una generació a l'altra.
Si la penalització per caixa fos menor que el cost d'una ruta (per exemple, amb capacitats 36/36 l'òptim prefereix pagar 2 caixes d'excés, 40 €, abans que obrir Zaragoza–centre per 55 €), l'algorisme fa el que diu la funció objectiu, no el que vol el Diego: quan la capacitat és dura, puja la penalització fins que cap solució infactible surti a compte.
Variants: substitueix l'encreuament d'un punt per encreuament uniforme (cada bit del pare 1 o 2 a l'atzar); afegeix un tercer magatzem (representació amb 0/1/2); mesura, per a mida 30 i 40 comandes, el temps del genètic davant del de la força bruta (2³⁰ ja és inabordable).

Errors Comuns i Consells

Copiar el codi de 03-02/03-04 sense rellegir els detalls (test de l'objectiu en treure del monticle, pares sobreescrivible a Dijkstra, >= a la poda): els errors subtils del mòdul 3 reapareixen aquí. Tingues a mà les traces d'aquelles lliçons per comparar.
Validar només amb una execució. En tot allò estocàstic (reinicis, recuit, genètic) compara amb moltes llavors i contra la força bruta en una versió reduïda; sense això no saps si la teva implementació és correcta o afortunada.
Barrejar unitats a la funció objectiu (km, minuts, euros): decideix una unitat, converteix-ho tot a aquesta (aquí minuts a l'exercici 5, euros al 6) i documenta els factors de conversió (MIN_PER_KM, PES_RETARD).
Penalitzacions mal calibrades: massa baixes i l'algorisme "compra" la infracció; massa altes i aixafen les diferències reals. Comprova sempre que la millor solució trobada té excés 0 (o que la infracció és deliberada).
No comprovar l'heurística: la consistència per arestes és un test barat que s'hauria d'executar cada vegada que canvien les dades del mapa.
Consell: desa cada exercici com un script amb una funció main() i una comprovació (assert cost == 402); són les proves de 07-04 aplicades a algorismes.

Conclusió

Has tornat a recórrer el mòdul 3 sense que la lliçó et portés de la mà: BFS i DFS amb un carrer tallat (Vallecas a 3 trams per Usera; tres talls per aïllar-la), Dijkstra amb la reconstrucció dels 7 camins mínims i el descobriment que Usera seria el millor punt de repartiment (44 km de suma davant de 70,5), A* cap a Moratalaz amb 4 nodes expandits davant de 8, la comprovació que una "drecera" de 3,0 km trenca l'admissibilitat i que una heurística inflada fa perdre l'òptim (14,5 davant de 14,0), minimax a dues setmanes (baixar 5 % continua garantint més, 31 nodes que la poda deixa en 28, 25 o 17 segons l'ordre), el viatjant amb finestres horàries (99 minuts davant dels 132 de la ruta més curta en km, amb l'ascens amb reinicis guanyant al recuit tret del refredament lent) i el genètic per a l'assignació amb cost de ruta (402 €, validat contra 256 i contra el milió d'assignacions). El fil comú: representar bé, definir la funció objectiu amb les seves unitats i penalitzacions, i validar contra un òptim conegut o contra moltes llavors.

Els exercicis següents canvien d'eina però no de disciplina: a 09-02, Pràctiques de Machine Learning, treballaràs amb els generadors de NovaMarket del mòdul 4 (neteja d'un lot brut, un pipeline de devolucions amb una característica nova, previsió de demanda amb TimeSeriesSplit, segmentació de clients i ajust de llindar amb comprovació d'equitat), sempre amb una línia base i una comparació honesta.

Exercicis d'Algorismes

Contingut

Preparació comuna: graf, coordenades i utilitats

Exercici 1: BFS i DFS, barris assolibles i un carrer tallat

Solució

Retroalimentació

Exercici 2: Dijkstra des del magatzem, camins i el millor punt de repartiment

Solució

Retroalimentació

Exercici 3: A* amb un barri nou, admissibilitat i nodes expandits

Solució

Retroalimentació

Exercici 4: minimax i alfa-beta a la guerra de preus a dues setmanes

Solució

Retroalimentació

Exercici 5: viatjant amb finestres horàries, ascens de turó davant de recuit

Solució

Retroalimentació

Exercici 6 (repte): assignació amb capacitat i cost de ruta amb un algorisme genètic

Solució

Retroalimentació

Errors Comuns i Consells

Conclusió

Fonaments d'Intel·ligència Artificial (IA)

Mòdul 1: Introducció a la Intel·ligència Artificial

Mòdul 2: Principis Bàsics de la IA

Mòdul 3: Algorismes en IA

Mòdul 4: Aprenentatge Automàtic (Machine Learning)

Mòdul 5: Xarxes Neuronals i Deep Learning

Mòdul 6: Lògica i Sistemes Experts

Mòdul 7: Eines i Llenguatges de Programació en IA

Mòdul 8: Projectes i Casos d'Estudi

Mòdul 9: Exercicis i Pràctiques

Mòdul 10: Recursos Addicionals