SMA*

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

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

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

Реализация Реализация SMA* очень похожа на реализацию A* с той лишь разницей, что когда не остаётся места, узлы с наибольшей f-стоимостью удаляются из очереди. Поскольку эти узлы удаляются, SMA* также должен помнить 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; // нет решения, которое уместилось бы в данной памяти 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

Примечания

Категория:Алгоритмы на графах Категория:Маршрутизация Категория:Алгоритмы поиска Категория:Игровой искусственный интеллект