SMA*

SMA* o o simplificat de memòria acotada A * és un algoritme del camí més curt basada en l'algoritme A*. La principal ventaja de SMA * és que utilisa una memòria llimitada, mentres que l'algoritme A * pot ser que necessite memòria exponencial. Totes les demés característiques de SMA * són heretats de *.

Procés

Com A *, s'expandix les branques més prometedores d'acort en l'heurística. Lo que diferencia a SMA * a banda és que poda nodos l'expansió dels quals s'ha revelat menys prometedor de lo esperat. L'enfocament permet que l'algoritme per a explorar branques i donar marcha arrere per a explorar atres branques.

L'expansió i la poda dels nodos és impulsat per mantindre dos valors de $f$ per a cada nodo. El nodo $x$ almagasena un valor de $f(x)$ que estima el cost d'aplegar a la meta per mig de l'adopció d'un camí a través d'eixe nodo. Quant menor siga el valor, major és la prioritat. De la mateixa manera que en A * este valor és inicializado per a $h(x)+g(x)$, pero llavors serà actualisat per a reflectir els canvis en esta estimació quan els seus fills s'expandixen. Un nodo completament expandit tindrà un valor de $f$ per lo manco tan alta com la dels seus successors. Ademés, el nodo almagasena el valor $f$ del successor millor oblidat. Este valor es restablix si el successor oblidat es revela per a ser el successor més prometedor.

Començant en el primer nodo, manté ABIERTO, va ordenar lexicográficamente per $f$ i profunditat. En elegir un nodo per a expandir, elegix la millor d'acort a eixe orde. En seleccionar un nodo de podar, elegix el pijor.

Propietats

SMA * té les següents propietats

• Funciona en una heurística, de la mateixa manera que A
• * És complet si la memòria permés és lo suficientment alta per a almagasenar la solució menys profunda
• És òptim si la memòria permés és lo suficientment alta com per a almagasenar la solució òptima menys profunda, de lo contrari tornarà la millor solució que s'ajusta en la memòria permés
• Evita estats repetix mentres la memòria unida permet
• S'utilisarà tota la memòria disponible
• L'ampliació de la memòria lligada de l'algoritme només accelerarà el càlcul
• Quan hi ha suficient memòria disponible per a contindre tot l'arbre de busca, a continuació, el càlcul té una velocitat òptima