SMA*
SMA* eli Simplified Memory Constrained Algorithm A* on lyhimmän polun algoritmi , joka perustuu A*-algoritmiin . SMA* :n tärkein etu on, että se käyttää rajoitettua muistia, kun taas A*-algoritmi saattaa vaatia eksponentiaalista muistia. Kaikki muut SMA* :n ominaisuudet periytyvät A* :lta .
Ominaisuudet
SMA* :lla on seuraavat ominaisuudet:
- SMA* toimii heuristiikan kanssa kuten A* .
- SMA* on valmis, jos sallittu muisti on tarpeeksi suuri matalimman ratkaisun säilyttämiseen.
- On optimaalista, jos sallittu muisti on tarpeeksi suuri matalimman optimaalisen ratkaisun tallentamiseen, muuten palautetaan paras sallittuun muistiin mahtuva ratkaisu.
- SMA* välttää toistuvia tiloja niin kauan kuin rajoitettu muisti sen sallii.
- Kaikki käytettävissä oleva muisti käytetään.
- Algoritmin muistin koon kasvattaminen vain nopeuttaa laskentaa.
- Kun muistia on riittävästi käytettävissä koko hakupuuhun, laskenta on optimaalisella nopeudella.
Toteutus
SMA* -toteutus on hyvin samankaltainen kuin A * -toteutus , sillä ainoa ero on, että kun tilaa ei ole jäljellä, korkeimman f-kustannustason solmut poistetaan jonosta. Kun nämä solmut poistetaan, SMA* :n tulee muistaa myös parhaan unohdetun alisolmun f-kustannus esi-isolmun kanssa. Kun näyttää siltä, että kaikki tutkitut polut ovat huonompia kuin tämä unohdettu polku, polku luodaan uudelleen [1] .
Pseudokoodi
toiminto SMA - star ( ongelma ) : polkujono
: joukko solmuja , järjestetty f - kustannusten mukaan ; _ _ aloitusjono . _ insert ( ongelma . root - node ) ;
kun taas True aloita jos jono . tyhjä () sitten palauta virhe ; // ei ratkaisua, joka mahtuu tähän muistisolmuun : = jonoon . aloita () ; // vähimmäisf-kustannussolmu , jos ongelma . on - tavoite ( solmu ) sitten palauttaa menestyksen ;
s := seuraava - seuraaja ( solmu )
jos ! ongelma . on - tavoite ( t ) && syvyys ( t ) == max_depth sitten
f ( s ) := inf ;
// ei ole muistia jäljellä s:n ohitse, joten koko polku on hyödytön
muuten
f ( s ) := max ( f ( solmu ) , g ( s ) + h ( s )) ;
// jälkeläinen f-arvo - suurin esi-isän f-arvo ja
// jälkeläinen heuristinen + jälkeläinen polun pituus
endif
jos seuraajia ei ole , päivitä f - solmun ja sen esivanhempien hinta tarvittaessa
jos solmu . seuraajat ⊆ jono sitten jono . poista ( solmu ) ;
// kaikki lapset on jo lisätty jonoon lyhyemmällä tavalla,
jos muisti on täynnä , aloita
badNode : = matalan solmu korkeimmalla f - hinnalla ; vanhemmille BadNodessa . _ _ vanhemmat aloittavat vanhemman . _ seuraajia . poista ( badNode ) ; tarvittaessa jonoon . _ _ lisää ( vanhempi ) ; endfor endif
jonoa . lisätä ( t ) ;
loppu
lopulla
Muistiinpanot
- ↑ Stuart Russell (1992). B. Neumann, toim. " Tehokkaat hakumenetelmät rajoitetulla muistilla ". Wien ( Itävalta ): John Wylie & Sons , New York ( NY ): 1-5. CiteSeerX 10.1.1.105.7839 .