Consider 11 cities denoted by A,B,C,D,E,F,G,H,I,J, and K, such that some of them are connected by roads permitting travel in both directions. The distance between connected cities appears at the end in the following triplets: (A,B,2), (B,C,4), (C,D,6), (D,H,8), (H,I,10),(I,K,12), (A,E,14), (E,F,16), (F,G,3), (G,H,6), (H,J,9), (C,G,5), and (J,K,20). The first two elements in each of these triplets are the cities connected by a road. There are 26 possible operators for the purpose of any search over this network of cities since there are 13 pairs of cities such that the cities in each pair are connected by a single road and travel is possible in both directions along each road. Any tree search for finding a path between two cities does not include any city twice or more on any path, which means that cities are not revisited along any path. The cost of a path is the total distance between the start and end of the path which equals the sum of distances between cities appearing contiguously along the path. The initial state in a search instance is A and the goal is K. The values of h which is a heuristic function are as follows: h(A) = 41, h(B) = 35, h(C) = 22, h(D) = 28, h(E) = 53, h(F) = 38, h(G) = 28, h(H) = 22, h(I) = 14, h(J) = 20, and h(K) = 0. h^* is the perfect heuristic which means that the value of h^* equals the cost of cheapest path to the goal for each city. Assuming all this, report answer to each question in the left column of the following table in the right column. You do not have to include an explanation.

1. Is h admissible?

2. Which citys shortest distance to K is overestimated the most by h?

3. For which cities are the values of h and h^* equal?

4. Consider the path A-B-C-D in the search tree of A*. What is the value of f(D)?

5. Consider the path A-B-C-G in the search tree of A*. What is the value of f(G)?

6. What is the value of

|h(A) - h^*(A)| + |h(B) h^*(B)|?

7. For how many cities does h not underestimate h^*?

8. What is the value of

|h(C) - h^*(C)| + |h(D) h^*(D)|?

9. Is heuristic h such that h(n) = 0.5 * h(n) admissible?

10. Is heuristic h such that h(n) = (h(n) 10) for every node that does not contain goal and h(n) = 0 if n contains goal, admissible?