Inteligenta Artificiala

Nu esti logat.

(Deadline: -)

Daca nu sunteti logati exercitiile nu se mai afiseaza.

Tehnici de cautare neinformata: breadthfirst

Puteti vizita wikipedia pentru a citi mai multe despre breadth-first.

Algoritmul presupune parcurgerea unui graf pornind dintr-un nod special desemnat ca initial si parcurgand graful pana ajungem la un nod scop (solutie). De exemplu: parcurgerea unui labirint (pornim dintr-o camera si incercam sa ajungem la o camera cu iesire din labirint (sau in exemplul dat, la o camera cu prajitura).

In unele situatii ne intereseaza doar sa ajungem la nodul scop fara a afisa drumul, in altele dorim sa dam ca solutie chiar drumul parcurs pana la nodul scop.

Ideea algoritmului.Algoritmul creeaza un fel de arbore de parcurgere. Ia nodul intial si spunem ca il expandeaza (adica memoreaza vecinii acestuia). Apoi ia pe rand fiecare dintre nodurile vecine astfel gasite si cauta noduri vecine si pentru ele (avand grija ca respectivele noduri sa nu mai fi fost parcurse inainte, pe acelasi drum. 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:

Sa presupunem ca avem urmatorul labirint:


Graful asociat ar fi:
[graful asociat camerei]

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).

Initial avem in coada doar drumul [a]


Avem in coada: [[a,b],[a,d],[a,e]]


Dupa extinderea tuturor drumurilor de lungime 2:






Pasii algoritmului

Puteti descarca un exemplu de implementare in Python a tehnicii breadth first.