SMA * - SMA*

SMA * oder Simplified Memory Bounded A * ist ein Algorithmus mit dem kürzesten Pfad, der auf dem A * -Algorithmus basiert . Der Hauptvorteil von SMA * besteht darin, dass ein begrenzter Speicher verwendet wird, während der A * -Algorithmus möglicherweise einen exponentiellen Speicher benötigt. Alle anderen Eigenschaften von SMA * werden von A * geerbt.

Prozess

Eigenschaften

SMA * hat die folgenden Eigenschaften

• Es funktioniert mit einer Heuristik , genau wie A *
• Es ist vollständig, wenn der zulässige Speicher hoch genug ist, um die flachste Lösung zu speichern
• Es ist optimal, wenn der zulässige Speicher hoch genug ist, um die flachste optimale Lösung zu speichern. Andernfalls wird die beste Lösung zurückgegeben, die in den zulässigen Speicher passt
• Es vermeidet wiederholte Zustände, solange die Speicherbindung dies zulässt
• Es wird der gesamte verfügbare Speicher verwendet
• Durch Vergrößern der Speichergrenze des Algorithmus wird die Berechnung nur beschleunigt
• Wenn genügend Speicher verfügbar ist, um den gesamten Suchbaum aufzunehmen, hat die Berechnung eine optimale Geschwindigkeit

Implementierung

Die Implementierung von SMA * ist der von A * sehr ähnlich. Der einzige Unterschied besteht darin, dass Knoten mit den höchsten f-Kosten aus der Warteschlange entfernt werden, wenn kein Speicherplatz mehr vorhanden ist. Da diese Knoten gelöscht werden, muss sich die SMA * auch die f-Kosten des am besten vergessenen Kindes mit dem übergeordneten Knoten merken. Wenn es den Anschein hat, dass alle erkundeten Pfade schlechter sind als ein solcher vergessener Pfad, wird der Pfad neu generiert.

Pseudocode:

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

Verweise