best-first search
In plain wordsA family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next.
A general state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal. strategy that keeps the frontier in a priority queue and always expands the node with the best (usually lowest) value of an evaluation function f(n). The choice of f defines the algorithm: f(n) = g(n), the path cost so far, gives uniform-cost search (Dijkstra's algorithm); f(n) = h(n), a heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer. estimate of the remaining cost, gives greedy best-first search, which is often fast but neither optimal nor, in infinite spaces, complete; and f(n) = g(n) + h(n) gives A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first.. Beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility. is a memory-bounded relative that keeps only the k best nodes at each step, the form used to decode sequences from language modelslarge language model, n.: A computer program trained on enormous amounts of text to predict the words that come next. At vast scale, that simple skill lets it chat, answer questions, translate, summarize and write code..
Origin
Selecting the node judged best by a heuristic appeared in James Doran and Donald Michie's Graph Traverser (1966) and in A* (1968). Judea Pearl's book Heuristics (1984) systematized best-first search as a general framework.
Related
- A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first.
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility.
- breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first.
- hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak.
- state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal.
Sources
- Doran, J. E. & Michie, D. (1966). Experiments with the Graph Traverser Program. Proceedings of the Royal Society A 294, 235–259.
- Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.
Mentioned in
A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first., breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first., Dijkstra's algorithmDijkstra's algorithm, n.: A classic method for finding the shortest routes from one starting point to every other point on a map or network, by always settling the nearest not-yet-settled point next., heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal., admissible heuristicadmissible heuristic, n.: An estimate of the remaining distance to a goal that is never more than the real distance — an optimistic guess — which lets some search methods guarantee that they find the best route., branch and boundbranch and bound, n.: A method for finding the provably best answer to a hard puzzle: divide the possibilities into groups, quickly estimate the best any group could offer, and throw out every group that cannot beat the best answer already in hand., Donald MichieDonald Michie, prop. n.: A British codebreaker turned AI pioneer who built a game-playing learning machine out of matchboxes and founded Edinburgh's influential machine-intelligence research group.