SMA*
SMA* sau Simplified Memory Constrained Algorithm A* este un algoritm cu calea cea mai scurtă bazat pe algoritmul A* . Principalul avantaj al SMA* este că folosește o memorie limitată, în timp ce algoritmul A* poate necesita memorie exponențială. Toate celelalte caracteristici ale SMA* sunt moștenite de la A* .
Proprietăți
SMA* are următoarele proprietăți:
- SMA* funcționează cu euristică la fel ca A* .
- SMA* este complet dacă memoria permisă este suficient de mare pentru a stoca soluția cea mai superficială.
- Este optim dacă memoria permisă este suficient de mare pentru a stoca cea mai mică soluție optimă, altfel soluția cea mai bună care se potrivește în memoria permisă va fi returnată.
- SMA* evită stările repetate atâta timp cât permite memoria limitată.
- Toată memoria disponibilă va fi folosită.
- Mărirea dimensiunii memoriei algoritmului nu va face decât să accelereze calculul.
- Când este disponibilă suficientă memorie pentru a se potrivi întregului arbore de căutare, calculul este la viteza optimă.
Implementare
Implementarea SMA* este foarte asemănătoare cu implementarea A* , singura diferență fiind că atunci când nu mai rămâne spațiu, nodurile cu cel mai mare cost f sunt eliminate din coadă. Pe măsură ce aceste noduri sunt șterse, SMA* trebuie să-și amintească și costul f al celui mai bun nod copil uitat cu nodul strămoș. Când pare că toate căile explorate sunt mai rele decât aceasta uitată, calea este recreată [1] .
Pseudocod
funcţia SMA - star ( problema ) : coada de căi
: set de noduri , ordonate după f - cost ; începe coada . inserare ( problemă . nod rădăcină ) ; _
în timp ce True începe dacă coadă . empty () apoi returnează eșecul ; // nicio soluție care să se potrivească în acest nod de memorie := coada . începe () ; // nodul minim f-cost dacă problema . is - goal ( nod ) apoi returnează succesul ;
s := următorul - succesor ( nod )
dacă ! problema . este - scop ( e ) && adâncime ( e ) == adâncime_max . apoi
f ( e ) := inf ;
// nu a mai rămas nicio memorie pentru a trece de s, deci întreaga cale este inutilă
altfel
f ( s ) := max ( f ( nod ) , g ( s ) + h ( s )) ;
// valoarea f descendentă - valoarea f maximă a strămoșului și
// euristica descendentă + lungimea căii descendentă
endif
dacă nu mai există succesori, atunci
actualizați f - costul nodului și pe cei ai strămoșilor săi dacă este necesar
dacă nodul . succesori ⊆ coadă apoi coadă . elimina ( nod ) ;
// toți copiii au fost deja adăugați la coadă într-un mod mai scurt
dacă memoria este plină , atunci începe
badNode := cel mai puțin adânc nod cu cel mai mare cost f ; pentru părinte în badNode . părinții încep părinte . _ succesori . elimina ( badNode ) ; dacă este necesar , puneți la coadă . insert ( părinte ) ; endfor endif
coada . insert ( e ) ;
sfârşitul în timp ce
sfârşitul
Note
- ↑ Stuart Russell (1992). B. Neumann, ed. „ Metode de căutare eficiente cu memorie limitată ”. Viena ( Austria ): John Wylie & Sons , New York ( NY ): 1-5. CiteSeerX 10.1.1.105.7839 .