Exercise 2        Name __________________        Score __/12

1. (3) Trace the operation of A* applied to the problem of getting to Bucharest from Lugoj using the straight-line distance heuristic. That is, show the sequence of nodes the algorithm will consider and the f, g and h score for each node.
2. (3) Does A* using TREE-SEARCH suffer from looping under admissible heuristics? Explain.
3. (3) On page 96 the straight-line distance heuristic leads greedy best-first search astray on the problem of going from Iasi to Fagaras. However, the heuristic is perfect on the opposite problem, going from Fagaras to Iasi. Are there problems for which the heuristic is misleading in both directions?
4. (3) Explain why the GRAPH-SEARCH when used for A* fails on the inconsistent graph at right.