Iteratív mélyítés A* algoritmus forrásának megtekintése

Az '''iteratív mélyítésű A*''' ('''IDA*''') algoritmusa egy [[gráf]]bejá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 <math>f(n) = g(n) + h(n)</math> képletet alkalmazza, ahol <math>g(n)</math> a gyökértől az n. csomópontig való eljutás költsége, <math>h(n)</math> 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.<ref>{{Cite journal|author=Korf|first=Richard E.|title=Depth-first Iterative-Deepening: An Optimal Admissible Tree Search|journal=[[Artificial Intelligence (journal)|Artificial Intelligence]]|year=1985|volume=27|pages=97–109|doi=10.1016/0004-3702(85)90084-0|url=http://www.cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf}}</ref>
== 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 <math>f(n) = g(n) + h(n)</math> 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.<ref name="re1985_7">{{Cite journal|author=Korf|first=Richard E.|year=1985|title=Depth-first iterative deepening|url=https://cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf|language=English|pages=7}}</ref>
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.
  <span style="color:Green;">path</span> ''aktuális keresési útvonal (úgy viselkedik, mint egy verem)''
  <span style="color:Green;">node</span> ''aktuális csomópont'' ''(az utolsó csomópont az aktuális útvonalon)''
  <span style="color:Green;">g</span> ''az aktuális csomópont elérésének költsége''
  <span style="color:Green;">f</span> ''a legolcsóbb út becsült költsége (gyökér..csomópont .. cél)''
  <span style="color:OrangeRed;">'''h'''</span> ( <span style="color:Green;">node</span> ) ''a legolcsóbb útvonal becsült költsége'' ( <span style="color:Green;">csomópont</span> ''.. cél)''
  <span style="color:OrangeRed;">'''cost'''</span> ( <span style="color:Green;">node</span>, <span style="color:Green;">succ</span> ) ''lépés költségfüggvény''
  <span style="color:OrangeRed;">'''is_goal'''</span> <span style="color:Green;">(node)</span> ''cél teszt''
  <span style="color:OrangeRed;">'''successors'''</span> (node ) ''bővítő függvény, kibővített csomópontok g + h szerint (csomópont)''
   <span style="color:OrangeRed;">'''ida_star'''</span> ( <span style="color:Green;">root</span> ) ''vagy NOT_FOUND-ot, vagy a legjobb elérési utat és annak költségét adja vissza''
  '''eljárás''' <span style="color:OrangeRed;">'''ida_star'''</span> ( <span style="color:Green;">root</span> )
   <span style="color:Green;">bound</span>   : = <span style="color:OrangeRed;">'''h'''</span> ( <span style="color:Green;">root</span> )
   <span style="color:Green;">path</span>   : = [ <span style="color:Green;">root</span> ]
   '''ciklus'''
    <span style="color:Green;">t</span>   : = <span style="color:OrangeRed;">'''keresés'''</span> ( <span style="color:Green;">path</span>, 0, bound )
    '''ha''' <span style="color:Green;">t</span> = FOUND, '''then return''' <span style="color:Green;">(path, bound)</span>
    '''ha''' <span style="color:Green;">t</span> = ∞, '''then return''' NOT_FOUND
    <span style="color:Green;">bound</span>   : = <span style="color:Green;">t</span>
    '''ciklus vége'''
  '''eljárás vége'''
  '''függvény''' <span style="color:OrangeRed;">'''keresés'''</span> ( <span style="color:Green;">path</span>, <span style="color:Green;">g</span>, <span style="color:Green;">bound</span> )
   node   : = <span style="color:Green;">path.</span>last
   <span style="color:Green;">f</span>   : = <span style="color:Green;">g</span> + <span style="color:OrangeRed;">'''h'''</span> ( <span style="color:Green;">node</span> )
   '''ha''' <span style="color:Green;">f</span> > <span style="color:Green;">bound,</span> '''then return''' <span style="color:Green;">f</span>
   '''ha''' <span style="color:OrangeRed;">'''is_goal'''</span> ( <span style="color:Green;">node</span> ), '''then return''' FOUND
   <span style="color:Green;">min</span>   : = ∞
   '''for''' <span style="color:Green;">succ</span> '''in''' <span style="color:OrangeRed;">'''successors'''</span> <span style="color:Green;">(node)</span> '''do'''
    '''ha''' <span style="color:Green;">succ</span> '''not in''' <span style="color:Green;">path,</span> '''then'''
     <span style="color:Green;">path</span>.push(<span style="color:Green;">succ</span>)
     <span style="color:Green;">t</span>   : = <span style="color:OrangeRed;">'''keresés'''</span> ( <span style="color:Green;">path</span>, <span style="color:Green;">g</span> + <span style="color:OrangeRed;">'''cost'''</span>( <span style="color:Green;">node</span>, <span style="color:Green;">succ</span> ), <span style="color:Green;">bound</span> )
     '''ha''' <span style="color:Green;">t</span> = FOUND, '''then return''' FOUND
     '''ha''' <span style="color:Green;">t</span> < <span style="color:Green;">min,</span> '''then''' <span style="color:Green;">min</span>   : = <span style="color:Green;">t</span>
     <span style="color:Green;">path</span>.pop()
    ha vége
   '''for vége'''
   '''return''' <span style="color:Green;">min</span>
  '''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ő,<ref name="re1985_7">{{Cite journal|author=Korf|first=Richard E.|year=1985|title=Depth-first iterative deepening|url=https://cse.sc.edu/~mgv/csce580f09/gradPres/korf_IDAStar_1985.pdf|language=English|pages=7}}</ref> azaz
: <math>h(n) \le h^*(n)</math>
bármely {{Mvar|n}} csomópontra, ahol {{Math|''h''*}} az {{Mvar|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]]").<ref name="ppai">{{Hivatkozás/Könyv |last=Bratko |first=Ivan |authorlink=Ivan Bratko (computer scientist) |title=Prolog Programming for Artificial Intelligence |year=2001 |publisher=Pearson Education|page=282–289}}</ref>
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 [[útgráf|út]]on 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 {{Mvar|h}} heurisztikus költség értékének becslése ''konzisztens'', azaz
: <math>h(n) \le \mathrm{cost}(n, n') + h(n')</math>
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.<ref>{{Cite journal|doi=10.1016/S0004-3702(01)00094-7|title=Time complexity of iterative-deepening-A∗|journal=Artificial Intelligence|volume=129|issue=1–2|pages=199–218|year=2001|author=Korf|first=Richard E.}}</ref>
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.<ref name="ppai"/>
== Alkalmazások ==
Az IDA* elsősorban olyan problémákra alkalmazható jól, mint a tervezés.<ref>{{Cite journal|doi=10.1016/S0004-3702(01)00108-4|title=Planning as heuristic search|journal=Artificial Intelligence|volume=129|issue=1–2|pages=5–33|year=2001|author=Bonet|first=Blai}}</ref>
== Jegyzetek ==
{{jegyzetek}}
== Fordítás ==
{{fordítás|en|Iterative deepening A*|oldid=950946617}}
[[Kategória:Gráfalgoritmusok]]
[[Kategória:Keresőalgoritmusok]]