Tip:
Highlight text to annotate it
X
Vzhledem k neoptimálnosti prohledávání do hloubky,
proč by jej někdo používal?
Odpověď souvisí s paměťovými nároky.
Zde jsem ilustroval stavový prostor,
sestávající se z velmi rozsáhlého, nebo dokonce nekonečného binárního stromu.
Jak postupujeme do úrovní 1, 2, 3 až do úrovně n,
strom se rozšiřuje.
Nyní pro každý z těchto vyhledávacích algoritmů uvažme hranici.
Víme, že při prohledávání do šířky vypadá hranice takto,
a když se dostaneme na úroveň n, budeme potřebovat paměť
2 na n průchodů prohledávání do šířky.
Pro "cheapest first" bude hranice komplikovanější.
Vyvine se nějaký takový obrys nákladů,
ale bude mít podobný celkový počet uzlů.
Při hledání do šířky, jak postupujeme stromem dolů, začneme klesat touto větví
a pak se vrátíme zpět, ale v každém místě bude naše hranice mít jen n uzlů
spíše než 2 na n uzlů, což je při hledání do hloubky podstatná úspora.
Nyní, samozřejmě, pokud udržujeme také záznam o prozkoumané množině,
nezískáme přílišnou úsporu.
Ovšem bez prozkoumané množiny má vyhledávání do hloubky velkou výhodu
z hlediska úspory prostoru.
Další vlastnost algoritmů k uvážení
je úplnost, ve smyslu že existuje-li nějaký cíl,
najde jej tento algoritmus?
Posuňme se od velkých stromů ke stromům nekonečným,
a řekněme, že kdesi hluboko ve stromu je nějaký skrytý cíl.
Otázka je, je každý z těchto algoritmů kompletní?
To znamená, mohou zaručit nalezení cesty k cíli?
Zaškrtněte check boxy u algoritmů o kterých se domníváte, že jsou v tomto smyslu kompletní.