Best-first search

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

Judea Pearl described the best search as estimating the cost of a node n for a " heuristic evaluation function, which is dependent on the description of n in general, the description of the target, the information gathered by the algorithm up to this point, and especially from the additional knowledge about the problem domain itself "

To determine the most promising next-hop node, a priority queue is used in concrete implementations often.

A well-known example of the best looking is the A * algorithm. For best pathfinding search is also often used in the combinatorial optimization.

Pseudo-code

OPEN = [ initial state ] while OPEN is not empty do   Take first best node from OPEN, call it n   2 If n is the target state, determine the path back to n (by Noted parent node ) and give him.   3 Expanding successor of n   4 Rate each successor using the heuristic, add him to OPEN added, and noted th as a parent node. done However, this version of the algorithm is not complete, ie, the given pseudo - code can not be any possible combination of start and end nodes a way, even if it exists. For example, the algorithm gets caught in an endless loop as soon as a considered one node has no successor, except the parent node itself In this case, the parent node would be placed on the OPEN list again, and are then evaluated again, resulting in an endless recursion.

The following version extends the algorithm to an additional CLOSED list, which includes all previously evaluated nodes. Thus, since no node is visited twice, thereby prevent infinite loops.

OPEN = [ initial state ] CLOSED = [] while OPEN is not empty do   1 Open to best node from OPEN, call it n, add it added to CLOSED.   2 If n is the target state, determine path to n (by Noted parent node ) and place it back.   3 Expanding successor of n   4 For each successor:         a If not already in CLOSED, rate him using the heuristic paste added to OPEN and notice n as a parent node.         b. Otherwise: update remembered parent node of the successor if new path over n is less expensive than previous. done see also

  • Greedy algorithm
  • A * algorithm
  • Dijkstra's algorithm
A* search algorithm
120392
de