СМА*

СМА* или Поједностављено меморијско ограничење А* је најкраћи пут алгоритма заснован на А* алгоритму. Главна предност СМА* је да користи ограничену меморију, док алгоритам А* треба експоненцијалну меморију. Све остале карактеристике СМА* су наслеђене од А*.

Процес

Као А*, обилази одговарајуће гране према хеуристици. Оно сто разликује СМА* је то да одсеца чворове чији развој није обећавајући. Овај приступ омогућава алгоритму да претражи гране и да се врати у претходни чвор како би претражио остале гране.

Проширивање и одсецање чворова је вођено двема вредностима $f$ за сваки чвор. Чвор $x$ чува вредности $f(x)$ и узима у обзир вредности путева кроз чвор. Приоритет је већи за нижу вредност. Као у А* ова вредност је иницијализована на $f(x)+g(x)$, али ће бити ажурирана у складу са променама. Потпуно проширени чвор ће имати вредност $f$ колику и наследници. Поред тога, чвор складишти $f$ вредност заборављених наследника. Та вредност је обновљена ако заборављени наследници нису обећавајући.

Својства

СМА* има следећа својства:

• Ради као истраживач, као А*.
• Потпуно је ако је дозвољена меморија довољна за складиштење најупрошћенијег решења.
• Оптимално је ако је дозвољена меморија довољна за складиштење најупрошћенијег оптималног решења, иначе ће вратити најбоље решење које се уклапа у оквир дозвољене меморије.
• Избегава понављање стања све док је меморија омогућена.
• Користи све расположиве меморије.
• Проширењем меморије ће се убрзати извршавање алгоритма.
• Када је на располагању толико меморије да стаје цело стабло претраге, извршавање има оптималну брзину.

Имплементација

Имплементација СМА* је слична оној од А*, једина разлика је у томе што не оставља простор с лева, мења чворове са највећом вредности. Пошто се ти чворови бришу, СМА* такође мора да запамти најбоље заборављено дете и чвора родитеља. Када се истраже сви путеви до тог заборављеног пута, пут се регенерише.

Псеудо код:

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