Question 3: Informed Search 25 points Consider again the same maze shown in Figure 2. 1. Give the value of the heuristic given by the Manhattan distance for each state. Answer a b d e f h k 0 n h(n) 2. Is h admissible? Is it consistent? Explain Answer h admissible: Yes / No h consistent: Yes / No Page 7 of 9 CSC 432 HW Name ID: 3. Use the heuristic function above and give the: final search tree, final explored list (the order is important), final frontier list (the order is important: the leftmost node is the next oneto be explored, indicate the priority), solution found, cost of the solution, for each of the following algorithms: (a) Greedy best-first graph search. Answer Greedy Best First Search Final search tree: Final explored list: Final frontier list: Solution found: Cost of the solution: (b) A* graph search. Answer Question 4: Local Search ... ....15 points Circle the correct answer: 1. The solution found by simulated annealing depends on the initial state. [ True, False ] 2. Simulated annealing finds the optimal solution, if the probability of accepting abad move is approaching 1. [ True, False ] 3. The number of steps in simulated annealing depends only on the temperature schedule. [ True, False ] 4. The number of steps in local beam search depends on the objective function. [True, False ] 5. Local search algorithms consume less memory than uninformed search algo- rithms. [ True, False ] 6. Local beam search is not guaranteed to find an optimal solution. [True, False] 7. Simulated annealing consumes less memory than local beam search [ True, False ] 8. Local beam search with k= 1 is equivalent to hill-climbing [ True, False ). 9. Simulated annealing may sometimes find a local optimum only [ True, False ]. 10. Simulated annealing with constant temperature T = 0 at all times and ignoring the termination test, is equivalent to stochastic hill-climbing [ True, False ).

1 2 3 4 1 b e 2 a f 3 d 4 | 5 | 0 0 k Figure 2: Maze 1 2 3 4 1 b e 2 a f 3 d 4 | 5 | 0 0 k Figure 2: Maze