(Deadline: -)
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:
- Arborele de parcurgere nu este construit nivel de nivel, ci în funcție de costul minim al frunzelor. Totuși, dacă toate muchiile au ponderi egale, arborele se va construi în aceeași ordine ca și in cazul breadthfirst (deci pe nivele)
- Algoritmul ofera drumul de cost minim, care nu este neapărat și cel mai scurt drum (cu cele mai puține muchii).
- Algoritmul cauta solutia pe mai multe drumuri in paralel (asta nu inseamna neaparat programare paralela in sensul strict al cuvantului, ci doar faptul ca tine evidenta parcurgerii tuturor drumurilor pana la un nivelul curent in arbore).
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
- Initializari. Trebuie sa stabilim un nod de start si unul sau mai multe noduri scop. In plus consideram o lista de noduri(sau drumuri, adica liste de noduri) neexpandate inca, organizata sub forma de coada ordonată (o vom nota cu c). Coada va fi ordonată după costul drumului (ca o coadă de priorități). Pentru fiecare nod vom memora un nod parinte (pentru a putea reconstrui drumul) Punem nodul de start in coada si setam nodul parinte la null (deoarece nodul de start e radacina arborelui de parcurgere).
- Repetam urmatorii pasi atata timp cat coada nu e vida, sau nu ne-am oprit din cautat drumuri (am calculat deja suficiente drumuri-solutie):
- Extragem primul nod din coada ordonata crescător după cost. In cazul in care memoram chiar drumuri, extragem drumul.
- Verificam daca e nod scop. Daca da, ne oprim. (in cazul in care ne intereseaza drumul in sine, afisam drumul)
- Expandam nodul extras (sau ultimul nod din drumul extras) obtinand nodurile lui vecine
- Daca nodurile nu au mai fost vizitate, le adaugam in coada c astfel încât coada să rămână ordonată după cost. Pentru a marca nodurile vizitate, avem doua cazuri. Daca ne intereseaza doar prima solutie, putem pur si simplu sa marcam nodul in sine ca fiind vizitat. Daca vrem sa calculam mai multe solutii, verificam pentru fiecare nod din drumul curent (de la radacina pana la nodul tocmai expandat) daca mai apare in drum, caz in care nu il adaugam in coada).
Aveti aici codul python pentru UCS (o singura solutie)