Inteligenta Artificiala

Nu esti logat.

(Deadline: -)

Daca nu sunteti logati exercitiile nu se mai afiseaza.

Tehnici de cautare neinformata: depthfirst


Despre depthfirst

Algoritmul presupune parcurgerea unui graf pornind dintr-un nod special desemnat ca initial si parcurgand graful pana ajungem la un nod scop (solutie).

Ideea algoritmului.Algoritmul creeaza un fel de arbore de parcurgere. Ia nodul intial si spunem ca il expandeaza luand un prim succesor al acestuia. Apoi considera drept nod curent acest nod succesor adaugat in drum. La fiecare pas verifica daca nodul curent este nod-scop. Daca nu, ia si pentru el unul dintre succesorii neevalutai inca, si il adauga in drum. Procedeul se continua pana ori gasim o solutie, ori nu mai gasim un succesor viabil pentru nodul curent( de exemplu daca nu are el succesori, sau succesorii lui sunt toti in drum). In acel moment algoritmul se intoarce la nodul anterior nodului curent, si ia urmatorul succesor posibil (daca acesta exista; daca nu exista face intoarceri pana gaseste un nod cu succesori neprocesati).

Observatii:

Sa presupunem ca avem urmatorul labirint:


Graful asociat labirintului:
[graful asociat camerei]

Arborele extinderilor se va forma in felul urmator (numai o parte din pasi):











Pasii algoritmului

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

Observatie, in cazulimplementarii date ca exemplu, nu s-a folosit efectiv o lista ca stiva. Stiva e simulata prin inlantuirea nodurilor din drum.

Tehnici de cautare neinformata: depthfirst iterative deepening (cautarea in adancime incrementala)


Despre depth-first iterative deepening

Ideea algoritmului. Se aplica algoritmul depth first pana la o adancime fixa Ad din arbore (se realizeaza o intoarcere in stiva si in momentul in care stiva are lungimea Ad, ca si cum nodul nu ar mai fi avut succesori). Iterativ, aceasta adancime creste de la 1 la o adancime maxima. Ca si in cazul depth-first-ului simplu, cand varful stivei este nod-scop, inseamna ca am gasit o solutie.

Observatii:

Pasii algoritmului

  • Initializari. Trebuie sa stabilim un nod de start si unul sau mai multe noduri scop. Stabilim si o adancime maxima, ADMAX, pana la care cautam solutii. Consideram o stiva S initial vida. Pentru fiecare nod din parcurgerea curenta vom memora un nod parinte (pentru a putea reconstrui drumul). Punem nodul de start in stiva S si setam nodul parinte la null (None), deoarece nodul de start e radacina arborelui de parcurgere.
  • Pentru ADcurent(adancimea curenta) de la 1 la ADMAX aplicam algoritmul DF pe graf nemaiexpandand nodul din varful stivei daca stiva are deja lungimea Adcurent

Puteti descarca un exemplu de implementare in Python a tehnicii depth first iterative deepening.

Observatie, in cazulimplementarii date ca exemplu, nu s-a folosit efectiv o lista ca stiva. Stiva e simulata prin inlantuirea nodurilor din drum.