SMA*
SMA* eller Simplified Memory Constrained Algorithm A* er en algoritme med den korteste vej baseret på A*-algoritmen . Den største fordel ved SMA* er, at den bruger begrænset hukommelse, mens A*-algoritmen kan kræve eksponentiel hukommelse. Alle andre egenskaber ved SMA* er nedarvet fra A* .
Egenskaber
SMA* har følgende egenskaber:
- SMA* arbejder med heuristik ligesom A* .
- SMA* er fuldført, hvis den tilladte hukommelse er stor nok til at rumme den mest overfladiske løsning.
- Det er optimalt, hvis den tilladte hukommelse er stor nok til at gemme den laveste optimale løsning, ellers vil den bedste løsning, der passer i den tilladte hukommelse, blive returneret.
- SMA* undgår gentagne tilstande, så længe begrænset hukommelse tillader det.
- Al tilgængelig hukommelse vil blive brugt.
- Forøgelse af hukommelsesstørrelsen af algoritmen vil kun fremskynde beregningen.
- Når nok hukommelse er tilgængelig til at passe til hele søgetræet, er beregningen ved sin optimale hastighed.
Implementering
SMA* -implementeringen ligner meget A* -implementeringen, med den eneste forskel, at når der ikke er plads tilbage, fjernes noderne med den højeste f-omkostning fra køen. Da disse noder slettes, skal SMA* også huske f-omkostningen for den bedst glemte underknude med forfaderknuden. Når det ser ud til, at alle udforskede stier er værre end denne glemte, genskabes stien [1] .
Pseudokode
funktion SMA - stjerne ( problem ) : sti
kø : sæt af noder , sorteret efter f - omkostninger ;
start
køen . indsætte ( problem . root - node ) ;
mens True begynder hvis køen . _
empty () returner derefter fejl ; // ingen løsning, der passer i denne hukommelsesknude : = kø . start () ; // minimum f-cost node if problem . is - mål ( node ) returner derefter succes ;
s := næste - efterfølger ( node )
if ! problem . er - mål ( r ) && dybde ( r ) == max_depth derefter
f ( s ) := inf ;
// ingen hukommelse tilbage til at komme forbi s, så hele stien er ubrugelig
ellers
f ( s ) := max ( f ( knudepunkt ) , g ( s ) + h ( s )) ;
// efterkommer f-værdi - maksimal forfader f-værdi og
// efterkommer heuristik + efterkommer sti længde
endif ,
hvis der ikke er flere efterfølgere , så
opdater f - omkostninger for node og de for dens forfædre , hvis det er nødvendigt
hvis node . efterfølgere ⊆ kø derefter kø . fjern ( knudepunkt ) ;
// alle børn er allerede blevet tilføjet til køen på en kortere måde,
hvis hukommelsen er fuld , så start
badNode := laveste node med højeste f - omkostning ;
for forælder i badNode . forældre begynder forældre . _
efterfølgere . fjern ( badNode ) ; hvis nødvendigt så kø . indsætte ( forælder ) ; endfor endif
kø . indsætte ( r ) ;
ende mens
ende
Noter
- ↑ Stuart Russell (1992). B. Neumann, red. " Effektive søgemetoder med begrænset hukommelse ". Wien ( Østrig ): John Wylie & Sons , New York ( NY ): 1-5. CiteSeerX 10.1.1.105.7839 .