You should complete this assignment on your own (not in teams). You may discuss the assignment with other students and on the class discussion list cse473-discuss, but you should do your own writeup, and you should not pass around your written solution.
1. The two objectives of finding a solution as quickly as possible and finding an optimal solution are often conflicting. In some problems, one may design two heuristic functions h and k, such that h is admissible and k is not admissible, with k resulting in much faster search most of the time. Then, one may try to take advantage of both functions.
The tree search algorithm that uses the evaluation function f(N) = g(N) + h(N) is A*, since h is admissible. Let Ae* be a variant of this algorithm, defined as follows: Ae* also uses the evaluation function f(N) = g(N) + h(N), but at each iteration, instead of expanding a node with the minimum value of f (let's call that value m), it expands an arbitrary node N’ among those such that f(N') is less than or equal to (1+e)m.
(a) Prove that the cost C of a path returned by Ae* is less than or equal to (1+e)C*, where C* is the cost of a path returned by A*.
(b) Next, explain briefly how Ae* can be modified to make use the second heuristic function k in order to reduce the time of the search, while still retaining this quality guarantee. What tradeoff is being made in choosing e?
2. Beam search is a variety of breath-first tree search search that makes use of a heuristic function h that estimates the distance to a goal. When a node is expanded, the h-values of the children are calculated, and only the m best children are added to the fringe, for some fixed constant m. The fringe is stored in a FIFO queue (not a priority queue).
(a) Describe in words, perhaps with the aid of a sketch, the kind of state space where beam search would work well, and in particular, be better than best-first search or depth-first search.
(b) Beam search is neither complete nor optimal. Write pseudo-code for an iterative version of beam search that is guaranteed to be complete. (Note: the tricky part is to make search that every iteration terminates!) Explain briefly why iterative beam search is still not guaranteed to find optimal solutions.