best first search

(redirected from Best-first search)
Also found in: Wikipedia.

best first search

(algorithm)
A graph search algorithm which optimises breadth first search by ordering all current paths according to some heuristic. The heuristic attempts to predict how close the end of a path is to a solution. Paths which are judged to be closer to a solution are extended first.

See also beam search, hill climbing.
References in periodicals archive ?
"Linear-Space Best-First Search," Artificial Intelligence, Volume 62, Issue 1, July 1993, Pages 41-78, ISSN 0004-3702
[A.sup.*] algorithm, local search algorithm and best-first search algorithm are all heuristic search algorithm with heuristic function.
Hence, our BFB based CA algorithm consists of two parts: best-first search based procedure and backtracking procedure.
Dechter, Rina; Pearl, Judea (1985).Generalized best-first search strategies and the optimality of A*.
Many of the PBP algorithms in the literature can be thought of as applying some kind of best-first search with branch-and-bound pruning.
Condition 1, as in standard best-first search, guarantees optimality because search is guided towards an optimal.
The algorithms tested were the breadth-first search, Dijsktra's algorithm, the best-first search, and two [A.sup.*] algorithms (the two had differences in their distance estimates).
For these planning problems, agent-centered search methods compete with other heuristic search methods such as greedy (best-first) search (Russell and Norvig 1995) that can find plans faster than agent-centered search or linear-space best-first search (Korf 1993; Russell 1992) that can consume less memory (Bonet and Geffner 2001; Korf 1993).
The heuristic function of incremental best-first search can also be changed dynamically as parts of the terrain get discovered, D* (Stentz 1995) and D*LITE (Likhachev and Koenig 2000), for example, exhibit the following behavior: The robot repeatedly moves from its current location with minimal execution cost to a goal location, assuming that unknown terrain is traversable.
The search phase consists of a simple best-first search strategy.
We therefore implemented a forward planner, FORPLAN, using a simple best-first search strategy.