SMA *

SMA *
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(n)$ ${\ displaystyle O (n)}$ $Pe)$ ^[2]
Optim	da ^[3]
Costum de afaceri	da ^[4]
Manual

SMA * , acronim pentru Simplified Memory-Bounded A * , este un algoritm euristic pentru căutarea celei mai scurte căi pe baza algoritmului A * , propus de informaticianul anglo-american Stuart Russell în 1992. ^[5]

Principalul avantaj al SMA * este utilizarea limitată a memoriei, spre deosebire de A * care are nevoie de spațiu exponențial în cel mai rău caz. Toate celelalte caracteristici ale SMA * derivă direct din A *, inclusiv performanța în termeni de timp, care în cel mai rău caz rămâne exponențial. ^[6] După cum sugerează și numele, acest tip de căutare face parte din familia A * (sau MA *) legată de memorie . ^[5]

Descriere

Ideea algoritmilor cu memorie mărginită apare din faptul că alți algoritmi euristici, precum RBFS sau IDA * , folosesc prea puțină memorie, ^[7] în detrimentul performanței vitezei. Prin urmare, SMA * folosește un algoritm substanțial identic cu A * până când memoria alocată acestuia este suficientă, după care stările cu cel mai mare cost f vor fi eliminate (sau „tăiate”) din coadă. ^[7] În acest moment, algoritmul va adopta o strategie RBFS, ^[7] reținând cel mai bun cost f față de fiecare ramură tăiată (în loc de costul nodului de la care începe ramura). Când toate ramurile explorate par mai rele decât cea uitată, acestea din urmă vor fi reexplorate mai în profunzime. ^[8]

Implementare

Urmează o posibilă implementare în pseudocod :

 funcția SMA_star ( problemă ) : cale
  Coada: set de noduri, clasificate după costul lor f;
începe
  coada . inserare ( problemă . nod - rădăcină ) ;

  în timp ce adevărații începe
    dacă coadă . empty () apoi returnează eșecul ; // nicio soluție nu intră în memorie
    nod : = coada . begin () ; // nodul cu cel mai mic cost f
    dacă problemă . soluție ( nod ) apoi returnează succesul ;
    
    s : = succesor ( nod )
    dacă ! problema . solution (s) && depth à (s) == maxim_profondit à then
        f ( s ) : = inf ; 
        // nu mai este spațiu disponibil în memorie
    altceva
        f ( s ) : = max ( f ( nod ) , g ( s ) + h ( s )) ;
        // costul f al succesorului este valoarea maximă dintre
        // costul f al părintelui
        // costul atingerii succesorului + costul prevăzut (euristic) al succesorului
    endif
    dacă nu există un nou succesor atunci
       actualizați costul f al nodului și, dacă este necesar, a părinților săi (recursiv)
    
    dacă nod . succesori ⊆ coadă apoi coadă . scoate ( nod ) ; 
    // toți copiii au fost deja adăugați la coadă printr-o cale mai scurtă
    dacă memoria este plină, atunci începeți
      nodoPeggiore: suprafata = pi pi ù ù nod cu costuri ridicate f;
      pentru părinte în cel mai rău nod . Părinții nu încep
        părinte . succesori . elimina ( Cel mai prost nod ) ;
        dacă este necesar, atunci faceți coada . introduceți ( părinte ) ; 
      endfor
    endif

    coada . inserție ( e ) ;
  în cele din urmă
Sfârșit

Proprietate

SMA * se caracterizează prin următoarele proprietăți:

Lucrați cu un euristic , la fel ca A *.
Este complet dacă cea mai superficială soluție intră în memorie.
Este optim dacă soluția cea mai superficială intră în memorie, altfel returnează cea mai bună soluție pe care ar putea să o găsească.
Evitați explorarea aceleiași stări de mai multe ori până când memoria vă permite acest lucru.
Folosiți toată memoria disponibilă.
Utilizarea memoriei este proporțională cu viteza de execuție a algoritmului. Având suficientă memorie pentru a găzdui întregul arbore de execuție, viteza de execuție va fi optimă.

Notă

^ Unde $b$ ${\ displaystyle b}$ $b$ este factorul de ramificare (factor de ramificare) și $d$ ${\ displaystyle d}$ $d$ este adâncimea soluției.
^ Unde $n$ ${\ displaystyle n}$ $n$ este numărul de noduri care intră în memorie.
^ Dacă cea mai superficială soluție intră în memorie, altfel returnează cea mai bună soluție pe care ar putea să o găsească.
^ Dacă cea mai superficială soluție intră în memorie.
^ ^a ^b Rong Zhou și Eric A. Hansen, Memory-Bounded A * Graph Search ( PDF ), Proceedings of the Fifteen International Florida Artificial Intelligence Research Society Conference Society , Pensacola Beach, Florida, 2002, pp. 203-209.
^ (EN) Max Welling, Algoritmi de căutare informată (PDF) pe ics.uci.edu, Universitatea din California, Irvine , pp. 31-33. Accesat la 27 martie 2020 ( arhivat la 3 octombrie 2015) .
^ ^a ^b ^c Russell & Norvig, 2009 , p. 101 .
^ S. Russell, Metode eficiente de căutare limitate la memorie , editat de Neumann B., Proceedings of the 10th European Conference on Artificial intelligence , Viena, Austria, John Wiley & Sons, New York, NY, 1992, pp. 1–5.

Bibliografie

( 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, pp. 101-102, ISBN 978-0-13-604259-4 .

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.

[2] Unde $n$ ${\ displaystyle n}$ $n$ este numărul de noduri care intră în memorie.

[3] Dacă cea mai superficială soluție intră în memorie, altfel returnează cea mai bună soluție pe care ar putea să o găsească.

[4] Dacă cea mai superficială soluție intră în memorie.

[Zhou-Hansen-2002-5] Rong Zhou și Eric A. Hansen, Memory-Bounded A * Graph Search ( PDF ), Proceedings of the Fifteen International Florida Artificial Intelligence Research Society Conference Society , Pensacola Beach, Florida, 2002, pp. 203-209.

[6] (EN) Max Welling, Algoritmi de căutare informată (PDF) pe ics.uci.edu, Universitatea din California, Irvine , pp. 31-33. Accesat la 27 martie 2020 ( arhivat la 3 octombrie 2015) .

[russel-norvig-2009-7] Russell & Norvig, 2009 , p. 101 .

[8] S. Russell, Metode eficiente de căutare limitate la memorie , editat de Neumann B., Proceedings of the 10th European Conference on Artificial intelligence , Viena, Austria, John Wiley & Sons, New York, NY, 1992, pp. 1–5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]