Iteratív mélyítés A* algoritmus
Az iteratív mélyítésű A* (IDA*) algoritmusa egy gráfbejáró útkereső algoritmus, amely egy kijelölt kezdőpont és a célpontok halmazának bármely eleme között megtalálja a legrövidebb utat. Az iteratív, mélységi keresés egy változata, alapötlete, hogy egy heurisztikus függvényt használ annak a kiértékelésére, hogy mennyi a fennmaradó költsége a cél elérésének az A* kereső algoritmusban. Mivel egy mélységi kereső algoritmus, a memóriaigénye kevesebb, mint az A algoritmusé, de ellentétben a szokásos iteratív mélyítéssel, a legígéretesebb csomó megtalálására fókuszál, éppen ezért nem megy mindenhol ugyanabba a mélységbe a keresőfában. Az A* -gal ellentétben az IDA* nem használ dinamikus programozást, így gyakran ugyanazokat a csomópontokat járja be újra és újra.
Míg a standard iteratív mélységi kereső a keresési mélységet használja minden egyes iterációhoz, az IDA* a sokkal egyértelműbb képletet alkalmazza, ahol a gyökértől az n. csomópontig való eljutás költsége, egy problémaspecifikus heurisztikus becslése n-től a célig való eljutás költségének.
Az algoritmust először Richard Korf írta le 1985-ben.[1]
Leírás szerkesztés
Az iteratív A* algoritmus a következőképpen működik. Minden egyes iterációnál végrehajt egy mélységi keresést a fán, és levág egy ágat, aminek a teljes költsége meghalad egy adott küszöböt. Ez a küszöb a költség becsült értéke kezdeti állapotban, és minden egyes iterációval emelkedik. Minden iterációnál a következő iterációhoz használt küszöbérték az összes érték minimális költsége, amely meghaladta az aktuális küszöböt.[2]
Akárcsak az A*-nál, a heurisztikának bizonyos tulajdonságokkal kell rendelkeznie az optimálisság garantálása érdekében (legrövidebb utak). Lásd később a tulajdonságoknál.
path aktuális keresési útvonal (úgy viselkedik, mint egy verem) node aktuális csomópont (az utolsó csomópont az aktuális útvonalon) g az aktuális csomópont elérésének költsége f a legolcsóbb út becsült költsége (gyökér..csomópont .. cél) h ( node ) a legolcsóbb útvonal becsült költsége ( csomópont .. cél) cost ( node, succ ) lépés költségfüggvény is_goal (node) cél teszt successors (node ) bővítő függvény, kibővített csomópontok g + h szerint (csomópont) ida_star ( root ) vagy NOT_FOUND-ot, vagy a legjobb elérési utat és annak költségét adja vissza eljárás ida_star ( root ) bound : = h ( root ) path : = [ root ] ciklus t : = keresés ( path, 0, bound ) ha t = FOUND, then return (path, bound) ha t = ∞, then return NOT_FOUND bound : = t ciklus vége eljárás vége függvény keresés ( path, g, bound ) node : = path.last f : = g + h ( node ) ha f > bound, then return f ha is_goal ( node ), then return FOUND min : = ∞ for succ in successors (node) do ha succ not in path, then path.push(succ) t : = keresés ( path, g + cost( node, succ ), bound ) ha t = FOUND, then return FOUND ha t < min, then min : = t path.pop() ha vége for vége return min függvény vége
Tulajdonságok szerkesztés
Akárcsak A*, IDA* is garantáltan megtalálja a legrövidebb utat egy adott kezdeti csomóponttól bármely célig az adott gráfban, ha a heurisztikus függvény megengedő,[2] azaz
bármely n csomópontra, ahol h* az n től induló legrövidebb út elérésének tényleges költsége a legközelebbi célhoz (a "tökéletes heurisztika").[3]
Az IDA* akkor hasznos, ha a probléma memóriakapacitása korlátozott. Az A* keresés eltárolja számos fel nem fedett csomópont sorozatát, ami így gyorsan telíti a memóriát. Ezzel szemben, mivel az IDA* csak az aktuális úton lévő csomópontokat tárolja el, a memóriaigénye az általa gyártott megoldás hosszával egyenesen arányos. Időbeli összetettségét Korf és munkatársai úgy vizsgálták, hogy feltételezték, hogy a h heurisztikus költség értékének becslése konzisztens, azaz
bármely n csomóra és annak n’ szomszédjára. Azt a következtetést vonták le, hogy összehasonlítva egy brute-force fabejáró algoritmussal egy exponenciális méretű feladaton, IDA kisebb keresési mélységbe megy (egy konstans tényezővel kisebb), de az elágazási tényező nem változik.[4]
A rekurzív legjobbat-először keresés egy másik memóriaigényes fajtája az A* nak, ami a gyakorlatban gyorsabb az IDA* algoritmusnál, mivel kevesebb csomópontot kell újragenerálnia.[3]
Alkalmazások szerkesztés
Az IDA* elsősorban olyan problémákra alkalmazható jól, mint a tervezés.[5]
Jegyzetek szerkesztés
- ↑ Korf (1985). „Depth-first Iterative-Deepening: An Optimal Admissible Tree Search”. Artificial Intelligence 27, 97–109. o. DOI:10.1016/0004-3702(85)90084-0.
- ↑ a b Korf (1985). „Depth-first iterative deepening” (english nyelven), 7. o.
- ↑ a b Bratko, Ivan. Prolog Programming for Artificial Intelligence. Pearson Education, 282–289. o. (2001)
- ↑ Korf (2001). „Time complexity of iterative-deepening-A∗”. Artificial Intelligence 129 (1–2), 199–218. o. DOI:10.1016/S0004-3702(01)00094-7.
- ↑ Bonet (2001). „Planning as heuristic search”. Artificial Intelligence 129 (1–2), 5–33. o. DOI:10.1016/S0004-3702(01)00108-4.
Fordítás szerkesztés
Ez a szócikk részben vagy egészben az Iterative deepening A* című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.