— Ch. 1 · Algorithmic Foundations And Heuristics —
Best-first search.
~2 min read · Ch. 1 of 5
Judea Pearl described best-first search as estimating the promise of node n by a heuristic evaluation function. This function may depend on the description of n and the description of the goal. It also relies on information gathered during the search up to that point. Most importantly, it uses any extra knowledge about the problem domain. The algorithm explores a regular undirected graph by expanding the most promising node chosen according to a specified rule. Some authors use the term specifically for searches predicting how close a path end is to a solution. Paths judged closer to a goal are expanded first in these specific cases.
Greedy Versus Optimal Approaches
A* search algorithms incorporate distance from the start alongside estimated distances to the goal. Neither A* nor B* qualifies as greedy best-first search because they include this additional cost factor. Greedy best-first search expands the first successor of the parent using only heuristic values. If a successor's heuristic is better than its parent, the successor goes to the front of the queue. The parent then reinserts directly behind it before the loop restarts. Otherwise, the successor inserts into the queue based on its heuristic value alone. This approach does not guarantee an optimal path or minimum cost solution like A* might provide.Data Structures And Implementation
Efficient selection of the current best candidate for extension typically uses a priority queue. The queue orders nodes based on their heuristic distances from the target. A procedure named GBS marks the start node as visited and adds it to the queue. The main loop continues while the queue remains non-empty. It removes the vertex with the minimum distance to the target from the queue. Each neighbor n of the current node gets checked if it has not been visited yet. If that neighbor equals the target, the algorithm returns it immediately. Otherwise, the system marks n as visited and adds it back to the queue.