SMA*

SMA* o o simplificado de memoria acotada A * es un algoritmo del camino más corto basada en el algoritmo A*. La principal ventaja de SMA * es que utiliza una memoria limitada, mientras que el algoritmo A * puede ser que necesite memoria exponencial. Todas las demás características de SMA * son heredados de A *.

Proceso

Como A *, se expande las ramas más prometedoras de acuerdo con la heurística. Lo que diferencia a SMA * aparte es que poda nodos cuya expansión se ha revelado menos prometedor de lo esperado. El enfoque permite que el algoritmo para explorar ramas y dar marcha atrás para explorar otras ramas.

La expansión y la poda de los nodos es impulsado por mantener dos valores de $f$ para cada nodo. El nodo $x$ almacena un valor de $f(x)$ que estima el costo de llegar a la meta mediante la adopción de un camino a través de ese nodo. Cuanto menor sea el valor, mayor es la prioridad. Al igual que en A * este valor es inicializado para $h(x)+g(x)$, pero entonces será actualizado para reflejar los cambios en esta estimación cuando sus hijos se expanden. Un nodo completamente expandido tendrá un valor de $f$ por lo menos tan alta como la de sus sucesores. Además, el nodo almacena el valor $f$ del sucesor mejor olvidado. Este valor se restablece si el sucesor olvidado se revela para ser el sucesor más prometedor.

Comenzando con el primer nodo, mantiene ABIERTO, ordenó lexicográficamente por $f$ y profundidad. Al elegir un nodo para expandir, elige la mejor de acuerdo a ese orden. Al seleccionar un nodo de podar, elige el peor.

Propiedades

SMA * tiene las siguientes propiedades

• Funciona con una heurística, al igual que A *
• Es completo si la memoria permitido es lo suficientemente alta para almacenar la solución menos profunda
• Es óptimo si la memoria permitido es lo suficientemente alta como para almacenar la solución óptima menos profunda, de lo contrario volverá la mejor solución que se ajusta en la memoria permitido
• Evita estados repite mientras la memoria unida permite
• Se utilizará toda la memoria disponible
• La ampliación de la memoria ligada del algoritmo sólo acelerará el cálculo
• Cuando hay suficiente memoria disponible para contener todo el árbol de búsqueda, a continuación, el cálculo tiene una velocidad óptima

Implementación

La aplicación de SMA * es muy similar a la de A *,la única diferencia es que cuando no hay ningún espacio a la izquierda, los nodos con el más alto f costo se podan de la cola. Debido a que se eliminan los nodos, la SMA * también tiene que recordar el f - coste del niño mejor olvidado con el nodo padre.​

Pseudo código:

function SMA-star(problem): path
  queue: set of nodes, ordered by f-cost;
begin
  queue.insert(problem.root-node);

  while True do begin
    if queue.empty() then return failure; //there is no solution that fits in the given memory
    node := queue.begin(); // min-f-cost-node
    if problem.is-goal(node) then return success;
    
    s := next-successor(node)
    if !problem.is-goal(s) && depth(s) == max_depth then
        f(s) := inf; 
        // there is no memory left to go past s, so the entire path is useless
    else
        f(s) := max(f(node), g(s) + h(s));
        // f-value of the successor is the maximum of
        //      f-value of the parent and 
        //      heuristic of the successor + path length to the successor
    endif
    if no more successors then
       update node-s f-cost and those of its ancestors if needed
    
    if node.successors ⊆ queue then queue.remove(node); 
    // all children have already been added to the queue via a shorter way
    if memory is full then begin
      badNode := shallowest node with highest f-cost;
      for parent in badNode.parents do begin
        parent.successors.remove(badNode);
        if needed then queue.insert(parent); 
      endfor
    endif

    queue.insert(s);
  endwhile
end

Referencias

• Datos: Q493743