SMA*
SMA* neboli Simplified Memory Constrained Algorithm A* je algoritmus nejkratší cesty založený na algoritmu A* . Hlavní výhodou SMA* je, že využívá omezenou paměť, zatímco algoritmus A* může vyžadovat exponenciální paměť. Všechny ostatní vlastnosti SMA* jsou zděděny z A* .
Vlastnosti
SMA* má následující vlastnosti:
- SMA* pracuje s heuristikou stejně jako A* .
- SMA* je kompletní, pokud je povolená paměť dostatečně velká na to, aby pojala i nejmělčí řešení.
- Optimální je, pokud je povolená paměť dostatečně velká pro uložení nejmělčího optimálního řešení, jinak se vrátí nejlepší řešení, které se do povolené paměti vejde.
- SMA* se vyhýbá opakovaným stavům, dokud to omezená paměť umožňuje.
- Bude využita veškerá dostupná paměť.
- Zvětšení velikosti paměti algoritmu pouze urychlí výpočet.
- Když je k dispozici dostatek paměti, aby se vešel celý vyhledávací strom, výpočet je optimální.
Implementace
Implementace SMA* je velmi podobná implementaci A* , jen s tím rozdílem, že když nezbude místo, uzly s nejvyššími náklady jsou z fronty odstraněny. Protože jsou tyto uzly odstraněny, SMA* si také musí pamatovat f-cost nejlepšího zapomenutého podřízeného uzlu s uzlem předka. Když se zdá, že všechny prozkoumané cesty jsou horší než tato zapomenutá, cesta je znovu vytvořena [1] .
Pseudokód
funkce SMA - star ( problém ) : fronta cesty
: sada uzlů , seřazené podle f - cost ; _ počáteční fronta . vložit ( problém . kořenový uzel ) ; _
zatímco True nezačíná pokud fronta . _
empty () then return failure ; // žádné řešení, které se nevejde do tohoto paměťového uzlu := fronta . start () ; // minimální f-cost uzel v případě problému . is - goal ( node ) then return success ;
s : = další následník ( uzel ) if ! problém . je - cíl ( s ) && hloubka ( s ) == max_hloubka then f ( s ) := inf ; // na překonání s nezbyla žádná paměť, takže celá cesta je k ničemu , jinak f ( s ) := max ( f ( uzel ) , g ( s ) + h ( s )) ; // f-hodnota potomka - maximální f-hodnota předka a // heuristika potomka + délka cesty potomka endif , pokud nejsou další následníci , aktualizujte f - cena uzlu a jeho předků , pokud je to potřeba
pokud uzel . následníci ⊆ fronta pak fronta . odstranit ( uzel ) ;
// všechny děti již byly přidány do fronty kratším způsobem
, pokud je paměť plná , začněte badNode := nejmělčí uzel s nejvyšší f - cost ; pro rodiče v badNode . rodiče začínají rodiči . _ nástupci . remove ( badNode ) ; v případě potřeby se postavte do fronty . vložit ( rodič ) ; endfor endif
fronta . vložit ( y ) ;
end while
end
Poznámky
- ↑ Stuart Russell (1992). B. Neumann, ed. „ Efektivní metody vyhledávání s omezenou pamětí “. Vídeň ( Rakousko ): John Wylie & Sons , New York ( NY ): 1.-5. CiteSeerX 10.1.1.105.7839 .