Tip:
Highlight text to annotate it
X
Considerand non-optimalitatea algoritmului de parcurgere in adancime a grafului,
de ce acesta este totusi folosit?
Raspunsul are in vedere cerintele legate spatiul de stocare.
Aici am ilustrat un spatiu al starilor
ce consta dintr-un arbore binar foarte mare, poate chiar infinit.
Pe masura ce parcurgem nivelele 1,2,3 pana la nivelul n,
arborele devine din ce in ce mai mare.
In cele ce urmeaza, sa consideram frontiera pentru fiecare dintre acesti algoritmi de cautare.
In cazul algoritmului de parcurgere in largime, cunoastem ca o frontiera arata in felul urmator,
astfel incat, atunci cand ajungem la nivelul n, vom avea nevoie de un spatiu de stocare
de 2 la n per parcurgere in largime.
In cazul algoritmului cu cost minim, frontiera va fi mai complicata,
adica va organiza un soi de contur de cost
dar va avea un numar total de noduri similar.
Dar, in cazul algoritmului de parcurgere in adancime, pa masura ce avansam in arbore, parcurgem mai intai aceasta ramura,
apoi ne intoarcem inapoi, dar in orice punct, frontiera noastra va avea doar n noduri
in loc de 2 la n noduri. Rezulta, deci, ca algoritmul de parcurgere in adancime a grafului ofera o economie substantiala.
Acum, daca, de asemenea, tinem socoteala setului de noduri explorate,
atunci economiile vor fi mai modeste.
Insa, daca nu tinem cont de setul de noduri explorate, algoritmul de parcurgere in adancime are un avantaj major
in termeni de spatiu de stocare neocupat.
O alta proprietate a algoritmilor pe care trebuie sa o luam in considerare,
este aceea de completitudine, adica daca exista un obiectiv undeva,
algoritmul il va gasi?
Sa consideram in loc de arbori foarte mari, arbori infiniti
si sa presupunem ca exista un obiectiv ascuns, undeva, adanc in arbore.
Intrebarea este daca fiecare dintre acesti algoritmi este sau nu complet?
Cu alte cuvinte, este garantat fiecare dintre acestia ca va gasi calea catre obiectiv?
Marcati casutele corespunzatoare algoritmilor pe care ii credeti completi in acet sens.