SMA * - SMA*

SMA * eller Simplified Memory Bounded A * er en korteste algoritme basert på A * -algoritmen. Hovedfordelen med SMA * er at den bruker et begrenset minne, mens A * -algoritmen kan trenge eksponentielt minne. Alle andre kjennetegn ved SMA * er arvet fra A *.

Prosess

Eiendommer

SMA * har følgende egenskaper

• Det fungerer med en heuristikk , akkurat som A *
• Det er komplett hvis det tillatte minnet er høyt nok til å lagre den grunne løsningen
• Det er optimalt hvis det tillatte minnet er høyt nok til å lagre den grunne optimale løsningen, ellers vil den returnere den beste løsningen som passer i det tillatte minnet
• Det unngår gjentatte tilstander så lenge minnebindingen tillater det
• Den vil bruke alt tilgjengelig minne
• Å forstørre minnebindingen til algoritmen vil bare øke beregningen
• Når nok minne er tilgjengelig til å inneholde hele søketreet, har beregningen en optimal hastighet

Gjennomføring

Implementeringen av SMA * er veldig lik den for A *, den eneste forskjellen er at når det ikke er plass igjen, beskjæres noder med høyest f-kostnad fra køen. Fordi disse nodene blir slettet, må SMA * også huske kostnadene til det best glemte barnet med foreldrenoden. Når det ser ut til at alle utforskede stier er verre enn en slik glemt sti, blir stien re-generert.

Pseudokode:

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

Referanser