Изворни код странице 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 <math>f</math> za svaki čvor. Čvor <math>x</math> čuva vrednosti <math>f(x)</math> i uzima u obzir vrednosti puteva kroz čvor. Prioritet je veći za nižu vrednost. Kao u A* ova vrednost je inicijalizovana na <math>f(x)+g(x)</math>, ali će biti ažurirana u skladu sa promenama. Potpuno prošireni čvor će imati vrednost <math>f</math> koliku i naslednici. Pored toga, čvor skladišti <math>f</math> 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.<ref>{{cite conference |last=Russell| first = S. |year=1992| id = {{citeseerx|10.1.1.105.7839}} | title = Efikasni metodi pretrage ograničene memorije | booktitle = Zbornik desete evropske konferencije o Veštačkoj inteligenciji | location = Beč, Austria | editor-first = B. | editor-last=Neman| publisher = John Wiley i Sons, Njujork, NY |pages=1–5}}</ref>

Pseudo kod:
<source lang="pascal">
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
</source>

== Reference ==
{{reflist}}

{{normativna kontrola}}

{{СОРТИРАЊЕ:СМА*}}
[[Категорија:Графовски алгоритми]]
[[Категорија:Алгоритми претраживања]]
[[Категорија:Усмеривачки алгоритми]]