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	$O(\|E\|)=O(b^{d})$ ${\ displaystyle O (\| E \|) = O (b ^ {d})}$ ${\ displaystyle O (\| E \|) = O (b ^ {d})}$ ^[1]
Cel mai rău caz spațial	$O(d)$ ${\ displaystyle O (d)}$ ${\ displaystyle O (d)}$
Optim	da
Costum de afaceri	da
Manual

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 $f(n)=g(n)+h(n)$ ${\ displaystyle f (n) = g (n) + h (n)}$ ${\ displaystyle f (n) = g (n) + h (n)}$ , unde este $g$ ${\ displaystyle g}$ $g$ este costul acumulat pentru a ajunge la nod $n$ ${\ displaystyle n}$ $n$ , in timp ce $h$ ${\ displaystyle h}$ $h$ este o estimare euristică a costului sosirii la soluție începând de la $n$ ${\ displaystyle n}$ $n$ .

Algoritmul începe prin setarea pragului (pragului) $T\leftarrow f(s)$ ${\ displaystyle T \ leftarrow f (s)}$ ${\ displaystyle T \ leftarrow f (s)}$ unde este $s$ ${\ displaystyle s}$ $s$ este nodul inițial și îi plasează pe copiii lui $s$ ${\ displaystyle s}$ $s$ într-o codă (numită franjură ). Apoi, extinde nodurile din marginea pentru care $f(n)=T$ ${\ displaystyle f (n) = T}$ ${\ displaystyle f (n) = T}$ până ajunge la o soluție. Dacă nu este nimeni în periferie $n$ ${\ displaystyle n}$ $n$ astfel încât $f(n)=T$ ${\ displaystyle f (n) = T}$ ${\ displaystyle f (n) = T}$ , apoi algoritmul setează $T\leftarrow \min _{n\in fringe}(g(n)+h(n))$ ${\ displaystyle T \ leftarrow \ min _ {n \ in fringe} (g (n) + h (n))}$ ${\ displaystyle T \ leftarrow \ min _ {n \ in fringe} (g (n) + h (n))}$ , 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ă $h$ ${\ displaystyle h}$ $h$ este admisibil , ^[4] sau astfel încât

h(n)\leq c(n)

{\ displaystyle h (n) \ leq c (n)}

{\ displaystyle h (n) \ leq c (n)}

pentru toate nodurile $n$ ${\ displaystyle n}$ $n$ a graficului, unde $c(n)$ ${\ displaystyle c (n)}$ $c (n)$ este costul real al atingerii soluției de la nod $n$ ${\ displaystyle n}$ $n$ .

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 $h$ ${\ displaystyle h}$ $h$ este consecvent (condiție mai puternică decât euristica admisibilă), sau astfel încât

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

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

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

pentru fiecare nod $n$ ${\ displaystyle n}$ $n$ și pentru fiecare dintre succesorii săi $n^{'}$ ${\ displaystyle n '}$ $n '$ ; 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 $b$ ${\ displaystyle b}$ $b$ este factorul de ramificare (factor de ramificare) și $d$ ${\ displaystyle d}$ $d$ 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, adâncime-prima profundizare iterativă: (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 .

Elemente conexe

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] Unde $b$ ${\ displaystyle b}$ $b$ este factorul de ramificare (factor de ramificare) și $d$ ${\ displaystyle d}$ $d$ este adâncimea soluției.

[russel-norvig_99-2] Russell & Norvig, 2009 , p. 99 .

[3] Russell și Norvig, 2009 , p. 101 .

[korf-1985_7-4] Korf, 1985 , p. 7 .

[5] Korf și colab., 2001 .

[1]

[2]

[3]

[4]

[5]