breadth-first search
In plain wordsA 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.
An uninformed 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. algorithm that expands nodes in order of their depth, using a first-in, first-out queue as the frontier: every node one step from the start is expanded before any node two steps away, and so on. It is complete whenever the branching factor is finite and finds a shortest path when all actions cost the same; with unequal costs, uniform-cost search (Dijkstra's algorithm), which always expands the cheapest frontier node, takes over that role. Its weakness is memory: with branching factor b and solution depth d it must store on the order of b^d nodes, which soon becomes infeasible. Outside AI it is a basic graph algorithm for finding connected components, hop-count distances in networks and bipartite structure.
Breadth-first search guarantees the fewest moves, but on this puzzle it ran out of memory at depth 14.
Origin
The usual reference is Edward F. Moore's 1959 paper on finding the shortest way through a maze. Konrad Zuse had used the idea in 1945 to find connected parts of a graph in his Plankalkül manuscript, which appeared in print only in 1972, and C. Y. Lee's 1961 maze-routing algorithm put it to work wiring circuit boards.
Related
- depth-first searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch.
- iterative deepening searchiterative deepening search, n.: A search strategy that explores one step deep, then starts over and explores two steps deep, then three, and so on. It repeats some work but needs very little memory and still finds the shortest 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.
- best-first searchbest-first search, n.: A 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* 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.
- depth-first searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch.
Sources
- Moore, E. F. (1959). The Shortest Path Through a Maze. Proceedings of the International Symposium on the Theory of Switching. Harvard University Press.
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., 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., depth-first searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch., 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., 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., best-first searchbest-first search, n.: A 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., iterative deepening searchiterative deepening search, n.: A search strategy that explores one step deep, then starts over and explores two steps deep, then three, and so on. It repeats some work but needs very little memory and still finds the shortest answer., tree of thoughtstree of thoughts, n.: A method in which an AI explores several possible next steps of a problem, judges which look promising and backs out of dead ends, like a chess player weighing moves, instead of reasoning in one straight line.