Best search

from Wikipedia, the free encyclopedia

Best-first search ( engl. Best-first search ) is an algorithm for searching a graph in which the most promising node is selected in each iteration, evaluated after a certain heuristic . This makes it one of the informed search algorithms .

Judea Pearl described the best search as estimating the cost of a node n according to a "heuristic evaluation function , which is generally dependent on the description of n , the description of the goal, the information gathered by the algorithm up to this point and above all on the additional knowledge about the problem domain itself. "

In specific implementations, a priority queue is often used to determine the most promising successor node .

A well-known example of the best search is the A * algorithm . To find the way, best search is often used in combinatorial optimization .

Pseudo code 

OPEN = [Ausgangszustand]
while OPEN nicht leer
do
 1. Nimm besten Knoten aus OPEN, nenne ihn n.
 2. Wenn n der Zielzustand ist, bestimme Pfad zu n (anhand gemerkter Elternknoten) und gib ihn zurück.
 3. Expandiere Nachfolger von n.
 4. Bewerte jeden Nachfolger mithilfe der Heuristik, füge ihn zu OPEN hinzu, und merke n als Elternknoten.
done

However, this version of the algorithm is not complete ; In other words, the given pseudo-code does not find a path to every possible combination of start and destination nodes, even if this exists. For example, the algorithm gets caught in an infinite loop as soon as a considered node has no more descendants, except for the parent node itself. In this case, the parent node would be placed on the OPEN list again and then considered again, which results in an endless recursion.

The following version extends the algorithm by an additional CLOSED list that contains all nodes that have already been evaluated. Since no node is visited twice, this prevents infinite loops. 

OPEN = [Ausgangszustand]
CLOSED = []
while OPEN nicht leer
do
 1. Nimm besten Knoten aus OPEN, nenne ihn n, füge ihn zu CLOSED hinzu.
 2. Wenn n der Zielzustand ist, bestimme Pfad zu n (anhand gemerkter Elternknoten) und gib ihn zurück.
 3. Expandiere Nachfolger von n.
 4. Für jeden Nachfolger:
       a. Wenn nicht bereits in CLOSED, bewerte ihn mithilfe der Heuristik, füge ihn zu OPEN hinzu und merke n als Elternknoten.
       b. Sonst: Aktualisiere gemerkten Elternknoten des Nachfolgers, wenn neuer Weg über n kostengünstiger ist als vorheriger.
done

See also

Individual evidence

  1. ↑ Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving . Addison-Wesley, 1984. p. 48.
  2. ↑ http://wiki.roblox.com/index.php/Best-first_search#Pseudo_Code

Web links