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.