Artificial
Intelligence 2E
foundations of computational agents
The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).
3.7.3 Summary of Search Strategies
Figure 3.11 summarizes the searching strategies presented so far.
| Strategy | Selection from Frontier | Path found | Space |
|---|---|---|---|
| Breadth-first | First node added | Fewest arcs | Exponential |
| Depth-first | Last node added | No | Linear |
| Iterative deepening | — | Fewest arcs | Linear |
| Greedy best-first | Minimal | No | Exponential |
| Lowest-cost-first | Minimal | Least cost | Exponential |
| Minimal | Least cost | Exponential | |
| — | Least cost | Linear |
“Path found” refers to guarantees about the path found (for graphs with finite branching factor and arc costs bounded above zero). The algorithms that guarantee to find a path with fewest arcs or least cost are complete. “No” means that it is not guaranteed to find a path in infinite graphs. Both depth-first search and greedy best-first search can fail to find a solution on finite graphs with cycles unless cycle pruning or multiple-path pruning is used.
Space refers to the space complexity, which is either “Linear” in the maximum number of arcs in a path expanded before a solution is found or “Exponential” in the number of arcs in a path expanded before a solution is found.
Iterative deepening is not an instance of the generic search algorithm, and so the iterative deepening methods do not have an entry for the selection from the frontier.
A search algorithm is complete if it is guaranteed to find a solution if there is one. Those search strategies that are guaranteed to find a path with fewest arcs or the least cost are complete. They have worst-case time complexity which increases exponentially with the number of arcs on the paths explored. Whether there can be algorithms that are complete but better than exponential time complexity is related to the question. The algorithms that are not guaranteed to halt (depth-first and greedy best-first) have an infinite worst-case time complexity.
Depth-first search used linear space with respect to the number of arcs in the paths explored, but is not guaranteed to find a solution even if one exists. Breadth-first, lowest-cost-first, and may be exponential in both space and time, but are guaranteed to find a solution if one exists, even if the graph is infinite as long as there are finite branching factors and arc costs are bounded above zero. Iterative deepening and reduce the space complexity at the cost of recomputing the elements on the frontier.
Lowest-cost-first, and searches are guaranteed to find a lowest-cost solution.