(Deadline: -)
Daca nu sunteti logati exercitiile nu se mai afiseaza.
Tehnici de cautare informata: A*
Algoritmul A* se foloseste pentru a gasi un drum de cost minim de la un nod-start la un nod-scop intr-un graf cu muchii/arce ponderate (cu costuri).
Datele de intrare:
- graful(nodurile, muchiile/arcele impreuna cu costurile lor)
- nodul din care incepe cautarea (nodul-start)
- Un scop dat sub forma unei conditii pe care trebuie sa o indeplineasca nodul cautat (se poate oferi chiar nodul propriu-zis, conditia fiind relatia de egalitate cu acest nod). Vom numi mai departe nodul care indeplineste c
- O estimare (euristica) a costului de la fiecare nod din graf la nodul(nodurile) scop.
Notatii:
- f - costul unui drum
- f̂ - costul estimat al unui drum
- g(nod_c) - costul de la nodul start la un nod curent, nod_c, din drum
- h(nod_c) - costul de la nodul curent la nodul scop pe un anumit drum
- ĥ(nod_c) - costul estimat de la nodul curent la nodul scop
Pentru un drum dat D, avem formula: fD=gD(nod_c)+hD(nod_c), unde nod_c e un nod din drumul D
Deoarece pe parcursul construirii arborelui de parcurgere nu cunoastem costul adevarat de la nodul curent la nodul scop (graful fiind descoperit pe masura ce e parcurs), ne vom folosi in algoritm de formula costului estimat: f̂D=gD(nod_c)+ĥD(nod_c).
Spunem ca euristica este admisibila daca indeplineste conditia: ĥ(nod)≤h(nod)
Regula de consistenta:
Avand un arc n1->n2, euristica calculata in nodul n1 trebuie sa fie mai mica sau egala cu costul arcului n1->n2 adunat la euristica nodului n2
ĥ(n1)≤ cost(n1->n2)+ĥ(n2)
Consideram ca avem graful cu muchii ponderate, de mai jos:
Pasii algoritmului
Se considera doua liste: OPEN(cu nodurile descoperite care inca nu au fost expandate) si CLOSED (cu nodurile descoperite si expandate).
Pasii de mai jos sunt preluati din cartea Aspecte ale Cautarii si Reprezentarii Cun ostintelor in Inteligenta Artificiala (BALCAN Maria Florina, HRISTEA Florentina, Editura Universitatii din Bucuresti, 2004):
- In lista open se pune la inceput doar nodul de pornire.
- Initial lista closed e vida
- cat timp lista open nu e vida se executa repetitiv pasii urmatori:
- se extrage primul nod, n, din lista open si se pune in closed
- daca nodul n este nodul scop, oprim cautarea si afisam drumul de la nodul-start pana la n
- extindem nodul n, obtinand succesorii lui in graf. Nu se vor lua in considerare succesorii care se afla in drumul de la nodul start la n. Toti succesorii il au ca parinte pe n. Toti succesorii care nu se afla deja in open sau closed sunt inserati in lista open astfel incat fie in continuare ordonata dupa f. Daca sunt doua noduri cu acelasi f, se aseaza inainte nodul cu g-ul mai mare.
- Pentru succesorii care sunt deja in open sau closed, in cazul in care pentru drumul care trece prin n, s-a obtinut un f mai mic, li se schimba parintele la n, si lise actualizeaza f-ul, iar nodurile din open sunt repozitionate in lista astfel incat sa ramana ordonata crescator dupa f.
- Pentru nodurile din closed (care au fost deja expandate) ar trebui refacut calculul pentru nodurile succesoare lor, prin urmare, cel mai simplu este sa le readaugam in open).
Implementare
Pentru implementare putem considera niste clase ajutatoare, care ar fi adaptate la particularitatile problemei curente rezolvate cu A*.
Clasa NodParcurgere reprezinta clasa prin care se memoreaza informatiile despre nodurile din arborele de parcurgere. Poate avea urmatoarele proprietati:
- nod - referinta catre nodul corespunzator din graf
- parinte - referinta catre nodul-parinte din arbore. Pentru radacina arborelui, parintele va avea valoarea None.
- g - costul de la radacina arborelui pana la nodul curent
- f - costul estimat pentru drumul care porneste de la radacina si trece prin nodul curent
- expandat - o proprietate optionala (booleana). O putem folosi in locul listei closed
si urmatoarele metode:
- expandeaza - care va returna o lista cu toti succesorii posibili ai nodului curent
- test_scop -care testeaza daca nodul e nod scop
Clasa Nod se refera la nodurile efectiv aflate in graf si ar trebui sa aiba minim proprietatile:
- info: informatia nodului
- h- estimarea facuta pentru nod
Clasa Problema care contine datele particulare ale problemei.
Pseudocod
Initial lista open e vida
Cream primul nod din arborele de parcurgere corespunzator nodului de start np_start
Punem nodul np_start in lista open
Cat timp (open nu e vid) repetam:
extragem primul nod din open si il punem in variabila nod_curent
daca nod_curent indeplineste conditia scop
afisam drum
oprim cautarea
expandez nod_curent
pentru fiecare succesor s:
nod_nou=None
daca s nu apartine drumului lui nod_curent
daca s e in open
daca f-ul nodului din open e mai mare decat f-ul gasit pentru s
scoate nodul vechi din open
seteaza pentru s parintele, g-ul si f-ul
seteaza nod_nou=s
daca a fost expandat(closed)
seteaza pentru s parintele, g-ul si f-ul
ca sa adaug nodul in open (pentru a fi reexpandat) setez nod_nou=s
daca nod_nou contine un nod de inserat
pune nod_nou in open astfel incat open sa ramana ordonat crescator dupa f