Name: Anonymous 2011-10-04 17:28
Consider a finite tree of depth d and branching factor b. (A tree of only the root node is considered depth zero; a tree with root and b successors has depth one, etc.) Suppose the shallowest goal node
is at depth g d.
1. What is the minimum and maximum number of nodes that might be generated by a depth-first search with depth bound equal to d?
2. What is the minimum and maximum number of nodes that might be generated by a breadth-first search?
3. What is the minimum and maximum number of nodes that might be generated by a depth-first iterative deepening search? Assume you start with an initial depth limit of 1, increment this limit by 1 each time no goal is found within the current limit.
is at depth g d.
1. What is the minimum and maximum number of nodes that might be generated by a depth-first search with depth bound equal to d?
2. What is the minimum and maximum number of nodes that might be generated by a breadth-first search?
3. What is the minimum and maximum number of nodes that might be generated by a depth-first iterative deepening search? Assume you start with an initial depth limit of 1, increment this limit by 1 each time no goal is found within the current limit.