Homework #2, 15.3.
-
1.) Suppose that we run a greedy search algorithm with h(n) = - g(n).
What sort of search will the greedy search emulate?
-
2.) Sometimes there is no good evaluation function for a problem, but there
is a good comparison method: a way to tell if one vertex is better than
another, without assigning numerical values to either. Show that this is
enough to do a best-first search. What properties of best-first search
do we give up if we only have a comparison method?
-
3.) The problem we did in class shows that the straight-line distance heuristic
is misleading in some cases, e.g. going from Iasi to Faragas. However,
the heuristic is perfect on the opposite problem: going from Fargas to
Iasi. Are there problems for which the heuristic is misleading in both
directions?
-
4.) Prove that if the heuristic function h obeys the triangel inequality,
then the f-cost along any path in the search tree is nondecreasing.
-
5.) Does monotonicity in f imply admissibility of the associated
h?
-
6.) Would a bidirectional A* search be a good idea? Under which
conditions would it be applicable? Describe how the algorithm would work.