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 $f(n)=g(n)+h(n)$ képletet alkalmazza, ahol $g(n)$ a gyökértől az n. csomópontig való eljutás költsége, $h(n)$ 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.

Leírá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 $f(n)=g(n)+h(n)$ 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.

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

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ő, azaz

$h(n)\le h^{*}(n)$

bármely Sablon:Mvar csomópontra, ahol Sablon:Math az Sablon:Mvar 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").

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 Sablon:Mvar heurisztikus költség értékének becslése konzisztens, azaz

$h(n)\le \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(n,n^{\prime })+h(n^{\prime })$

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.

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.

Alkalmazások

Az IDA* elsősorban olyan problémákra alkalmazható jól, mint a tervezés.