Mi a különbség az A * algoritmus és a kapzsi legjobb első keresési algoritmus között? Melyiket használjam? Melyik a jobb algoritmus, és miért?
Válasz
Mindkét algoritmus a “legjobb első keresés” kategóriába tartozik algoritmusok, amelyek olyan algoritmusok, amelyek fel tudják használni mind az eddig megszerzett tudást, mind a keresési helyet feltárva, $ g (n) $ jelöléssel, és egy heurisztikus függvény, amelyet $ h (n) $ jelöl, amely megbecsüli a célcsomópont távolságát minden egyes csomópontnál $ n $ a keresési térben (gyakran grafikonként ábrázolva).
Ezen keresési algoritmusok mindegyike meghatároz egy “kiértékelési függvényt” a grafikonon (vagy a keresési helyen) minden $ n $ csomópont számára, amelyet $ f (n) $ . Ezt az értékelő függvényt használják annak meghatározására, hogy melyik csomópont keresés közben legyen először “kibővítve”, vagyis melyik csomópontot távolítsák el először a “peremről” (vagy “határ” vagy “határ”) , annak érdekében, hogy “meglátogassa” gyermekeit. Általánosságban elmondható, hogy a “legjobb az első” kategóriában szereplő algoritmusok közötti különbség az $ f (n) $ értékelő függvény meghatározásában rejlik.
a kapzsi BFS algoritmus esetén az értékelő függvény $ f (n) = h (n) $ , vagyis a kapzsi BFS algoritmus először kitágítja azt a csomópontot, amelynek becsült távolsága a céltól a legkisebb. Tehát a kapzsi BFS nem használja a “múltbeli tudást”, azaz a $ g (n) $ -ot. Ezért “kapzsi” jelzése. Általában a kapzsi BST algoritmus nem teljes , vagyis mindig fennáll annak a veszélye, hogy olyan utat választunk, amely nem célhoz juttatni. A kapzsi BFS algoritmusban a határ minden csomópontja (vagy a perem vagy a határ) a memóriában marad, és a már kibővített csomópontokat nem kell a memóriában tárolni, ezért eldobhatók. Általában a kapzsi BFS is nem optimális , vagyis előfordulhat, hogy a megtalált út nem az optimális. Az idő összetettsége általában $ \ mathcal {O} (b ^ m) $ , ahol $ b $ a (maximális) elágazási tényező, a $ m $ a keresési fa maximális mélysége. A tér bonyolultsága arányos a perem csomópontjainak számával és a megtalált útvonal hosszával.
esetén az A * algoritmus , az értékelő függvény $ f (n) = g (n) + h (n) $ , ahol $ h $ egy megengedett heurisztikus funkció . A “csillag”, amelyet gyakran csillaggal jelölnek, *, arra a tényre utal, hogy A * megengedett heurisztikus függvényt használ, ami lényegében azt jelenti, hogy A * optimális , vagyis mindig megtalálja az optimális utat a kezdő csomópont és a cél csomópont között. A * szintén teljes (kivéve, ha a keresési térben végtelen sok csomópont van felfedezésre). Az idő összetettsége $ \ mathcal {O} (b ^ m) $ . Az A * -nak azonban keresés közben minden csomópontot meg kell tartania a memóriában, nem csak a peremén, mert az A * lényegében “kimerítő keresést” hajt végre (amely “tájékozott”) abban az értelemben, hogy heurisztikus funkciót használ ).
Összefoglalva: a kapzsi BFS nem teljes, nem optimális, időbeli összetettsége $ \ mathcal {O} (b ^ m) $ és egy tér bonyolultsága, amely polinom lehet. Az A * teljes, optimális, idő és tér összetettsége $ \ mathcal {O} (b ^ m) $ . Tehát általában A * több memóriát használ, mint a kapzsi BFS. Az A * nem praktikus, ha a keresési hely hatalmas. Az A * ugyanakkor garantálja, hogy a kezdő csomópont és a cél csomópont közötti megtalált út az optimális, és hogy az algoritmus végül megszűnik. A kapzsi BFS viszont kevesebb memóriát használ, de nem biztosítja az A * optimális és teljességi garanciáját. Tehát az, hogy melyik algoritmus a “legjobb”, a kontextustól függ, de mindkettő a “legjobb” első keresés.
Megjegyzés: a gyakorlatban nem használhatja ezen algoritmusok egyikét sem: pl. ehelyett IDA * .
Megjegyzések
- A megjegyzések nem kiterjesztett vita; ezt a beszélgetést csevegésbe helyezte .
Válasz
A Mesterséges intelligencia könyv szerint: Egy modern megközelítés (3. kiadás), konkrétan Stuart Russel és Peter Norvig, a 3.5.1 szakasz: Kapzsi legjobb első keresés (92. o.)
A kapzsi legjobb első keresés megpróbálja kibővíteni a célhoz legközelebb eső csomópontot, azzal az indokkal, hogy valószínűleg gyors megoldáshoz vezet. Így csak a heurisztikus függvény használatával értékeli a csomópontokat; vagyis $ f (n) = h (n) $ .
Ebben ugyanabban a részben a szerzők mutatnak be egy példát, amely azt mutatja, hogy a kapzsi legjobb első keresés nem optimális és nem is teljes.
A 3.5.2 szakaszban A * keresés: A teljes becsült megoldás költségének minimalizálása (93. o.), És a következőket állítja:
A * A keresés a csomópontokat úgy értékeli ki, hogy egyesíti a $ g (n) $ -ot, a csomópont elérésének költségét és a $ h (n) $ , a csomóponttól a célig eljutás költsége $$ f (n) = g (n) + h (n). $$
Mivel a $ g (n) $ megadja az út költségét a kezdő csomóponttól a csomópontig $ n $ , és a $ h (n) $ a $ n $ a célig, $ f (n) $ = a legolcsóbb megoldás becsült költsége a $ n $ segítségével.
Így ha a legolcsóbb megoldást próbáljuk megtalálni, akkor ésszerű dolog először kipróbálni a legkisebb értékű csomópontot: $ g (n) + h (n) $ . Kiderült, hogy ez a stratégia nem csupán ésszerű: feltéve, hogy a $ h (n) $ heurisztikus függvény megfelel bizonyos feltételeknek, az A * keresés teljes és optimális. Az algoritmus megegyezik az egységes költségű kereséssel, azzal a különbséggel, hogy A * $ g + h $ -ot használ a $ g $
Válasz
Amit mondtál, nem teljesen rossz, de az A * algoritmus akkor válik optimálisá és teljesé, ha a h heurisztikus függvény megengedett, ami azt jelenti, hogy ez a függvény soha nem becsüli túl a cél elérésének költségeit. Ebben az esetben az A * algoritmus sokkal jobb, mint a kapzsi keresési algoritmus.
Hozzászólások
- kedves tudná részletezni a válaszát. Sajnálom, de nem értettem a véleményét.
- @IramShah – TemmanRafk arról a bizonyítékról beszél, hogy A * egyszerre optimális és teljes. Ehhez a háromszög egyenlőtlenség miatt látható, hogy a heurisztika, amely becsüli a célig hátralévő távolságot, nem túlértékelt. A teljesebb magyarázat megtekintéséhez lásd: hu.wikipedia.org/wiki/Adiable_heuri stic