Depth Limited Search

—depth-first search with depth limit l,

¡i.e., nodes at depth l have no successors

¡Solves infinite loop problem

—Common AI strategy: let user choose search/resource bound.
 Complete? No if l < d:

—Time? O(bl):

—Space? O(bl), i.e., linear space!

—Optimal? No if l > b

The DLS solve the infinite path problem. But introduces many othe problems.

Solve Yourself!

Only 20 cities on the map, so no path longer than 19. In fact, any city can reach any other in at most 9 steps. (Here Max depth=3)