# 3.7.3 Summary of Search Strategies

Figure 3.11 summarizes the searching strategies presented so far.

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 $P\neq NP$ 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 $A^{*}$ 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 $\mbox{IDA}^{*}$ reduce the space complexity at the cost of recomputing the elements on the frontier.

Lowest-cost-first, $A^{*}$ and $\mbox{IDA}^{*}$ searches are guaranteed to find a lowest-cost solution.