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.

   Repeated states can occur but not infinitely.

   Note that the text proved A* is optimal using TREE-SEARCH if h(n) is admissible.

   We assume g(n) > 0 for all but the goal node. Then for a node expanded more than one time in a cycle, g(n+1) = g(n) + c(n,a,n+1) > g(n) where n is one expansion, n+1 is the next expansion and c(n,a,n+1) > 0 is the cost of the cycle from n to same node n+1. Therefore, g(n+1) > g(n) and is monotonically increasing to infinity as n increases.

   Since A* is optimal either n is on the optimal path or not. If on the optimal path, g(n) <= g(G) so repetitions to n is finite and repeated states stop. If not on the optimal path, some repetition of n will not be expanded and repeated states stop.

    

3. (3) On page 96 the straight-line distance (by inspecting the map below) 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?

   Going between Rimnicu Vilcea and Lugoj is one example. The shortest path is the southern one, through Mehadia, Dobreta and Craiova. But  a greedy search using the straight-line heuristic starting in Rimnicu Vilcea will start the wrong way heading to Sibiu. Starting at Lugoj, the heuristic will correctly lead us to Mehadia, but then a greedy search will return to Lugoj and oscillate forever between these two cities.

    

4. (3) Explain why the GRAPH-SEARCH when used for A* fails on the inconsistent graph at right.

Fails is not quite accurate, it does not fail to find a solution but does fail to find the optimal solution.

Side note:

For the graph to be consistent:

7 = h(S)<=c(S,a,A)+h(A)=
                 4+1 = 5

which is false.

Starting at S, the GRAPH-SEARCH fringe with f(n) and the closed list is:

      fringe                                    closed

1. [S]                                        []
2. [(A, 5=4+1), (B,7=2+5)]        [S]
3. [(B, 7=2+5), (G,8=8+0)]        [S, A]
4. [(A, 4=3+1),(G,8)]                 [S, A, B]
5. [(G,8)]                                   [S, A, B]
6. []                                           [S, A, B]

Goal reached S->A->G at cost of 8 though optimal path S->B->A->G cost of 7.