Question 1: Inadmissible Heuristic Affects Completeness [50 points] We saw in the class that if the heuristic function h is inadmissible, A* search may find a suboptimal goal. We now show that A may not even be complete, namely it may not terminate even if a goal with small cost exists. Consider the following graph where the right branch goes on forever: where A is the initial state C1 C2 C3 and G is the only goal state. Let cost (A, B)- 1/2, cost (B, G)-1/2 so the solution path from A to G has a cost of 1. Furthermore, let cost(A.G)-1 cost(G.G)-1/2 ost(C2,C3) = 1/4 dost(C3.G)-1/8 so that the costs decrease by half toward the right Suppose for all states s the heuristic function h(s)0 ercept that h(B) 100. This makes h inadmissible. Nonetheless, let us run the A* algorithm with this h. 1. (5 points) By definition, what range of h(B) is considered admissible? 2. (20 points) Run the A* algorithm (on slide 9 of part 2 of informed search) by hand for five iterations: that is, you should execute step 5 five times. At the end of each iteration, show the following states in OPEN e states in CLOSED . for each state, show its f,g, h values . for each state, show its back pointer 3. (5 points) What is limf(Ci)? Show your derivation. Question 1: Inadmissible Heuristic Affects Completeness [50 points] We saw in the class that if the heuristic function h is inadmissible, A* search may find a suboptimal goal. We now show that A may not even be complete, namely it may not terminate even if a goal with small cost exists. Consider the following graph where the right branch goes on forever: where A is the initial state C1 C2 C3 and G is the only goal state. Let cost (A, B)- 1/2, cost (B, G)-1/2 so the solution path from A to G has a cost of 1. Furthermore, let cost(A.G)-1 cost(G.G)-1/2 ost(C2,C3) = 1/4 dost(C3.G)-1/8 so that the costs decrease by half toward the right Suppose for all states s the heuristic function h(s)0 ercept that h(B) 100. This makes h inadmissible. Nonetheless, let us run the A* algorithm with this h. 1. (5 points) By definition, what range of h(B) is considered admissible? 2. (20 points) Run the A* algorithm (on slide 9 of part 2 of informed search) by hand for five iterations: that is, you should execute step 5 five times. At the end of each iteration, show the following states in OPEN e states in CLOSED . for each state, show its f,g, h values . for each state, show its back pointer 3. (5 points) What is limf(Ci)? Show your derivation