СМА*

SMA* или упрощенная память с ограниченной памятью A* — это алгоритм кратчайшего пути, основанный на алгоритме A* . Основное преимущество SMA* заключается в том, что он использует ограниченную память, тогда как алгоритму A* может потребоваться экспоненциальная память. Все остальные характеристики SMA* унаследованы от A*.

Характеристики

SMA* имеет следующие свойства

• Он работает с эвристикой , так же, как A*
• Он завершен, если разрешенная память достаточно велика для хранения самого поверхностного решения.
• Оптимально, если разрешенная память достаточно велика для хранения наименьшего оптимального решения, в противном случае будет возвращено лучшее решение, которое помещается в разрешенную память.
• Он избегает повторяющихся состояний, пока это позволяет ограничение памяти.
• Он будет использовать всю доступную память
• Увеличение объема памяти алгоритма только ускорит расчет.
• Когда доступно достаточно памяти для размещения всего дерева поиска, скорость вычислений оптимальна.

Выполнение

Реализация простой памяти A* очень похожа на реализацию A*; единственное отличие состоит в том, что узлы с самой высокой f-стоимостью удаляются из очереди, когда не остается места. Поскольку эти узлы удаляются, простой A*, ограниченный в памяти, должен запомнить f-стоимость наиболее забытого дочернего узла родительского узла. Когда кажется, что все исследованные пути хуже такого забытого пути, путь возрождается.

Псевдокод:

function simple memory bounded A*-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
    end if
    if no more successors then
       update f-cost of node 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
      bad Node := shallowest node with highest f-cost;
      for parent in bad Node.parents do begin
        parent.successors.remove(bad Node);
        if needed then queue.insert(parent); 
      end for
    end if

    queue.insert(s);
  end while
end