Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
3.6.2 Summary of Search Strategies
The table in Figure 3.9 gives a summary of the searching strategies presented so far.
| Strategy | Selection from Frontier | Halts? | Space |
| Depth-first | Last node added | No | Linear |
| Breadth-first | First node added | Yes | Exponential |
| Best-first | Globally minimal h(p) | No | Exponential |
| Lowest-cost-first | Minimal cost(p) | Yes | Exponential |
| A* | Minimal cost(p)+h(p) | Yes | Exponential |
"Halts?" means "Is the method guaranteed to halt if there is a path to a goal on a (possibly infinite) graph with a finite number of neighbors for each node and where the arc costs have a positive lower bound?" Those search strategies where the answer is "Yes" have worst-case time complexity which increases exponentially with the size of the path length. Those algorithms that are not guaranteed to halt have infinite worst-case time complexity.
Space refers to the space complexity, which is either "Linear" in the path length or "Exponential" in the path length.
The depth-first methods are linear in space with respect to the path lengths explored but are not guaranteed to find a solution if one exists. Breadth-first, lowest-cost-first, and A* may be exponential in both space and time, but they are guaranteed to find a solution if one exists, even if the graph is infinite (as long as there are finite branching factors and positive non-trivial arc costs).
Lowest-cost-first and A* searches are guaranteed to find the least-cost solution as the first solution found.
