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 

Графовски алгоритми
Алгоритми претраживања
Усмеривачки алгоритми
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 Графовски алгоритми Алгоритми претраживања Усмеривачки алгоритми