| dbo:abstract
|
- 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. (hu)
- 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. (hu)
|
