depth-first search
In plain wordsA 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.
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 pushes along a single line of successors as far as it can, keeping its frontier in a last-in, first-out stack (or the call stack of a recursion), and backtracks to the most recent node with unexplored successors when it reaches a dead end. Its memory use grows only linearly with search depth — on the order of b·m nodes for branching factor b and maximum depth m — which makes it practical where 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. is not; but it can descend forever in infinite or cyclic spaces and does not guarantee a shortest solution. Backtracking search for constraint satisfactionconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes., PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs.'s execution strategy and minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best. game-tree search are all depth-first. In graph theory it underlies linear-time algorithms for cycle detection, topological sorting and strongly connected components.
Depth-first search found a solution quickly, but it was 40 moves longer than the optimum.
Origin
Its roots lie in maze-solving: Charles Pierre Trémaux's 19th-century rule for exploring a labyrinth by marking passages is an early form. Robert Tarjan's 1972 paper 'Depth-First Search and Linear Graph Algorithms' and his work with John Hopcroft made it a cornerstone of algorithm design, recognized in their 1986 Turing Award.
Related
- 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.
- 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.
- constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes.
- minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best.
- 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.
Sources
- Tarjan, R. (1972). Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing 1(2), 146–160.
Mentioned in
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., constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes., 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., 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.