Iteratív mélyítés A* algoritmus

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 ${\displaystyle 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.^[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 

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

${\displaystyle h(n)\leq h^{*}(n)}$

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

${\displaystyle h(n)\leq \mathrm {cost} (n,n')+h(n')}$

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]

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

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.