Inteligenta Artificiala

(Deadline: 12.12.2022 23:59:59)

Daca nu sunteti logati exercitiile nu se mai afiseaza.

Cautare neinformata pe grafuri cu muchii ponderate (uniform cost search)

Puteti vizita wikipedia pentru a citi mai multe despre uniform cost search care este de fapt o optimizare a algoritmului lui Dijkstra.

Algoritmul presupune parcurgerea unui graf cu muchii ponderate ( = cu un număr asociat fiecărei muchii) pornind dintr-un nod special desemnat ca initial si parcurgand graful pana ajungem la un nod scop (solutie). De exemplu: parcurgerea unui traseu într-un oraș, cu mașina încercând să mergem pe o distanță cât mai mică (pe cel mai scurt drum).

Ideea algoritmului.Algoritmul creeaza un arbore de parcurgere pentru fiecare nod memorând și cât am parcurs (costul drumului de la rădăcină la acel nod). Ia nodul intial si spunem ca il expandeaza (adica memoreaza vecinii acestuia). Apoi, repetitiv, ia nodul-frunză, din arborele de parcurgere, cu costul (de parcurgere de la rădăcină până la el) cel mai mic, și îl expandează, adăugând nodurile vecine lui. Totuși, nu va adăuga un nod care există deja în drumul său. De exemplu un drum de forma a->b->c->a nu ar fi ales). Inainte de expandarea oricarui nod algoritmul verifica daca nodul este un nod scop.

Observatii:

Să presupunem ca avem următorul graf:


Arborele extinderilor se va forma in felul ilustrat mai jos. Consideram cazul in care vrem sa obtinem toate drumurile (sau oricum o parte din ele), motiv pentru care permitem inclusiv extinderea drumurilor cu noduri vizitate pe alta ramura (insa nepermitand repetarea nodului pe un drum de la radacina pana la el).

Vom alege mereu ramura cu costul cel mai mic (al drumului de la radacină până la frunza acelei ramuri). Intern ne vom folosi de o coadă ordonată crescător după cost, din care vom extrage mereu primul nod (deci de cost minim).

Initial avem in coada doar "drumul partial" ["a"]. Vom nota cu g costul.


Avem in coadă: [["a","b"],["a","d"],["a","c"]], cu costurile 3, 7, respectiv 9 (drumurile sunt ordonate după cost)


Dupa extinderea tuturor drumurilor de lungime 2:



În imaginea de mai jos, vedem că obținem un drum mai bun pentru c(cost 8) decât cel existent(cost 9). Putem alege să stergem din arbore nodul cu cost mai mare, dacă ne interesează doar drumul de cost minim.





Nodul k (cel cu costul cel mai mic: 12) nu are succesori, asa că îl extindem pe g, cu costul 13.


Ar fi fost rândul nodului j cu costul 13, dar nu are succesori, așadar avem pasul opțional de extindere a lui g cu costul 14. Pasul este opțional, deoarece sigur acea ramură nu face parte din drumul de cost minim, iar extinderea se face doar în cazul în care dorim mai multe drumuri posibile, ordonate după cost.






Următorul nod de extins ar fi k cu costul 15, dar nu are succesori, apoi în coadă ar urma j cu costul 16 și k cu costul 16, dar nici ei nu au succesori. Toate aceste noduri s-au marcat cu roșu în imaginea de mai jos:


Urmează în coadă f cu costul 17 care e și nod scop, obținându-se, astfel, prima soluție.


Pasii algoritmului

Aveti aici codul python pentru UCS (o singura solutie)