„Simplified Memory-Bounded Algorithm“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[gesichtete Version]

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

Inhalt gelöscht Inhalt hinzugefügt

Inline

Version vom 4. Februar 2011, 11:41 Uhr

Der Simplified Memory-Bounded Algorithm (SMA*) ist ein Algorithmus zur speicheroptimierten Suche in Bäumen. Es ist ein Sonderfall des A*-Algorithmus' zur Berechnung eines kürzesten Pfades.

Wenn der zu untersuchende Baum mit einem Greedy-Algorithmus durchsucht wird und nicht genügend Speicher vorhanden ist, um den kompletten Baum im Speicher zu halten, dann werden ungünstige Knoten bzw. Teilbäume zunächst ignoriert. Im Vorgängerknoten werden Informationen über die Kosten des Teilbaums gespeichert. Wenn bei den verbleibenden Teilbäumen kein besseres Ergebnis erzielt wird, kann die Berechnung an den günstigen vergessenen Knoten wieder aufgenommen werden. Der Einspareffekt beim Speicherverbrauch resultiert daraus, dass wenig erfolgversprechende Lösungsvarianten zunächst nicht im Speicher gehalten werden.

@@ Zeile 1: / Zeile 1: @@
 Der '''Simplified Memory-Bounded Algorithm''' (SMA*) ist ein Algorithmus zur speicheroptimierten Suche in Bäumen. Es ist ein Sonderfall des [[A*-Algorithmus]]' zur Berechnung eines [[Kürzester_Pfad|kürzesten Pfades]].
-Wenn der zu untersuchende Baum mit einem [[Greedy-Algorithmus]] durchsucht wird und nicht genügend Speicher vorhanden ist, um den kompletten Baum im Speicher zu halten, dann werden ungünstige Knoten bzw. Teilbäume zunächst ignoriert. Im Vorgängerknoten werden Informationen über die Kosten des Teilbaums gespeichert. Wenn sich bei den verbleibenden Teilbäumen keinen besseren Ergebnis zu erzielen ist, kann an den günstigen vergessenen Knoten die Berechnung wieder aufgenommen werden. Der Einspareffekt beim Speicherverbrauch resultiert daraus, dass wenig erfolgversprechende Lösungsvarianten zunächst nicht im Speicher gehalten werden.
+Wenn der zu untersuchende Baum mit einem [[Greedy-Algorithmus]] durchsucht wird und nicht genügend Speicher vorhanden ist, um den kompletten Baum im Speicher zu halten, dann werden ungünstige Knoten bzw. Teilbäume zunächst ignoriert. Im Vorgängerknoten werden Informationen über die Kosten des Teilbaums gespeichert. Wenn bei den verbleibenden Teilbäumen kein besseres Ergebnis erzielt wird, kann die Berechnung an den günstigen vergessenen Knoten wieder aufgenommen werden.
+Der Einspareffekt beim Speicherverbrauch resultiert daraus, dass wenig erfolgversprechende Lösungsvarianten zunächst nicht im Speicher gehalten werden.
 [[Kategorie:Algorithmus]]