Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC384: Introduction to Artificial Intelligence

Search: Uninformed Search

Practice Problems

1. List the order in which nodes are visited in the tree in the figure below for each of the following three search strategies (choosing leftmost branches first in all cases):

(a) Breadth-first search

(b) Depth-first search

(c) Iterative-deepening depth-first search

2. It would seem that iterative deepening search should have a higher asymptotic time complexity than breadth-first search because every time the depth-bound is increased it must start its search from scratch. However this is not true. Why?

3. How do depth-first, breadth-first and depth-first with iterative deepening search compare in terms of their asymptotic time complexity? In terms of their asymptotic space complexity? Please indicate any assumptions you are using (i.e. justifications from the textbook, from other sources, etc).