SMA * - SMA*
Алгоритмы поиска по графам и деревьям |
---|
Списки |
похожие темы |
SMA * или Simplified Memory Bounded A * - алгоритм кратчайшего пути, основанный на алгоритме A * . Основное преимущество SMA * заключается в том, что он использует ограниченную память, в то время как алгоритму A * может потребоваться экспоненциальная память. Все остальные характеристики SMA * унаследованы от A *.
Процесс
Характеристики
SMA * имеет следующие свойства
- Он работает с эвристикой , как A *
- Это завершено, если разрешенная память достаточно велика для хранения самого мелкого решения.
- Оптимально, если разрешенная память достаточно велика для хранения самого мелкого оптимального решения, в противном случае будет возвращено лучшее решение, которое умещается в разрешенной памяти.
- Он избегает повторяющихся состояний, пока это позволяет ограниченная память.
- Он будет использовать всю доступную память
- Увеличение объема памяти алгоритма только ускорит расчет.
- Когда доступно достаточно памяти, чтобы вместить все дерево поиска, расчет имеет оптимальную скорость.
Выполнение
Реализация 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; //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 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
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