Depth-First-Depth-Bounded Search

• As depth-first search

• Disallow nodes beyond a certain depth d in tree

  • to implement, add depth in tree to search state

• Compare DFDB with Depth-first

  • DFDB: always finds solution at depth <= d
    • DF may find very deep solution before shallow ones
  • DFDB: never goes down infinite branch
    • relevant if search tree contains infinite branches
      • e.g. Eights puzzle
    • DFDB: we have a resource limit (b^d if b branching rate)
    • How do we choose d?

Previous slide

Next slide

Back to first slide

View graphic version