Jaké jsou rozdíly mezi A * a chamtivým vyhledáváním typu „first-first“?

Oba algoritmy spadají do kategorie „vyhledávání podle prvního vyhledávání“ algoritmy, což jsou algoritmy, které mohou využívat jak dosud získané znalosti při zkoumání vyhledávacího prostoru, označené $ g (n) $ , a heuristická funkce označená $ h (n) $ , která odhaduje vzdálenost k uzlu cíle, pro každý uzel $ n $ ve vyhledávacím prostoru (často reprezentováno jako graf).

Každý z těchto vyhledávacích algoritmů definuje „vyhodnocovací funkci“ pro každý uzel $ n $ v grafu (nebo vyhledávacím prostoru), označený $ f (n) $ . Tato vyhodnocovací funkce se používá k určení, který uzel se při vyhledávání nejprve „rozbalí“, to znamená, který uzel se nejprve odebere z „okraje“ (nebo „hranice“, nebo „hranice“) , aby „navštívila“ své děti. Rozdíl mezi algoritmy v kategorii „nejlepší první“ je obecně v definici vyhodnocovací funkce $ f (n) $ .

V případě chamtivého BFS algoritmu je vyhodnocovací funkcí $ f (n) = h (n) $ , to znamená, že chamtivý algoritmus BFS nejprve rozšíří uzel, jehož odhadovaná vzdálenost k cíli je nejmenší. Chamtivý BFS tedy nepoužívá „minulé znalosti“, tj. $ g (n) $ . Proto jeho konotace „chamtivý“. Obecně platí, že chamtivý algoritmus BST není úplný , to znamená, že vždy existuje riziko vydat se cestou, která není přinést k cíli. V chamtivém algoritmu BFS jsou všechny uzly na hranici (nebo na okraji nebo na hranici) uchovávány v paměti a uzly, které již byly rozšířeny, nemusí být uloženy v paměti, a proto je lze zahodit. Chamtivý BFS obecně také není optimální , to znamená, že nalezená cesta nemusí být optimální. Obecně je časová složitost $ \ mathcal {O} (b ^ m) $ , kde $ b $ je (maximální) větvící faktor a $ m $ je maximální hloubka vyhledávacího stromu. Složitost prostoru je úměrná počtu uzlů na okraji a délce nalezené cesty.

V případě A * algoritmus , vyhodnocovací funkce je $ f (n) = g (n) + h (n) $ , kde $ h $ je přípustná heuristická funkce . „Hvězda“, často označovaná hvězdičkou, *, odkazuje na skutečnost, že A * používá přípustnou heuristickou funkci, což v podstatě znamená, že A * je optimální , tj. vždy najde optimální cestu mezi počátečním uzlem a uzlem cíle. A * je také kompletní (pokud ve vyhledávacím prostoru není nekonečně mnoho uzlů k prozkoumání). Časová složitost je $ \ mathcal {O} (b ^ m) $ . A * však musí při vyhledávání udržovat všechny uzly v paměti, nejen ty na okraji, protože A * v zásadě provádí „vyčerpávající vyhledávání“ (které je „informované“ v tom smyslu, že používá heuristickou funkci ).

Stručně řečeno, chamtivý BFS není úplný, není optimální, má časovou složitost $ \ mathcal {O} (b ^ m) $ a složitost prostoru, která může být polynomiální. A * je kompletní, optimální a má časovou a prostorovou složitost $ \ mathcal {O} (b ^ m) $ . Obecně tedy A * používá více paměti než chamtivý BFS. A * se stává nepraktickým, když je prostor pro vyhledávání obrovský. A * však také zaručuje, že nalezená cesta mezi počátečním uzlem a uzlem cíle je optimální a že algoritmus nakonec skončí. Greedy BFS, na druhé straně, používá méně paměti, ale neposkytuje záruky optimality a úplnosti A *. Který algoritmus je tedy „nejlepší“, záleží na kontextu, ale oba jsou „nejlepší“ – první vyhledávání.

Poznámka: V praxi nesmíte použít žádný z těchto algoritmů: můžete např. místo toho použijte IDA * .

Komentáře

• Komentáře nejsou pro rozšířená diskuse; tato konverzace byla přesunuta do chatu .

Podle knihy Umělá inteligence: Moderní přístup (3. vydání), konkrétně Stuart Russel a Peter Norvig, část 3.5.1 Greedy best-first search (str. 92)

Greedy best-first search se snaží rozšířit uzel, který je nejblíže k cíli, z toho důvodu, že pravděpodobně povede rychle k řešení. Vyhodnocuje tedy uzly pouze pomocí heuristické funkce; tj. $ f (n) = h (n) $ .

V tomto ve stejné sekci autoři uvádějí příklad, který ukazuje, že chamtivé vyhledávání typu „první“ není ani optimální, ani úplné.

V sekci 3.5.2 A * vyhledávání: Minimalizace celkových odhadovaných nákladů na řešení téže knihy (str. 93) uvádí

A * vyhledávání vyhodnocuje uzly kombinací $ g (n) $ , nákladů na dosažení uzlu a $ h (n) $ , náklady na přechod z uzlu do cíle $$ f (n) = g (n) + h (n). $$

Protože $ g (n) $ udává cenu cesty od počátečního uzlu k uzlu $ n $ a $ h (n) $ je odhadovaná cena nejlevnější cesty z $ n $ do cíle, máme $ f (n) $ = odhadovaná cena nejlevnějšího řešení prostřednictvím $ n $ .

Tedy pokud se snažíme najít nejlevnější řešení, je rozumné nejprve zkusit uzel s nejnižší hodnotou $ g (n) + h (n) $ . Ukazuje se, že tato strategie je víc než jen rozumná: za předpokladu, že heuristická funkce $ h (n) $ splňuje určité podmínky, je vyhledávání A * úplné a optimální. Algoritmus je identický s vyhledáváním s jednotnými náklady s tím rozdílem, že A * používá $ g + h $ namísto $ g $

To, co jsi řekl, není úplně špatné, ale algoritmus A * se stane optimálním a úplným, pokud je přípustná heuristická funkce h, což znamená, že tato funkce nikdy nadhodnocuje náklady na dosažení cíle. V takovém případě je algoritmus A * mnohem lepší než chamtivý vyhledávací algoritmus.

Komentáře

• drahá, můžete svou odpověď rozpracovat. omlouvám se, ale váš názor jsem nepochopil.
• @IramShah – TemmanRafk hovoří o důkazu, že A * je jak optimální, tak úplné. Ukazuje se to kvůli nerovnosti trojúhelníku, že heuristika, která odhaduje zbývající vzdálenost k cíli, není nadhodnocenou. Podrobnější vysvětlení najdete v en.wikipedia.org/wiki/Admissible_heuri statické