СМА*
СМА* или Поједностављено меморијско ограничење А* је најкраћи пут алгоритма заснован на А* алгоритму. Главна предност СМА* је да користи ограничену меморију, док алгоритам А* треба експоненцијалну меморију. Све остале карактеристике СМА* су наслеђене од А*.
Процес
[уреди | уреди извор]Као А*, обилази одговарајуће гране према хеуристици. Оно сто разликује СМА* је то да одсеца чворове чији развој није обећавајући. Овај приступ омогућава алгоритму да претражи гране и да се врати у претходни чвор како би претражио остале гране.
Проширивање и одсецање чворова је вођено двема вредностима за сваки чвор. Чвор чува вредности и узима у обзир вредности путева кроз чвор. Приоритет је већи за нижу вредност. Као у А* ова вредност је иницијализована на , али ће бити ажурирана у складу са променама. Потпуно проширени чвор ће имати вредност колику и наследници. Поред тога, чвор складишти вредност заборављених наследника. Та вредност је обновљена ако заборављени наследници нису обећавајући.
Својства
[уреди | уреди извор]СМА* има следећа својства:
- Ради као истраживач, као А*.
- Потпуно је ако је дозвољена меморија довољна за складиштење најупрошћенијег решења.
- Оптимално је ако је дозвољена меморија довољна за складиштење најупрошћенијег оптималног решења, иначе ће вратити најбоље решење које се уклапа у оквир дозвољене меморије.
- Избегава понављање стања све док је меморија омогућена.
- Користи све расположиве меморије.
- Проширењем меморије ће се убрзати извршавање алгоритма.
- Када је на располагању толико меморије да стаје цело стабло претраге, извршавање има оптималну брзину.
Имплементација
[уреди | уреди извор]Имплементација СМА* је слична оној од А*, једина разлика је у томе што не оставља простор с лева, мења чворове са највећом вредности. Пошто се ти чворови бришу, СМА* такође мора да запамти најбоље заборављено дете и чвора родитеља. Када се истраже сви путеви до тог заборављеног пута, пут се регенерише.[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; //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
Референце
[уреди | уреди извор]- ^ Русселл, С. (1992). „Ефикасни методи претраге ограничене меморије”. Ур.: Неман, Б. Зборник десете европске конференције о Вештачкој интелигенцији. Беч, Аустриа: Јохн Wилеy и Сонс, Њујорк, НY. стр. 1—5. ЦитеСеерX: 10
.1 .1 .105 .7839.