SMA*

SMA* ili Pojednostavljeno memorijsko ograničenje A* je najkraći put algoritma zasnovan na A* algoritmu. Glavna prednost SMA* je da koristi ograničenu memoriju, dok algoritam A* treba eksponencijalnu memoriju. Sve ostale karakteristike SMA* su nasleđene od A*.

Proces Kao A*, obilazi odgovarajuće grane prema heuristici. Ono sto razlikuje SMA* je to da odseca čvorove čiji razvoj nije obećavajući. Ovaj pristup omogućava algoritmu da pretraži grane i da se vrati u prethodni čvor kako bi pretražio ostale grane.

Proširivanje i odsecanje čvorova je vođeno dvema vrednostima za svaki čvor. Čvor čuva vrednosti i uzima u obzir vrednosti puteva kroz čvor. Prioritet je veći za nižu vrednost. Kao u A* ova vrednost je inicijalizovana na , ali će biti ažurirana u skladu sa promenama. Potpuno prošireni čvor će imati vrednost koliku i naslednici. Pored toga, čvor skladišti vrednost zaboravljenih naslednika. Ta vrednost je obnovljena ako zaboravljeni naslednici nisu obećavajući.

Svojstva SMA* ima sledeća svojstva: Radi kao istraživač, kao A*. Potpuno je ako je dozvoljena memorija dovoljna za skladištenje najuprošćenijeg rešenja. Optimalno je ako je dozvoljena memorija dovoljna za skladištenje najuprošćenijeg optimalnog rešenja, inače će vratiti najbolje rešenje koje se uklapa u okvir dozvoljene memorije. Izbegava ponavljanje stanja sve dok je memorija omogućena. Koristi sve raspoložive memorije. Proširenjem memorije će se ubrzati izvršavanje algoritma. Kada je na raspolaganju toliko memorije da staje celo stablo pretrage, izvršavanje ima optimalnu brzinu.

Implementacija Implementacija SMA* je slična onoj od A*, jedina razlika je u tome što ne ostavlja prostor s leva, menja čvorove sa najvećom vrednosti. Pošto se ti čvorovi brišu, SMA* takođe mora da zapamti najbolje zaboravljeno dete i čvora roditelja. Kada se istraže svi putevi do tog zaboravljenog puta, put se regeneriše.

Pseudo kod: 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

Reference

Категорија:Графовски алгоритми Категорија:Алгоритми претраживања Категорија:Усмеривачки алгоритми