A la lliçó anterior vam formalitzar el mapa de repartiment de NovaMarket com el graf GRAF_CIUTAT i vam comprovar que la força bruta s'ofega tan bon punt creixen els lliuraments: avalua n! rutes i la immensa majoria són físicament impossibles. En aquesta lliçó resoldrem el problema de manera intel·ligent. Començarem pel cas més simple i més important: portar la furgoneta des d'Almacen_Getafe fins a un barri de destinació pel millor camí, construint la solució pas a pas, només a través de carreteres reals, i sense enumerar res que no faci falta. Presentarem el vocabulari de la cerca (espai d'estats, node, frontera, explorats), els criteris amb què es jutja un algorisme de cerca, i després implementarem cinc algorismes clàssics sobre el mateix graf: tres de no informats (amplada, profunditat i cost uniforme, que només coneixen el graf) i dos d'informats (voraç i A*, que a més fan servir una estimació del que falta fins a la meta). Veuràs amb traces i taules per què la cerca en amplada no sempre dona el camí més curt en quilòmetres, per què la profunditat pot retornar camins dolents, i com una heurística tan senzilla com la distància en línia recta permet a A* trobar l'òptim explorant menys. Aquests algorismes són el cor de qualsevol planificador de rutes i els reutilitzarem al projecte d'exercicis del mòdul 9 (09-01).
Contingut
- Vocabulari de la cerca: espai d'estats, node, frontera, explorats, camí i cost
- Arbre de cerca davant de graf: el problema dels estats repetits
- Com s'avalua un algorisme de cerca: completesa, optimalitat, complexitat
- L'esquema general i el graf de treball
- Cerca en amplada (BFS) amb
deque, amb traça pas a pas - Cerca en profunditat (DFS): la mateixa idea amb una pila
- Cerca de cost uniforme (Dijkstra) amb
heapq - Cerca informada: heurístiques, admissibilitat i consistència
- Cerca voraç (greedy best-first)
- A*: el millor de tots dos mons, amb traça
- Taula comparativa i quan fer servir cadascun
- Vocabulari de la cerca
Recorda la formulació de problemes de 02-01 i 03-01: estat inicial, accions, model de transició, test d'objectiu i cost. Sobre aquesta formulació, els algorismes de cerca manegen uns quants conceptes que convé fixar amb precisió, perquè apareixen al codi de tots ells:
| Terme | Definició | En el problema de la furgoneta |
|---|---|---|
| Espai d'estats | Conjunt de tots els estats assolibles des de l'inicial aplicant accions | Els 8 nodes de GRAF_CIUTAT (la furgoneta pot ser en qualsevol d'ells) |
| Node | Un estat tal com el veu la cerca, juntament amb informació de context: des de quin node s'hi ha arribat (pare) i el cost acumulat | "Usera, arribant des de Villaverde, amb 9,5 km recorreguts" |
| Expandir un node | Generar els seus successors aplicant totes les accions possibles | Des d'Usera: Villaverde, Carabanchel, Arganzuela, Vallecas |
| Frontera (o llista oberta) | Els nodes generats però encara no expandits: les opcions pendents | Els barris que sabem que podem visitar i encara no hem "mirat" |
| Explorats (o llista tancada) | Els nodes ja expandits | Barris les sortides dels quals ja hem considerat |
| Camí | Seqüència d'accions (o de nodes) des de l'inicial fins a un de donat | Almacen_Getafe -> Villaverde -> Usera |
| Cost del camí (g) | Suma dels costos de les accions del camí | 5,0 + 4,5 = 9,5 km |
| Solució | Un camí des de l'estat inicial fins a un estat objectiu; òptima si el seu cost és el mínim possible | El camí de menys quilòmetres fins a Retiro |
Tota cerca funciona repetint el mateix bucle: treure un node de la frontera, comprovar si és objectiu, i si no ho és, expandir-lo afegint els seus successors a la frontera. L'única diferència entre els algorismes d'aquesta lliçó és quin node es treu de la frontera a cada pas. Aquesta elecció és l'"estratègia de cerca", i determina si es troba solució, si és la millor i quant costa trobar-la.
- Arbre de cerca davant de graf
És important no confondre dues coses: el graf de l'espai d'estats (el mapa: 8 nodes, 12 arestes, fix) i l'arbre de cerca que l'algorisme va construint mentre explora (arrel = estat inicial; fills = successors; cada branca és un camí). El mateix estat pot aparèixer en diversos llocs de l'arbre: des de Getafe es pot arribar a Villaverde directament o passant per Leganés, i tots dos serien nodes diferents de l'arbre amb el mateix estat.
Si no controlem aquests estats repetits, l'arbre creix sense límit (Getafe → Leganés → Getafe → Leganés…) encara que el graf sigui diminut. La solució estàndard és la cerca en graf: recordar els estats ja explorats (i els que ja són a la frontera) i no tornar-los a generar. És el que fa el conjunt/diccionari pares a les nostres implementacions: a més de recordar d'on venim (per reconstruir el camí al final), serveix de "ja ho he vist". La variant sense memòria s'anomena cerca en arbre i només té sentit en espais sense cicles, com els arbres de joc de 03-03.
- Com s'avalua un algorisme de cerca
Quatre criteris, que farem servir a la taula final:
- Completesa: garanteix trobar una solució si n'hi ha?
- Optimalitat: garanteix que la solució trobada és la de menor cost?
- Complexitat temporal: quants nodes genera o expandeix? S'expressa en funció del factor de ramificació b (nombre mitjà de successors per node; al nostre graf, uns 3) i la profunditat d de la solució (nombre de passos). Un arbre de ramificació b i profunditat d té de l'ordre de bᵈ nodes, així que gairebé totes les complexitats són de la forma O(bᵈ): exponencials, com va anticipar 03-01.
- Complexitat espacial: quants nodes desa a la memòria alhora? Aquí és on més es diferencien amplada i profunditat.
- L'esquema general i el graf de treball
Treballarem sempre amb el GRAF_CIUTAT de 03-01, que reproduïm com a recordatori, més dues funcions auxiliars que tots els algorismes comparteixen: reconstruir_cami, que segueix la cadena de pares des de l'objectiu fins a l'inici, i cost_cami, que suma els quilòmetres d'un camí.
graph LR
G((Almacen_Getafe)) ---|4.5| L((Leganes))
G ---|5.0| V((Villaverde))
L ---|6.5| V
L ---|4.5| C((Carabanchel))
V ---|4.5| U((Usera))
V ---|7.5| VA((Vallecas))
C ---|4.5| U
C ---|5.0| A((Arganzuela))
U ---|3.5| A
U ---|5.5| VA
A ---|4.0| R((Retiro))
VA ---|6.0| R
from collections import deque
import heapq
import math
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)],
}
def reconstruir_cami(pares, objectiu):
"""Segueix els pares des de l'objectiu fins a l'inici i retorna el cami en ordre."""
cami = [objectiu]
while pares[cami[-1]] is not None: # l'inici es l'unic amb pare None
cami.append(pares[cami[-1]])
cami.reverse()
return cami
def cost_cami(graf, cami):
"""Suma els quilometres dels trams consecutius d'un cami."""
total = 0.0
for a, b in zip(cami, cami[1:]):
total += dict(graf[a])[b] # dict(...) converteix la llista de tuples en {vei: km}
return totalEl diccionari pares és la peça clau de totes les implementacions: pares[X] = Y significa "a X s'hi ha arribat des de Y". El node inicial té pare None, i això és el que atura el bucle de reconstruir_cami. El problema que resoldrem a totes les seccions serà anar d'Almacen_Getafe a Retiro, el barri més allunyat del magatzem, per al qual existeixen diversos camins raonables.
- Cerca en amplada (BFS)
Estratègia: expandir primer els nodes menys profunds. La frontera és una cua FIFO (deque): els nodes es treuen en el mateix ordre en què van entrar, així que primer s'expandeixen tots els que són a un pas de l'inici, després els que són a dos, etc. Va explorant el mapa "en ones concèntriques" des del magatzem.
def bfs(graf, inici, objectiu, traca=False):
frontera = deque([inici]) # cua FIFO
pares = {inici: None} # tambe fa de "ja vist"
explorats = []
while frontera:
node = frontera.popleft() # surt el mes antic
explorats.append(node)
if node == objectiu:
return reconstruir_cami(pares, objectiu), explorats
for vei, _ in graf[node]: # el pes (_) s'ignora: BFS no mira costos
if vei not in pares:
pares[vei] = node
frontera.append(vei) # entra pel final
if traca:
print(f"| {len(explorats)} | {node} | {', '.join(frontera)} | {', '.join(explorats)} |")
return None, explorats
cami, explorats = bfs(GRAF_CIUTAT, "Almacen_Getafe", "Retiro", traca=True)
print("Cami:", " -> ".join(cami))
print("Trams:", len(cami) - 1, "| km:", cost_cami(GRAF_CIUTAT, cami),
"| explorats:", len(explorats))La traça (frontera i explorats després d'expandir cada node) és aquesta:
| Pas | Node expandit | Frontera (cua) | Explorats |
|---|---|---|---|
| 1 | Almacen_Getafe | Leganes, Villaverde | Almacen_Getafe |
| 2 | Leganes | Villaverde, Carabanchel | + Leganes |
| 3 | Villaverde | Carabanchel, Usera, Vallecas | + Villaverde |
| 4 | Carabanchel | Usera, Vallecas, Arganzuela | + Carabanchel |
| 5 | Usera | Vallecas, Arganzuela | + Usera |
| 6 | Vallecas | Arganzuela, Retiro | + Vallecas |
| 7 | Arganzuela | Retiro | + Arganzuela |
| 8 | Retiro | (objectiu assolit) |
Llegeix-la amb calma: al pas 6, en expandir Vallecas, es genera Retiro per primera vegada i s'anota pares["Retiro"] = "Vallecas". Quan al pas 7 s'expandeix Arganzuela, Retiro ja és a pares i no s'actualitza, encara que el camí per Arganzuela sigui més curt en quilòmetres. BFS troba el camí amb menys trams (3), no el de menys quilòmetres: 18,5 km, quan l'òptim són 17,0 km per Villaverde–Usera–Arganzuela (4 trams). Aquest és el límit fonamental de BFS: és òptim només si totes les accions costen el mateix. És complet (si hi ha solució, la troba), i el seu cost temporal i espacial és O(bᵈ): desa a la frontera tota l'"ona" actual, cosa que en mapes grans ocupa molta memòria.
- Cerca en profunditat (DFS)
Estratègia: expandir sempre el node més profund, és a dir, seguir un camí fins al final abans de provar alternatives. El codi és literalment el de BFS canviant la cua per una pila (append/pop d'una llista): tal com vam anunciar a 03-01, l'estructura de dades defineix l'algorisme.
def dfs(graf, inici, objectiu):
pila = [inici] # pila LIFO
pares = {inici: None}
explorats = []
while pila:
node = pila.pop() # surt el mes recent
explorats.append(node)
if node == objectiu:
return reconstruir_cami(pares, objectiu), explorats
for vei, _ in reversed(graf[node]): # reversed: per expandir en l'ordre de la llista
if vei not in pares:
pares[vei] = node
pila.append(vei)
return None, explorats
cami, explorats = dfs(GRAF_CIUTAT, "Almacen_Getafe", "Retiro")
print("Cami:", " -> ".join(cami))
print("Trams:", len(cami) - 1, "| km:", cost_cami(GRAF_CIUTAT, cami),
"| explorats:", len(explorats))Cami: Almacen_Getafe -> Leganes -> Carabanchel -> Usera -> Vallecas -> Retiro Trams: 5 | km: 25.0 | explorats: 6
DFS ha explorat menys nodes (6 davant de 8), però retorna un camí clarament pitjor: 25 km, 5 trams. S'ha "ficat" per Leganés, ha seguit cap a Carabanchel i Usera, i des d'allà ha continuat per la primera sortida no visitada fins a topar amb Retiro. Característiques:
- No és òptim: retorna el primer camí que troba, no el millor.
- Pot no ser complet: en espais infinits o amb cicles sense control de repetits, pot seguir un camí sense fi i no tornar mai. Amb el nostre
parescom a control de visitats i un graf finit, sí que acaba. - El seu gran avantatge és la memòria: només desa el camí actual i els germans pendents, O(b·m) on m és la profunditat màxima, davant de l'O(bᵈ) de BFS. Per això es fa servir en problemes amb moltíssims estats on qualsevol solució val (i a la recursió de minimax de 03-03, que és una cerca en profunditat).
Una variant habitual, la cerca en profunditat limitada (tallar a una profunditat màxima) i la seva versió iterativa (aprofundir 1, 2, 3… fins a trobar solució), combina la poca memòria de DFS amb la completesa de BFS; l'esmentem per completesa, no la implementarem.
- Cerca de cost uniforme (Dijkstra)
Estratègia: expandir sempre el node de la frontera amb menor cost acumulat g. La frontera és una cua de prioritat que implementem amb heapq, un monticle binari en què heappop retorna sempre la tupla més petita. És l'algorisme de Dijkstra vist com a cerca, i a diferència de BFS sí que té en compte els quilòmetres.
def cost_uniforme(graf, inici, objectiu, traca=False):
frontera = [(0.0, inici)] # monticle de tuples (g, node): la de menor g surt primer
pares = {inici: None}
millor_g = {inici: 0.0} # millor cost conegut per arribar a cada node
explorats = []
while frontera:
g, node = heapq.heappop(frontera)
if node in explorats: # entrada obsoleta (ja l'hem tancat amb un g menor)
continue
explorats.append(node)
if node == objectiu: # el test es fa EN TREURE, no en generar
return reconstruir_cami(pares, objectiu), g, explorats
for vei, d in graf[node]:
nou_g = g + d
if vei not in millor_g or nou_g < millor_g[vei]:
millor_g[vei] = nou_g
pares[vei] = node # es pot REASSIGNAR el pare si apareix res millor
heapq.heappush(frontera, (nou_g, vei))
if traca:
print(f"| {len(explorats)} | {node} ({g}) | "
f"{', '.join(f'{n} ({c})' for c, n in sorted(frontera))} |")
return None, math.inf, explorats
cami, g, explorats = cost_uniforme(GRAF_CIUTAT, "Almacen_Getafe", "Retiro", traca=True)
print("Cami:", " -> ".join(cami), "| km:", g, "| explorats:", len(explorats))| Pas | Node expandit (g) | Frontera ordenada per g |
|---|---|---|
| 1 | Almacen_Getafe (0.0) | Leganes (4.5), Villaverde (5.0) |
| 2 | Leganes (4.5) | Villaverde (5.0), Carabanchel (9.0) |
| 3 | Villaverde (5.0) | Carabanchel (9.0), Usera (9.5), Vallecas (12.5) |
| 4 | Carabanchel (9.0) | Usera (9.5), Vallecas (12.5), Arganzuela (14.0) |
| 5 | Usera (9.5) | Vallecas (12.5), Arganzuela (13.0), Arganzuela (14.0) |
| 6 | Vallecas (12.5) | Arganzuela (13.0), Arganzuela (14.0), Retiro (18.5) |
| 7 | Arganzuela (13.0) | Arganzuela (14.0), Retiro (17.0), Retiro (18.5) |
| 8 | Retiro (17.0) | (objectiu assolit) |
Fixa't en tres detalls que expliquen per què funciona:
- Al pas 5, en expandir Usera, es descobreix que Arganzuela és a 13,0 km (per Usera) en lloc de 14,0 (per Carabanchel). Es reassigna el pare d'Arganzuela i s'insereix una nova entrada al monticle. L'antiga (14,0) queda obsoleta; quan surti, l'
if node in explorats: continuela descarta. És més simple que esborrar-la del monticle i és la tècnica habitual ("esborrat mandrós"). - Al pas 6 es genera Retiro amb 18,5 km (per Vallecas), però no es declara solució en generar-lo: s'espera que surti del monticle. Al pas 7 apareix Retiro amb 17,0 km i, com que és menor, surt abans. Si haguéssim comprovat l'objectiu en generar, hauríem retornat 18,5 km. Aquesta diferència amb BFS (que sí que pot comprovar en generar) és subtil però decisiva.
- El resultat és òptim: 17,0 km. La cerca de cost uniforme és completa i òptima sempre que els costos siguin positius, a canvi d'explorar en totes direccions sense cap idea d'on és la meta (aquí ha expandit els 8 nodes, inclòs Leganés, que és en direcció contrària).
- Cerca informada: heurístiques, admissibilitat i consistència
Els tres algorismes anteriors són no informats: només saben el que diu el graf. Un conductor humà, en canvi, sap que Retiro "queda cap al nord" i no es planteja sortir cap a Leganés. Aquesta intuïció es formalitza com una funció heurística h(n): una estimació barata del cost que falta des del node n fins a l'objectiu. L'heurística més natural en mapes és la distància en línia recta: mai no hi ha una carretera més curta que la recta, i es calcula a l'instant a partir de coordenades.
Fixem les coordenades (en quilòmetres, sobre un pla fictici amb el magatzem a l'origen) dels nodes de GRAF_CIUTAT, i l'heurística euclidiana:
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 heuristica(node, objectiu):
"""Distancia en linia recta (euclidiana) entre dos nodes, en km."""
(x1, y1), (x2, y2) = COORDENADES[node], COORDENADES[objectiu]
return math.hypot(x2 - x1, y2 - y1) # sqrt((x2-x1)² + (y2-y1)²)
for node in GRAF_CIUTAT:
print(f"{node:15s} h = {heuristica(node, 'Retiro'):.2f}")| Node | Coordenades | h(node, Retiro) en km |
|---|---|---|
| Almacen_Getafe | (0, 0) | 12,65 |
| Leganes | (−3, 3) | 11,40 |
| Villaverde | (3, 3) | 9,06 |
| Carabanchel | (−2, 7) | 7,81 |
| Usera | (2, 7) | 5,39 |
| Vallecas | (7, 8) | 5,00 |
| Arganzuela | (1, 10) | 3,61 |
| Retiro | (4, 12) | 0,00 |
Dues propietats d'una heurística determinen si A* serà òptim:
- Admissible: mai no sobreestima el cost real que falta, h(n) ≤ cost real mínim de n a l'objectiu. La distància en línia recta és admissible per construcció: la carretera sempre és igual o més llarga que la recta. Ho pots comprovar aresta per aresta al nostre graf (per exemple, Usera–Arganzuela: 3,5 km de carretera davant de 3,16 km en línia recta).
- Consistent (o monòtona): per a tot tram n → n' de cost c, es compleix h(n) ≤ c + h(n'). Intuïtivament, "l'estimació no pot baixar més del que costa el tram"; equival a la desigualtat triangular, que la distància euclidiana compleix sempre. Tota heurística consistent és admissible; a la pràctica, gairebé totes les heurístiques naturals ho són. Amb una heurística consistent, la primera vegada que A* extreu un node de la frontera ja ho fa amb el seu cost òptim, i per això podem tancar nodes (
explorats) sense tornar-los a obrir.
Una heurística que sobreestimi pot portar A* a descartar el camí òptim per semblar car (ho veuràs a l'exercici 2). Una heurística que subestimi massa (en l'extrem, h = 0) continua sent admissible però no ajuda: A* amb h = 0 és exactament la cerca de cost uniforme.
- Cerca voraç (greedy best-first)
Estratègia: expandir sempre el node que sembla més proper a la meta, és a dir, el de menor h(n), ignorant per complet el que ja s'ha recorregut (g). És la traducció directa de "tirar sempre cap on és Retiro".
def vorac(graf, inici, objectiu):
frontera = [(heuristica(inici, objectiu), inici)] # prioritat = h
pares = {inici: None}
explorats = []
while frontera:
_, node = heapq.heappop(frontera)
explorats.append(node)
if node == objectiu:
cami = reconstruir_cami(pares, objectiu)
return cami, cost_cami(graf, cami), explorats
for vei, _ in graf[node]:
if vei not in pares:
pares[vei] = node
heapq.heappush(frontera, (heuristica(vei, objectiu), vei))
return None, math.inf, explorats
cami, km, explorats = vorac(GRAF_CIUTAT, "Almacen_Getafe", "Retiro")
print("Cami:", " -> ".join(cami), "| km:", km, "| explorats:", len(explorats))És rapidíssima (només 4 nodes explorats: mai no mira cap a Leganés ni Carabanchel), però no és òptima: des de Villaverde, Vallecas (h = 5,00) sembla més a prop de Retiro que Usera (h = 5,39), així que se'n va per Vallecas, sense adonar-se que el tram Villaverde–Vallecas costa 7,5 km i el desviament total surt a 18,5 km. Ha caigut en la trampa de mirar només el futur estimat i no el passat real. A més, sense control de repetits, la voraç pot entrar en bucles (no és completa en general). La seva utilitat real és com a component d'altres mètodes i com a algorisme "d'emergència" quan el temps de resposta ho és tot.
- A*: el millor de tots dos mons
Estratègia: expandir el node amb menor f(n) = g(n) + h(n): cost real recorregut més cost estimat restant. Combina la garantia de cost uniforme (que mira g) amb la direcció de la voraç (que mira h). El codi és el de cost uniforme canviant la prioritat:
def a_estrella(graf, inici, objectiu, traca=False):
frontera = [(heuristica(inici, objectiu), 0.0, inici)] # tuples (f, g, node)
pares = {inici: None}
millor_g = {inici: 0.0}
explorats = []
while frontera:
f, g, node = heapq.heappop(frontera)
if node in explorats:
continue
explorats.append(node)
if node == objectiu:
return reconstruir_cami(pares, objectiu), g, explorats
for vei, d in graf[node]:
nou_g = g + d
if vei not in millor_g or nou_g < millor_g[vei]:
millor_g[vei] = nou_g
pares[vei] = node
f_vei = nou_g + heuristica(vei, objectiu)
heapq.heappush(frontera, (f_vei, nou_g, vei))
if traca:
print(f"| {len(explorats)} | {node} (g={g}, f={f:.2f}) | "
f"{', '.join(f'{n} (g={gg}, f={ff:.2f})' for ff, gg, n in sorted(frontera))} |")
return None, math.inf, explorats
cami, g, explorats = a_estrella(GRAF_CIUTAT, "Almacen_Getafe", "Retiro", traca=True)
print("Cami:", " -> ".join(cami), "| km:", g, "| explorats:", len(explorats))| Pas | Node expandit (g, f) | Frontera ordenada per f |
|---|---|---|
| 1 | Almacen_Getafe (0.0, 12.65) | Villaverde (g=5.0, f=14.06), Leganes (g=4.5, f=15.90) |
| 2 | Villaverde (5.0, 14.06) | Usera (g=9.5, f=14.89), Leganes (g=4.5, f=15.90), Vallecas (g=12.5, f=17.50) |
| 3 | Usera (9.5, 14.89) | Leganes (f=15.90), Arganzuela (g=13.0, f=16.61), Vallecas (f=17.50), Carabanchel (g=14.0, f=21.81) |
| 4 | Leganes (4.5, 15.90) | Arganzuela (f=16.61), Carabanchel (g=9.0, f=16.81), Vallecas (f=17.50), Carabanchel (g=14.0, f=21.81) |
| 5 | Arganzuela (13.0, 16.61) | Carabanchel (f=16.81), Retiro (g=17.0, f=17.00), Vallecas (f=17.50), Carabanchel (obsolet) |
| 6 | Carabanchel (9.0, 16.81) | Retiro (g=17.0, f=17.00), Vallecas (f=17.50), Carabanchel (obsolet) |
| 7 | Retiro (17.0, 17.00) | (objectiu assolit) |
A* retorna l'òptim (17,0 km), com cost uniforme, però orientat per l'heurística: surt directament cap a Villaverde (f = 14,06 < 15,90 de Leganés), segueix per Usera i Arganzuela, i només quan aquestes opcions tenen f més gran que Leganés torna enrere a comprovar-lo. Vallecas, la trampa de la voraç, té f = 17,50 i mai no arriba a expandir-se. En un graf tan petit l'estalvi és modest (7 nodes davant de 8), però en un mapa real de milers de cruïlles la diferència entre cost uniforme i A* és d'ordres de magnitud: A* explora una "el·lipse" al voltant de la línia recta entre origen i destinació, mentre que cost uniforme explora un cercle complet al voltant de l'origen.
Propietats: A* és complet i òptim si h és admissible (en cerca en arbre) o consistent (en cerca en graf, com la nostra). La seva complexitat continua sent exponencial en el pitjor cas, però es redueix dràsticament com millor sigui l'heurística; i el seu punt feble és la memòria, perquè desa tota la frontera igual que BFS.
- Taula comparativa i quan fer servir cadascun
Resultats sobre GRAF_CIUTAT per a tres destinacions diferents (quilòmetres del camí retornat / nodes explorats):
| Destinació | BFS | DFS | Cost uniforme | Voraç | A* |
|---|---|---|---|---|---|
| Retiro | 18,5 / 8 | 25,0 / 6 | 17,0 / 8 | 18,5 / 4 | 17,0 / 7 |
| Vallecas | 12,5 / 6 | 19,0 / 5 | 12,5 / 6 | 12,5 / 3 | 12,5 / 3 |
| Arganzuela | 14,0 / 7 | 14,0 / 7 | 13,0 / 7 | 13,0 / 4 | 13,0 / 5 |
I el resum teòric (b = factor de ramificació, d = profunditat de la solució, m = profunditat màxima):
| Algorisme | Frontera | Complet | Òptim | Temps | Memòria | Quan fer-lo servir |
|---|---|---|---|---|---|---|
| Amplada (BFS) | Cua FIFO | Sí | Només si tots els costos són iguals | O(bᵈ) | O(bᵈ) | Menor nombre de passos (p. ex. menys transbordaments, menys escales), grafs petits |
| Profunditat (DFS) | Pila LIFO | No en general (sí en grafs finits amb control de repetits) | No | O(bᵐ) | O(b·m) | Quan qualsevol solució val i la memòria és escassa; base de la recursió de minimax |
| Cost uniforme (Dijkstra) | Cua de prioritat per g | Sí (costos > 0) | Sí | O(b^(1+C*/ε)) ≈ exponencial | Igual | Camí de cost mínim sense heurística disponible; camins mínims a totes les destinacions |
| Voraç | Cua de prioritat per h | No en general | No | O(bᵐ) pitjor cas, molt ràpid a la pràctica | O(bᵐ) | Resposta rapidíssima quan l'optimalitat no importa |
| A* | Cua de prioritat per g + h | Sí | Sí, amb h admissible/consistent | Exponencial en el pitjor cas, molt inferior amb bona h | O(bᵈ) | Camí òptim amb heurística disponible: l'estàndard en navegació i planificació |
Regla pràctica de la Marta per al planificador de NovaMarket: A* amb distància en línia recta per calcular el millor camí entre dos punts; cost uniforme (Dijkstra) quan es necessiten les distàncies des d'un punt a tots els altres (que és just el que necessitarem a 03-04 per construir la matriu de distàncies entre parades); BFS només per a preguntes de "quants salts"; DFS i voraç com a peces auxiliars.
Errors Comuns i Consells
- Comprovar l'objectiu en generar en lloc d'en extreure en cost uniforme i A*: retorna el primer camí que toca la meta, no el millor (aquí hauria donat 18,5 km en lloc de 17,0). En BFS sí que és correcte comprovar en generar, perquè tots els camins de la mateixa profunditat costen el mateix.
- Fer servir
list.pop(0)per a la cua de BFS: és O(n) per extracció;deque.popleft()és O(1). - Oblidar el control de repetits: sense
pares(o un conjunt de visitats), DFS i voraç poden ciclar indefinidament entre dos barris connectats. - No permetre reassignar el pare en cost uniforme/A*: si tractes
parescom a BFS (només s'assigna la primera vegada), perds la millora Carabanchel→Usera per a Arganzuela i deixes de ser òptim. La condició correcta ésnou_g < millor_g[vei]. - Posar al monticle tuples que no es poden comparar: si dues entrades empaten en
fi eng, Python compara el tercer element; amb cadenes funciona, amb objectes sense ordre definit dona error. Afegeix un comptador com a desempat si els teus nodes no són comparables. - Heurística en unitats diferents del cost: si el cost és en minuts i h en quilòmetres, A* deixa de tenir garanties. Converteix h a la mateixa unitat (per exemple, km / velocitat màxima → minuts), cosa que a més la manté admissible.
- Confondre "explora menys nodes" amb "millor": DFS i voraç exploren menys i retornen camins pitjors. Tria segons el que necessitis garantir (optimalitat, memòria, temps de resposta), no pel comptador de nodes.
Exercicis
Exercici 1: seguir una traça a mà
Sense executar codi, construeix la taula de traça d'A* des d'Almacen_Getafe fins a Carabanchel (fes servir la taula de coordenades per calcular h amb math.hypot o a mà). Quants nodes expandeix i quin camí retorna? Compara-ho amb el que expandiria cost uniforme per a la mateixa destinació. Després verifica la teva taula amb a_estrella(..., traca=True).
Exercici 2: una heurística que sobreestima
Suposa que algú introdueix malament les coordenades d'Arganzuela a COORDENADES i hi posa (10, 16) en lloc de (1, 10). Calcula la nova h(Arganzuela, Retiro), comprova si continua sent admissible (compara-la amb el cost real Arganzuela → Retiro, que és 4,0 km) i executa a_estrella cap a Retiro. Quin camí retorna i per què? Restaura les coordenades en acabar.
Exercici 3: BFS davant de cost uniforme a totes les destinacions
Escriu un bucle que, per a cada node del graf com a destinació, executi bfs i cost_uniforme des d'Almacen_Getafe i imprimeixi el nombre de trams i els quilòmetres de cada camí. En quines destinacions discrepen i per què precisament en aquestes?
Solucions
Solució 1. h cap a Carabanchel (−2, 7): Getafe 7,28; Leganés 4,12; Villaverde 6,40; Carabanchel 0.
| Pas | Node expandit (g, f) | Frontera ordenada per f |
|---|---|---|
| 1 | Almacen_Getafe (0.0, 7.28) | Leganes (g=4.5, f=8.62), Villaverde (g=5.0, f=11.40) |
| 2 | Leganes (4.5, 8.62) | Carabanchel (g=9.0, f=9.00), Villaverde (g=5.0, f=11.40) |
| 3 | Carabanchel (9.0, 9.00) | objectiu assolit |
A* expandeix només 3 nodes i retorna Almacen_Getafe -> Leganes -> Carabanchel (9,0 km). Cost uniforme arriba al mateix camí, però n'expandeix 4 (Getafe, Leganés, Villaverde i Carabanchel), perquè Villaverde amb g = 5,0 surt del monticle abans que Carabanchel amb g = 9,0: sense heurística no té manera de saber que Villaverde queda en direcció contrària.
Solució 2. Amb (10, 16), h(Arganzuela, Retiro) = √(6² + 4²) = 7,21 km, més gran que el cost real de 4,0 km: l'heurística ja no és admissible. En executar A* cap a Retiro, Arganzuela passa a tenir f = 13,0 + 7,21 = 20,21, més gran que la f de Retiro via Vallecas (12,5 + 6,0 + 0 = 18,50), així que A* extreu Retiro per Vallecas abans d'expandir Arganzuela i retorna Almacen_Getafe -> Villaverde -> Vallecas -> Retiro amb 18,5 km: ha perdut l'optimalitat (17,0 km) per culpa d'una sobreestimació. És la demostració pràctica de la secció 8: l'admissibilitat no és un tecnicisme, sinó la condició que fa fiable A*.
COORDENADES["Arganzuela"] = (10, 16)
print(round(heuristica("Arganzuela", "Retiro"), 2)) # 7.21
print(a_estrella(GRAF_CIUTAT, "Almacen_Getafe", "Retiro")[:2])
# (['Almacen_Getafe', 'Villaverde', 'Vallecas', 'Retiro'], 18.5)
COORDENADES["Arganzuela"] = (1, 10) # restaurarSolució 3.
for desti in GRAF_CIUTAT:
c_bfs, _ = bfs(GRAF_CIUTAT, "Almacen_Getafe", desti)
c_ucs, km_ucs, _ = cost_uniforme(GRAF_CIUTAT, "Almacen_Getafe", desti)
marca = " <- discrepen" if c_bfs != c_ucs else ""
print(f"{desti:15s} BFS: {len(c_bfs)-1} trams, {cost_cami(GRAF_CIUTAT, c_bfs)} km | "
f"UCS: {len(c_ucs)-1} trams, {km_ucs} km{marca}")Discrepen a Arganzuela (BFS: 3 trams per Leganés–Carabanchel, 14,0 km; UCS: 3 trams per Villaverde–Usera, 13,0 km) i a Retiro (BFS: 3 trams, 18,5 km; UCS: 4 trams, 17,0 km). A Arganzuela tots dos fan servir 3 trams, però BFS es queda amb el primer que descobreix (per ordre d'expansió, el de Carabanchel) sense mirar quilòmetres; a Retiro, el camí de menys trams no és el de menys quilòmetres. A la resta de destinacions el camí de menys trams coincideix amb el de menys quilòmetres, i per això tots dos algorismes concorden; però és una coincidència del mapa, no una garantia.
Conclusió
Hem convertit la formulació de problemes en algorismes que funcionen. Tots comparteixen el mateix esquelet (frontera, explorats, pares, bucle d'extreure-comprovar-expandir) i es diferencien únicament en quin node surt primer de la frontera: el més antic (amplada, amb deque), el més recent (profunditat, amb una pila), el de menor cost acumulat g (cost uniforme, amb heapq), el de menor estimació h (voraç) o el de menor g + h (A*). Hem vist amb traces sobre GRAF_CIUTAT que BFS minimitza trams i no quilòmetres, que DFS estalvia memòria però retorna camins dolents, que cost uniforme és òptim però explora en totes direccions, que la voraç és ràpida però cau en trampes, i que A* amb una heurística admissible i consistent (la distància en línia recta calculada a partir de COORDENADES) obté l'òptim explorant menys. També hem après a avaluar qualsevol algorisme de cerca per la seva completesa, optimalitat i complexitat temporal i espacial.
Fins ara la furgoneta cercava el seu camí en un món que no reacciona: el mapa no canvia perquè ella es mogui. A la lliçó següent, Cerca amb Adversari: Jocs i Minimax, introduirem un segon agent amb objectius oposats, que respon a cada decisió nostra amb la seva. Veurem com es representa aquesta situació com un arbre de joc, com l'algorisme minimax tria la millor jugada suposant que el rival també juga tan bé com pot, i com la poda alfa-beta permet fer-ho explorant una fracció de l'arbre; ho provarem amb el tres en ratlla i ho portarem a una situació de NovaMarket amb competidor.
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
- Conceptes Fonamentals: Agents, Entorns i Racionalitat
- Tipus d'Intel·ligència Artificial
- Les Dades com a Matèria Primera de la IA
- Ètica i Consideracions en IA
Mòdul 3: Algorismes en IA
- Introducció als Algorismes
- Algorismes de Cerca
- Cerca amb Adversari: Jocs i Minimax
- Algorismes d'Optimització
Mòdul 4: Aprenentatge Automàtic (Machine Learning)
- Conceptes Bàsics de Machine Learning
- Tipus d'Aprenentatge Automàtic
- Preparació de Dades i Característiques
- Algorismes de Machine Learning
- Avaluació i Validació de Models
- Sobreajust, Regularització i Ajust d'Hiperparàmetres
Mòdul 5: Xarxes Neuronals i Deep Learning
- Introducció a les Xarxes Neuronals
- Arquitectura de Xarxes Neuronals
- Com Aprèn una Xarxa: Descens del Gradient i Retropropagació
- Deep Learning i les seves Aplicacions
- Transformers, Grans Models de Llenguatge i IA Generativa
Mòdul 6: Lògica i Sistemes Experts
- Lògica en IA
- Sistemes Experts
- Raonament amb Incertesa: Probabilitat i Xarxes Bayesianes
- Aplicacions dels Sistemes Experts
Mòdul 7: Eines i Llenguatges de Programació en IA
- Llenguatges de Programació per a IA
- Python Científic: NumPy, pandas i Matplotlib
- Eines i Llibreries Populars
- Entorns de Desenvolupament
Mòdul 8: Projectes i Casos d'Estudi
Mòdul 9: Exercicis i Pràctiques
- Exercicis d'Algorismes
- Pràctiques de Machine Learning
- Projectes de Xarxes Neuronals
- Projecte Integrador: de la Idea al Prototip