Simplified Memory-Bounded Algorithm
- Simplified Memory-Bounded Algorithm
-
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.
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
A* search algorithm — In computer science, A* (pronounced A star ) is a best first, graph search algorithm that finds the least cost path from a given initial node to one goal node (out of one or more possible goals). It uses a distance plus cost heuristic function… … Wikipedia
Kahan summation algorithm — In numerical analysis, the Kahan summation algorithm (also known as compensated summation) significantly reduces the numerical error in the total obtained by adding a sequence of finite precision floating point numbers, compared to the obvious… … Wikipedia
Criss-cross algorithm — This article is about an algorithm for mathematical optimization. For the naming of chemicals, see crisscross method. The criss cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional… … Wikipedia
Алгоритм поиска A* — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… … Википедия
Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… … Wikipedia
Malbolge — This article is about the programming language. For the eighth circle of hell, which this language is named after, see Malebolge. Malbolge is a public domain esoteric programming language invented by Ben Olmstead in 1998, named after the eighth… … Wikipedia
Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space … Wikipedia
John von Neumann — Von Neumann redirects here. For other uses, see Von Neumann (disambiguation). The native form of this personal name is Neumann János. This article uses the Western name order. John von Neumann … Wikipedia
Sieve of Eratosthenes — Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime s square). In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple,… … Wikipedia
mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… … Universalium
