This assignment is to be turned in individually. You may talk to others and discuss ideas, but you should ultimately turn in your own work.
1. Describe the characteristics of a search space in which iterative deepening search performs much worse than depth-first search. In this situation, give big-O descriptions of the running time for iterative deepening and for depth-first search. Your answer should reflect the structure of a particular search space, not where in that search space the solution happens to be or how often it appears.
2. Sometimes there is no good evaluation function for a problem, but
there is a good comparison method: a way to tell if one node is better
than another, without assigning numerical values to either. Show that
this is enough to do a best-first search. Describe in words and pseudo
code how you would implement this method, and show what the differences
in time and memory would be (if any) compared to a standard greedy
search where you know the particular value associated with each node.
(This problem is based on textbook problem 4.12)
3. The heuristic path
algorithm is a best-first search in which the objective
function is f(n) = (2-w)g(n) + w h(n). For what values of w is this
algorithm guaranteed to be optimal, assuming that h is admissible?
Prove your results. (You may assume that 0 <= w <= 2). What kind of
search does this perform when w = 0? When w = 1? When w = 2? (This
problem is based on textbook problem 4.2)