Search Algorithms

In artificial intelligence, search algorithms solve problems by systematically exploring a state space: they start from an initial state and apply actions to reach a goal state, building and traversing a tree or graph. A search problem is defined by an initial state, the possible actions, a transition model that says which state each action leads to, a goal test and a cost. This sense should be distinguished from “searching for” a datum in a database or on the web: here searching means finding a sequence of actions toward a goal.

Uninformed search

Uninformed or “blind” search uses no hint about where the goal is beyond the problem definition. Its classic strategies are breadth-first search, which explores the shallowest nodes first and is complete though it consumes much memory; depth-first search, which goes down one branch first and uses little memory but may not terminate; uniform-cost search, which always expands the node of lowest accumulated cost and finds the optimal path; and iterative deepening, which combines the best of the previous two.

Informed search

Informed or heuristic search uses a function that estimates closeness to the goal to guide exploration toward the most promising areas. Its examples are greedy best-first search and, above all, the A* algorithm, which combines the cost already traveled with that estimate and finds the optimal path if the heuristic meets certain conditions.

Other families

There are more types of search. Local search—such as hill climbing or simulated annealing—improves a single state and serves optimization problems. And adversarial search, such as the Minimax algorithm, applies to two-player games where an opponent responds to each move.