Vam tancar el mòdul 2 amb una promesa: deixar de descriure sistemes i començar a construir-los. Aquesta lliçó és el primer esglaó d'aquesta construcció. Abans de programar com un agent troba pel seu compte el camí cap a la seva meta (03-02), com decideix davant d'un adversari (03-03) o com optimitza quan l'espai de solucions és inabastable (03-04), necessitem parlar amb precisió de l'eina comuna a tot plegat: l'algorisme. Veurem què és exactament un algorisme i quines propietats ha de complir, les quatre formes habituals d'expressar-lo, per què la IA es pot resumir com "algorismes + dades + representació", quines estructures de dades fan servir una vegada i una altra els algorismes d'IA, i com es mesura el cost d'un algorisme amb la notació O gran. Amb aquestes eines reprendrem la formulació de problemes de 02-01 i formalitzarem com a graf el problema de rutes de NovaMarket: definirem el graf de barris que la furgoneta de Getafe recorrerà durant tot el mòdul i comprovarem, amb un programa de força bruta, per què "provar totes les rutes" deixa de ser una opció tan bon punt Diego hi afegeix unes quantes entregues més. Aquesta explosió combinatòria és la raó de ser de tot el que ve després.

1. Què és un algorisme i quines propietats ha de complir
2. Formes d'expressar un algorisme: llenguatge natural, pseudocodi, diagrama de flux, codi
3. La IA com a algorismes + dades + representació
4. Estructures de dades bàsiques en IA: llistes, cues, piles, diccionaris i grafs
5. Complexitat i notació O gran, a nivell intuïtiu
6. L'explosió combinatòria: quantes rutes pot fer la furgoneta de Getafe
7. Famílies d'algorismes en IA i on es veuen al curs
8. Del problema al graf: GRAF_CIUTAT, el mapa que farà servir tot el mòdul
9. Exemple en Python: representar el graf, recórrer veïns i enumerar rutes per força bruta

Un algorisme és una seqüència finita i precisa de passos que, a partir d'unes dades d'entrada, produeix un resultat de sortida. La paraula ve del matemàtic persa al-Khwarizmí (segle IX), però la idea és la de qualsevol recepta o instrucció ben escrita: algú (o alguna cosa) que no entén el problema pot seguir els passos i obtenir el resultat correcte. La Marta ho resumeix així a les reunions amb en Diego: "un algorisme és una recepta que un ordinador pot seguir sense preguntar res".

Perquè una seqüència de passos mereixi el nom d'algorisme ha de complir cinc propietats clàssiques:

Dues observacions importants per al que ve:

• Un algorisme és independent del llenguatge en què s'escriu. La cerca en amplada de 03-02 és el mateix algorisme en Python, en Java o explicada en una pissarra.
• Moltes "receptes" útils en IA no garanteixen el millor resultat, sinó un de bo en un temps raonable. Continuen sent algorismes (són finits, precisos, efectius), però s'anomenen heurístics o aproximats. Distingir quan es pot exigir la solució òptima i quan cal conformar-se amb una de bona és una de les lliçons centrals d'aquest mòdul.

El mateix algorisme es pot escriure amb diferents graus de formalitat. Expressarem de quatre maneres una regla senzilla del cas 6 (assignació de comandes a magatzems): decidir des de quin magatzem se serveix una comanda.

Llenguatge natural (com ho explicaria en Diego): "Si el magatzem més proper al client té el producte, surt d'allà. Si no, surt de l'altre magatzem. Si cap dels dos el té, la comanda queda pendent d'estoc".

Pseudocodi (més precís, sense sintaxi de cap llenguatge):

Diagrama de flux (visual; útil per validar la lògica amb persones no tècniques):

Codi (executable; l'única forma que l'ordinador entén):

Explicació línia a línia: stock és un diccionari de diccionaris (magatzem → producte → unitats). El mètode .get(producte, 0) retorna 0 si el producte no existeix en aquell magatzem, cosa que evita un error i tracta "no és al catàleg del magatzem" igual que "hi ha zero unitats". Les dues condicions if segueixen exactament l'ordre del pseudocodi. Fixa't que aquest algorisme compleix les cinc propietats: entrada (producte, estoc, magatzem més proper), sortida (un nom), precisió (no hi ha ambigüitat), finitud (com a molt dues comparacions) i efectivitat (cada pas és trivial).

És habitual fer servir les quatre formes en un mateix projecte: llenguatge natural per acordar la regla amb negoci, diagrama de flux per revisar-la, pseudocodi per dissenyar-la i codi per executar-la. En aquest curs emprarem sobretot pseudocodi breu, diagrames mermaid i codi Python.

A 01-02 vam adoptar la definició d'IA com a "sistemes que actuen racionalment" i a 02-01 vam descriure aquests sistemes com a agents. Des del punt de vista de l'enginyeria, tot agent d'IA es construeix amb tres ingredients:

• Algorismes: els procediments que decideixen (cercar un camí, triar una jugada, ajustar un model, encadenar regles).
• Dades: la matèria primera de 02-03, tant les que descriuen el problema (el mapa, els lliuraments, l'estoc) com les que serveixen per aprendre (històrics de comandes, ressenyes).
• Representació: la manera com traduïm el món a estructures que un algorisme pugui manipular. Un barri passa a ser un node; un carrer, una aresta amb un nombre; una comanda, una fila amb columnes; una jugada, un canvi en una llista.

Dels tres, la representació és l'ingredient que més se subestima. El mateix algorisme de cerca funciona sobre un mapa de ciutat, sobre un tauler de tres en ratlla o sobre les causes possibles d'una incidència sempre que representem cadascun d'aquests mons com a estats i transicions. Per això 02-01 insistia en la formulació del problema: triar la representació és mitja solució. La regla de la secció 2 només funciona perquè vam decidir representar l'estoc com a diccionari de diccionaris; amb una altra representació (una llista de textos lliures) el mateix algorisme seria impracticable.

Les estructures de dades són les "formes" en què desem la informació perquè els algorismes la facin servir amb eficiència. En aquest mòdul n'apareixeran una vegada i una altra cinc, totes disponibles a la biblioteca estàndard de Python.

Vegem les tres primeres en acció, amb un exemple mínim de cadascuna:

deque (cua de doble extrem) és la manera correcta de fer una cua en Python: popleft() és immediat, mentre que llista.pop(0) obliga a desplaçar tots els elements i es torna lent amb moltes comandes. La pila no necessita res d'especial: append i pop sobre una llista ja operen pel final. Guarda't mentalment aquesta parella cua/pila: a 03-02 veuràs que canviar l'una per l'altra transforma la cerca en amplada en cerca en profunditat, sense tocar res més.

Un graf és l'estructura estrella d'aquest mòdul. Es compon de nodes (també anomenats vèrtexs) i arestes que els connecten; si cada aresta porta un nombre (distància, temps, cost) parlem de graf ponderat; si les arestes es poden recórrer en tots dos sentits, és no dirigit. El mapa d'una ciutat és un graf ponderat no dirigit: barris com a nodes, trams de carretera com a arestes amb la seva longitud.

Hi ha dues representacions habituals:

En IA gairebé sempre es fa servir la llista d'adjacència, perquè els algorismes de cerca pregunten una vegada i una altra "on puc anar des d'aquí?". En Python s'escriu com un diccionari el valor del qual és una llista de tuples (vei, pes). La construirem a la secció 8.

Dos algorismes correctes poden diferir enormement en el temps que triguen. La complexitat temporal descriu com creix el temps d'execució en créixer la mida de l'entrada (n), i la notació O gran (big-O) resumeix aquest creixement quedant-se amb el terme dominant i ignorant les constants: no diu "triga 3 segons", sinó "si duplico n, el temps es duplica" (O(n)) o "es quadruplica" (O(n²)). És l'eina amb què la Marta respon a la pregunta preferida d'en Diego: "i això què passarà quan tinguem el doble de comandes?".

Tres idees per quedar-se:

• Fins a O(n log n) tot és "escalable": duplicar les dades costa poc més del doble.
• O(n²) és acceptable per a milers d'elements, incòmode per a centenars de milers i impossible per a milions.
• O(2ⁿ) i O(n!) són la frontera de l'impossible: a partir d'unes poques desenes d'elements cap ordinador del món acaba. És exactament el que passa amb les rutes de repartiment, com comprovarem tot seguit.

També existeix la complexitat espacial (quanta memòria cal); a 03-02 veurem que alguns algorismes de cerca són ràpids però devoren memòria, i d'altres a l'inrevés.

Tornem a la furgoneta que surt del magatzem de Getafe. Si ha de fer n lliuraments i tornar, quants ordres diferents pot seguir? La primera parada es tria entre n, la segona entre les n−1 restants, i així successivament: n × (n−1) × … × 1 = n! (factorial de n). La taula següent, calculada amb math.factorial, mostra quantes rutes hi ha i quant trigaria a provar-les totes un ordinador capaç d'avaluar un milió de rutes per segon:

Una furgoneta de NovaMarket fa habitualment entre 30 i 60 lliuraments per jornada. Per a 30 lliuraments, 30! és un nombre de 33 xifres: ni tan sols amb tots els ordinadors del planeta durant tota l'edat de l'univers es provarien totes les rutes. I això és un sol vehicle en una sola ciutat; NovaMarket mou ~3.000 comandes diàries.

D'aquí neixen les dues estratègies que estructuren la resta del mòdul:

• Cerca intel·ligent (03-02): no enumerar totes les solucions, sinó construir-les pas a pas des de l'estat inicial, descartant aviat el que no pot ser bo i fent servir heurístiques (estimacions informades, com la distància en línia recta) per dirigir l'exploració cap a la meta.
• Optimització aproximada (03-04): quan ni tan sols això és viable, partir d'una solució qualsevol i anar-la millorant, acceptant una ruta molt bona en segons en lloc de la ruta perfecta en segles.

En Diego ho va formular a la seva manera: "No necessito la millor ruta del món; necessito una ruta un 15 % millor que la que fan els meus conductors de memòria, i la necessito abans de les 8 del matí". Aquesta frase és, en el fons, la definició d'una heurística útil.

Els algorismes d'IA es poden agrupar en quatre grans famílies segons la pregunta a què responen. La taula serveix també de mapa de la resta del curs:

Les fronteres no són rígides: entrenar un model d'aprenentatge és, per dins, un problema d'optimització (ho veurem al final de 03-04), i molts sistemes moderns combinen les quatre famílies. Però la classificació ajuda a triar el punt de partida: quan en Diego descriu un problema, la primera pregunta de la Marta és sempre "això és cercar un camí, optimitzar una assignació, aprendre d'un històric o raonar amb regles?".

Reprenguem la formulació de 02-01 i apliquem-la al problema més simple del planificador de rutes: portar la furgoneta des del magatzem de Getafe fins a un barri concret pel camí més curt. Els cinc components queden així:

Amb aquesta formulació, l'espai d'estats és exactament un graf: cada barri és un node, cada carretera entre barris és una aresta i la seva longitud és el pes. Fixem el mapa (fictici, amb distàncies inventades però versemblants) del sud de Madrid que servirà per a tot el mòdul: el magatzem de Getafe i set barris on NovaMarket fa repartiment propi.

Vuit nodes, dotze arestes, distàncies en quilòmetres. És un graf petit a propòsit: prou ric perquè hi hagi diversos camins entre dos punts (i no sempre guanyi el que té menys trams), i prou petit perquè puguis seguir a mà les traces de 03-02. A 03-02 hi afegirem les coordenades de cada node per calcular distàncies en línia recta, i a 03-04 el farem servir com a base del problema del viatjant.

Cada clau és un node i el seu valor, la llista de tuples (vei, quilometres). Com que el graf és no dirigit, cada carretera apareix dues vegades (a la llista de cada extrem): ("Leganes", 4.5) és a Almacen_Getafe i ("Almacen_Getafe", 4.5) és a Leganes. És un petit cost de duplicació a canvi que la pregunta "on puc anar des d'aquí?" es respongui amb una sola consulta al diccionari.

Sortida:

veins és O(1): una consulta al diccionari. distancia_directa recorre la llista de veïns de a (com a molt quatre elements aquí), que és l'inconvenient de la llista d'adjacència esmentat a la secció 4; en un mapa real, amb pocs veïns per cruïlla, continua sent negligible. Observa que Usera i Retiro no estan connectats directament (None): per anar de l'un a l'altre cal passar per Arganzuela o per Vallecas, i decidir quin convé és precisament el que farà la cerca de 03-02.

Ara el problema complet del repartiment: la furgoneta surt del magatzem, visita una llista de barris (un per lliurament) i torna. L'estratègia més ingènua és la força bruta: generar tots els ordres possibles, calcular el cost de cadascun i quedar-se amb el menor. itertools.permutations genera exactament aquests n! ordres.

Per simplificar (i perquè encara no sabem calcular el camí més curt entre dos barris no veïns), en aquesta primera versió exigim que cada tram de la ruta sigui una carretera directa del graf; si dues parades consecutives no estan connectades, la ruta es declara impossible amb cost infinit. A 03-04 aixecarem aquesta restricció fent servir els camins més curts de 03-02.

Sortida:

Com funciona el codi:

• zip(ruta, ruta[1:]) aparella cada parada amb la següent; és la manera idiomàtica en Python de recórrer "trams".
• itertools.permutations(lliuraments) produeix cada ordre possible com a tupla, sense carregar-los tots a la memòria alhora (és un generador), però sí que els recorre tots: 24, 120 i 5.040 iteracions.
• La ruta es construeix concatenant tuples: (origen,) + ordre + (origen,).
• Desem el millor cost vist fins al moment i el substituïm només si n'apareix un de menor: el patró clàssic de "quedar-se amb el mínim".

El que ensenya la sortida és més important que la ruta concreta:

1. El nombre de rutes avaluades és exactament n!, independentment del que sàpiga l'algorisme sobre el problema. Amb 7 lliuraments ja són 5.040 avaluacions; amb 12 serien 479 milions.
2. Gairebé totes les rutes avaluades són impossibles (2 factibles de 120): la força bruta no sap res del graf, així que gasta el 98 % de l'esforç en combinacions que un conductor descartaria a l'instant. Els algorismes de cerca de 03-02 ho eviten construint les rutes pas a pas només a través d'arestes vàlides.
3. Les dues rutes factibles de cada cas són la mateixa en els dos sentits: la força bruta ni tan sols reconeix aquesta simetria, un exemple més de coneixement del problema que un algorisme intel·ligent pot explotar.

Prova d'afegir un import time i mesurar quant triga el cas de 7 lliuraments (en un portàtil actual, unes mil·lèsimes de segon) i calcula, amb la taula de la secció 6, quant trigaria amb 15. Aquest càlcul és la millor motivació possible per a la lliçó següent.

• Confondre "algorisme" amb "codi": el codi és una de les formes d'expressar un algorisme. Dissenya primer en pseudocodi o diagrama, i programa després; t'estalviaràs molts errors de lògica.
• Fer servir llista.pop(0) com a cua: funciona, però és O(n) en cada extracció. Fes servir collections.deque i popleft(); amb milers de nodes a la frontera d'una cerca la diferència és enorme.
• Oblidar la simetria en construir un graf no dirigit a mà: si afegeixes ("Leganes", 4.5) a Almacen_Getafe però no el recíproc, la furgoneta podrà anar a Leganés però mai tornar. Una comprovació automàtica (recórrer totes les arestes i verificar que existeix la inversa amb el mateix pes) evita hores de depuració.
• Refiar-se de la intuïció sobre la complexitat: "només són 12 lliuraments" sona poc, i són 479 milions de rutes. Calcula sempre la mida de l'espai de solucions abans de triar estratègia.
• Interpretar malament la notació O gran: O(n²) no vol dir "lent", vol dir "creix quadràticament". Per a 100 elements pot ser instantani; el problema apareix en escalar. A l'inrevés, un O(n log n) amb constants enormes pot ser més lent que un O(n²) senzill per a entrades petites.
• Triar la representació sense pensar en les operacions: abans de decidir entre llista i matriu d'adjacència (o entre llista i diccionari), pregunta't quina operació farà l'algorisme milions de vegades i optimitza aquesta.

En Diego proposa aquesta regla per triar la següent parada: "anar sempre al lliurament que tingui més pressa, i si hi ha empat, al que li sembli millor al conductor". Indica quina de les cinc propietats de la secció 1 no compleix i reescriu-la (en pseudocodi) perquè les compleixi totes.

Escriu una funció es_simetric(graf) que retorni True si per a tota aresta (a, b, d) existeix l'aresta (b, a, d). Comprova GRAF_CIUTAT; suposa després que s'obre una nova via ràpida directa entre Almacen_Getafe i Usera de 8,0 km, afegeix-la (en tots dos sentits) i torna a executar la força bruta amb els 4 lliuraments ["Leganes", "Carabanchel", "Usera", "Villaverde"]. Quantes rutes factibles hi ha ara, quines són i quina és la millor? Modifica forca_bruta (o escriu un bucle a part) per imprimir totes les rutes factibles.

Fent servir math.factorial, escriu un programa que, per a n de 5 a 20 lliuraments, imprimeixi el nombre de rutes i el temps estimat suposant 10 milions d'avaluacions per segon (un ordinador deu vegades més ràpid que el de la secció 6). A partir de quin n el temps supera una jornada laboral de 8 hores? Canvia gaire la resposta amb un ordinador deu vegades més ràpid?

Solució 1. No compleix la precisió: "el que li sembli millor al conductor" és ambigu, dos conductors farien coses diferents i un programa no ho pot executar. Una versió precisa:

El desempat final per identificador garanteix que mai queda una decisió sense definir. Fixa't que ara sí que és un algorisme, encara que no sigui necessàriament el millor (és una heurística "voraç": tria el que sembla millor ara sense mirar més enllà; tornarem sobre aquesta idea a 03-02).

Solució 2.

Sortida del bucle final:

La nova via crea dues rutes factibles més (les que surten o tornen per Usera), però la millor continua sent la de 23,0 km: una carretera nova amplia les opcions, no necessàriament millora l'òptim. Recorda desfer el canvi (o tornar a definir GRAF_CIUTAT com a la secció 9.1) abans de continuar amb les lliçons següents, que fan servir el graf original de 12 arestes.

Solució 3.

Amb 10 milions de rutes per segon, 13 lliuraments triguen uns 10 minuts, 14 lliuraments unes 2,4 hores i 15 lliuraments ja superen la jornada (1,5 dies). Un ordinador deu vegades més ràpid només desplaça la frontera un lliurament (de 14 a 15), perquè cada lliurament addicional multiplica la feina per n: la solució no és més maquinari, sinó un algorisme millor.

En aquesta lliçó hem posat els fonaments tècnics del mòdul. Hem definit l'algorisme com una seqüència finita, precisa i efectiva de passos amb entrada i sortida, i hem vist que es pot expressar en llenguatge natural, pseudocodi, diagrama de flux o codi, cada forma amb la seva utilitat. Hem resumit l'enginyeria de la IA com a algorismes + dades + representació i hem repassat les estructures de dades que apareixeran constantment (llistes, cues, piles, diccionaris i, sobretot, grafs representats amb llistes d'adjacència). Amb la notació O gran hem après a raonar sobre com escala un algorisme i hem comprovat amb nombres que el repartiment de NovaMarket pateix una explosió combinatòria (n! rutes) que fa inviable la força bruta a partir d'una dotzena de lliuraments. Finalment, hem reprès la formulació de problemes de 02-01 per convertir el mapa de la ciutat en el graf GRAF_CIUTAT, i hem escrit el codi que el representa, el recorre i enumera rutes per força bruta.

A la lliçó següent, Algorismes de Cerca, resoldrem sobre aquest mateix graf el primer problema de debò: trobar el millor camí des d'Almacen_Getafe fins a un barri de destinació sense enumerar totes les possibilitats. Veurem que canviar la cua per una pila converteix la cerca en amplada en cerca en profunditat, que una cua de prioritat ens dona el camí més curt (cost uniforme), i que una heurística tan simple com la distància en línia recta permet a A* arribar a la meta explorant una fracció del mapa.