Full text of the second edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2017 is now available.

### 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.