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.

Figure 3.9: Summary of search strategies

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.