3.7 Pruning the Search Space

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 h(p) No Exponential
Lowest-cost-first Minimal cost(p) Least cost Exponential
A* Minimal cost(p)+h(p) Least cost Exponential
IDA* 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.

Figure 3.11: Summary of search strategies

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 PNP 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 IDA* reduce the space complexity at the cost of recomputing the elements on the frontier.

Lowest-cost-first, A* and IDA* searches are guaranteed to find a lowest-cost solution.