Aprofundare iterativă A *
Aprofundare iterativă A * | |
---|---|
Clasă | Algoritm de căutare |
Structură de date | Grafic |
Cel mai rău caz din punct de vedere temporal | [1] |
Cel mai rău caz spațial | |
Optim | da |
Costum de afaceri | da |
Aprofundarea iterativă A * (cunoscută și sub acronimul IDA * ) este un algoritm euristic propus de Richard Korf în 1985. Este capabil să găsească cea mai scurtă cale între un nod inițial și fiecare membru al unui set de „noduri de soluție” într-un ponderat grafic .
Algoritmul este o variantă a căutării iterative de adâncire a adâncimii, folosită pentru a îmbunătăți performanța lui A * . [2] Principalul avantaj al IDA * este de fapt utilizarea liniară a memoriei, spre deosebire de A * care are nevoie, în cel mai rău caz, de un spațiu exponențial. Pe de altă parte, acest algoritm folosește prea puțină memorie, care ar putea fi în schimb exploatată pentru a îmbunătăți performanța în termeni de timp (a se vedea memoizarea ). [3]
Descriere
La fel ca în căutarea iterativă a adâncimii în primul rând, algoritmul se repetă de mai multe ori cu un prag din ce în ce mai mare, până când se ajunge la o soluție. Cu toate acestea, în acest caz, pragul nu va mai depinde de adâncimea față de nodul rădăcină, ci de valoarea asumată de funcția de evaluare . Ca și în A * și în alți algoritmi euristici, este folosit ca funcție de evaluare , unde este este costul acumulat pentru a ajunge la nod , in timp ce este o estimare euristică a costului sosirii la soluție începând de la .
Algoritmul începe prin setarea pragului (pragului) unde este este nodul inițial și îi plasează pe copiii lui într-o codă (numită franjură ). Apoi, extinde nodurile din marginea pentru care până ajunge la o soluție. Dacă nu este nimeni în periferie astfel încât , apoi algoritmul setează , adică actualizează pragul pe baza valorii minime asumate de funcția de evaluare dintre toate nodurile marginii . [4]
Datorită numărului de ori în care algoritmul poate extinde același nod, execuția sa rămâne exponențială în ceea ce privește timpul cel mai rău. Această problemă este parțial atenuată în alți algoritmi, cum ar fi RBFS și diferitele implementări ale MA * . [2]
Implementare
cale cale căutare curentă (acționează ca o stivă ) nod nod curent (ultimul nod al căii) g costul pentru atingerea nodului curent f cost estimat pentru a ajunge la soluție (rădăcină-> nod curent-> soluție) h ( nod ) cost estimat pentru a ajunge la soluție (nod curent-> soluție) cost ( nod , succ ) cost pentru pasul următor is_goal ( nod ) Funcție booleană care preia valoarea adevărului dacă nodul este o soluție funcția de extindere a succesorilor ( nodului ) unui nod, alege succesorii ordonându-i în funcție de g + h (n) ida_star ( rădăcină ) returnează fie NOT_FOUND, fie o pereche de valori (cale, cost) proceduri ida_star ( root ) legat : = h ( rădăcină ) cale : = [ rădăcină ] buclă t : = căutare ( cale , 0, legată ) dacă t = GĂSIT atunci revine (cale, legat) dacă t = ∞ atunci returnează NOT_FOUND legat : = t bucla de capăt încheierea procedurii căutare funcție ( cale , g , legată ) nod : = cale .ultima f : = g + h ( nod ) dacă f > legat atunci returnează f if is_goal ( nod ) atunci returnează FOUND min : = ∞ pentru succ în succesori ( nod ) do dacă succ nu în cale atunci Cale .push (succ) t : = căutare ( cale , g + cost ( nod , succ ), legat ) dacă t = Găsit, atunci reveniți GĂSIT dacă t < min atunci min : = t cale .pop () incheie daca sfârșit pentru retur min funcția finală
Proprietate
În ceea ce privește A * , IDA * garantează o soluție optimă la cea mai scurtă problemă de cale atunci când funcția euristică este admisibil , [4] sau astfel încât
pentru toate nodurile a graficului, unde este costul real al atingerii soluției de la nod .
IDA * este util mai ales atunci când funcționează pe un sistem cu memorie limitată. Căutarea A * păstrează o cantitate mare de noduri neexplorate în memorie, care se umple exponențial. Pe de altă parte, deoarece IDA * nu păstrează niciun nod în memorie, cu excepția celor din calea curentă, necesită o cantitate liniară de memorie în raport cu lungimea soluției căutate. Complexitatea sa de timp a fost analizată de Korf și colab. sub ipoteza că euristica este consecvent (condiție mai puternică decât euristica admisibilă), sau astfel încât
pentru fiecare nod și pentru fiecare dintre succesorii săi ; a concluzionat că, în comparație cu algoritmii de căutare neinformați (adică forța brută ), care găsesc o soluție în timp exponențial, IDA * reduce adâncimea de căutare a soluției (cu un factor constant), dar nu reduce ramura factorului . [5]
Notă
- ^ Unde este factorul de ramificare (factor de ramificare) și este adâncimea soluției.
- ^ a b Russell & Norvig, 2009 , p. 99 .
- ^ Russell și Norvig, 2009 , p. 101 .
- ^ a b Korf, 1985 , p. 7 .
- ^ Korf și colab., 2001 .
Bibliografie
- (EN) Richard E. Korf, O căutare optimă a arborelui admisibil, prima adâncime iterativă-aprofundare: (PDF), în Inteligență artificială , vol. 27, 1985, pp. 97-109, DOI : 10.1016 / 0004-3702 (85) 90084-0 .
- ( EN ) Richard E. Korf, Michael Reid și Stefan Edelkamp, Time complexity of iterative-deepening-A ∗ , în Artificial Intelligence , vol. 129, 1-2, 2001, pp. 199-218, DOI : 10.1016 / S0004-3702 (01) 00094-7 .
- ( EN ) Stuart Russell , Peter Norvig , 3.5 Strategii de căutare informate (euristice) , în Artificial Intelligence: A Modern Approach , ediția a 3-a, Pearson, 1 decembrie 2009, p. 99, ISBN 9780136042594 .