Search in AI: how breadth-first, depth-first and A* find solutions
Search algorithms find solutions by exploring a state space from a start state to a goal. Depth-first search and breadth-first search are uninformed strategies that do not use problem-specific knowledge. A* search uses a heuristic to estimate remaining cost and is complete and optimal when the heuristic is admissible.
.jpg){kind=link}
The search problem and tree search
Search in artificial intelligence is the process of finding a plan from a start state to a goal state. The standard protocol maintains a frontier of partial plans derived from a search tree, as described in the UC Berkeley CS188 textbook introduction. The algorithm repeatedly removes a node from the frontier, checks if it is a goal, and if not, expands it by adding all its children to the frontier.
The tree search pseudocode, presented in the UC Berkeley CS188 uninformed search notes, uses a frontier initialized with the start state. Each node stores information about its parent, the distance to the node, and the state itself. The expansion function generates all possible successor states by applying each available action to the current state.
Search strategies differ in how they select which node to remove from the frontier. Uninformed strategies have no knowledge of where goals are located, while informed strategies use estimates of distance to goals. The choice of strategy affects completeness, optimality, time complexity, and space complexity.
Depth-first search and breadth-first search
Depth-first search (DFS) always selects the deepest frontier node for expansion. It uses a last-in, first-out (LIFO) stack to represent the frontier, as explained in the UC Berkeley CS188 uninformed search notes. DFS is not complete because cycles in the state space can lead to infinite search trees, and it is not optimal because it does not consider path costs.
Breadth-first search (BFS) always selects the shallowest frontier node, using a first-in, first-out (FIFO) queue. BFS is complete because if a solution exists, the depth of the shallowest solution is finite. It is optimal only when all edge costs are equal, because it does not account for varying costs.
The time complexity of DFS is O(b^m) in the worst case, where b is the branching factor and m is the maximum depth. Its space complexity is O(bm). BFS has time complexity O(b^s) and space complexity O(b^s), where s is the depth of the shallowest solution. These complexities are stated in the UC Berkeley CS188 uninformed search notes.
Informed search and heuristics
Informed search uses heuristics to estimate the distance from a state to a goal. A heuristic is a function that takes a state as input and outputs an estimate, as described in the UC Berkeley CS188 informed search notes. For example, the Manhattan distance computes the sum of absolute differences in coordinates, assuming no walls in a maze.
Greedy search selects the frontier node with the lowest heuristic value, believing it is nearest to a goal. It uses a priority queue but only considers the estimated forward cost. Greedy search is not guaranteed to find a goal if one exists, nor is it optimal, especially with a poor heuristic.
A* search combines the backward cost g(n) used by uniform cost search with the heuristic forward cost h(n) used by greedy search, selecting the node with the lowest f(n) = g(n) + h(n). This approach is described in the UC Berkeley CS188 informed search notes.
Admissibility and optimality of A*
A* search is complete and optimal when the heuristic is admissible. An admissible heuristic never overestimates the true cost to reach a goal, and it is never negative. The admissibility constraint is defined in the UC Berkeley CS188 informed search notes as h(n) ≤ h*(n), where h*(n) is the true optimal forward cost.
The notes give an example of a heuristic that subtracts g(n) from 1, which makes f(n) constant and reduces A* to breadth-first search, which is not optimal for general edge costs.
Heuristics are often solutions to relaxed problems, where some constraints are removed. The Manhattan distance is an example because it ignores walls. This relaxation ensures the heuristic is a lower bound on the true distance, which is a key property for admissibility.
Practical considerations and resources
The Artificial Intelligence: A Modern Approach textbook by Stuart Russell and Peter Norvig covers search in chapters on problem-solving and search in complex environments. It is a widely used reference for AI algorithms, including search strategies.
MIT OpenCourseWare offers a course on artificial intelligence that introduces problem solving and search methods. The MIT 6.034 course page includes lecture videos and assignments that illustrate search algorithms in practice.
The UC Berkeley CS188 course home page provides access to lecture notes and resources for the course, which covers search as part of its curriculum. These materials are useful for understanding the implementation and properties of search algorithms.
| Strategy | Frontier representation | Completeness | Optimality | Time complexity | Space complexity |
|---|---|---|---|---|---|
| Depth-first search | LIFO stack | Not complete | Not optimal | O(b^m) | O(bm) |
| Breadth-first search | FIFO queue | Complete | Only with equal edge costs | O(b^s) | O(b^s) |
| Greedy search | Priority queue by h(n) | Not guaranteed | Not optimal | Not specified | Not specified |
| A* search | Priority queue by f(n) = g(n) + h(n) | Complete with admissible heuristic | Optimal with admissible heuristic | Not specified | Not specified |
Frequently asked questions
What is the difference between uninformed and informed search?
Uninformed search strategies, such as depth-first and breadth-first search, have no knowledge of where goals are located. Informed search strategies, such as greedy and A*, use heuristics to estimate the distance to goals.
Why is depth-first search not complete?
Depth-first search is not complete because cycles in the state space can lead to an infinite search tree, causing the algorithm to get stuck searching deeper without finding a solution.
When is breadth-first search optimal?
Breadth-first search is optimal only when all edge costs are equal, because it does not consider varying costs. In that case, it reduces to a special case of uniform cost search.
What is an admissible heuristic?
An admissible heuristic is one that never overestimates the true cost to reach a goal and is never negative. This condition is necessary for A* search to be optimal.
How does A* search combine cost and heuristic?
A* search uses a priority queue where the priority of a node is f(n) = g(n) + h(n), where g(n) is the total backward cost from the start and h(n) is the estimated forward cost to the goal.