SMA*

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

Свойства

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

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

Реализация

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

Псевдокод

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; // нет решения, которое уместилось бы в данной памяти
    node := queue.begin(); // узел минимальной f-стоимости
    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; 
        // не осталось памяти, чтобы пройти мимо s, поэтому весь путь бесполезен
    else
        f(s) := max(f(node), g(s) + h(s));
        // f-значение потомка — максимум f-значения предка и
        // эвристика потомка + длина пути к потомку
    endif
    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); 
    // все потомки уже добавлены в очередь более коротким способом
    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

Примечания

1. Стюарт Рассел (1992). Б. Нойман (ed.). "Эффективные методы поиска с ограничением памяти". Вена (Австрия): издательство Джон Уайли и сыновья, Нью-Йорк (штат Нью-Йорк): 1–5. CiteSeerX 10.1.1.105.7839. {{cite journal}}: Cite journal требует |journal= (справка); Неизвестный параметр |book-title= игнорируется (справка)