Tip:
Highlight text to annotate it
X
Vediac o neoptimálnosti prehľadávania do hĺbky,
prečo by ho niekto používal?
Odpoveď má čo dočinenia s požiadavkami na úložný priestor.
Tu som znázornil stavový priestor
pozostávajúci z veľmi veľkého, prípadne nekonečného binárneho stromu.
Ako klesáme na úroveň 1, 2, 3, až na úroveň N,
strom je stále väčší a väčší.
Teraz sa pozrime na hranicu každého z týchto vyhľadávacích algoritmov.
Pre prehľadávanie do šírky vyzerá hranica takto,
preto, keď zostúpime na úroveň N si potrebujeme pamätať
dva na N-tú krokov, pre prehľadávanie na šírku.
Pri vyhľadávaní najlacnejšieho, bude hranica je zložitejšia.
Bude približne kopírovať túto nákladovú obálku,
ale bude pozostávať z podobného počtu uzlov.
Ale v prípade prehľadávania do hĺbky, schádzajúc po strom, počnúc touto vetvou
a potom sa vrátime, ale v každom bode, bude naša hranica obsahovať len N uzlov
a nie 2 na N-tú, čo je obrovská úspora.
Samozrejme, ak zároveň zaznamenávame aj množinu preskúmaných uzlov,
úspora nebude až taká veľká.
ale bez zaznamenávania preskúmaných uzlov, má prehľadávanie do hĺbky obrovskú výhodu
pokiaľ ide o ušetrenie pamäte.
Ďalšia vlastnosť algoritmov, na ktorú sa pozrieme
je úplnosť, čo znamená, že ak niekde existuje cieľ,
nájde ho náš algoritmus?
Presuňme sa od veľmi veľkých stromov k nekonečným stromom,
a povedzme, že niekde hlboko v štruktúre stromu sa nachádza cieľ hľadania.
Otázkou je, je každý z týchto algoritmov úplný?
To znamená, je isté, že nájdu cestu k cieľu?
Zaškrtnite políčka pre algoritmy, o ktorých si myslíte, že sú v tomto zmysle úplné.