Answer Happy

Question 1 Consider the following search problem, represented as a graph. Step costs are given next to each arc. Heuristic values are given within each node (as h=x). The successors of each node are indicated by the arrows out of that node. Successors are returned in left-to-right order, i.e., successors of S are (A, B), successors of A are (B, D), successors of B are (C, D), and so for node C and D in that order. For each search strategy below, show the order in which nodes are expanded (i.e., to expand a node means that its children are generated), ending with the goal node that is found. Show the path from start (S) to goal (G). Give the cost of the path that is found, or write "None". S h=6 Visited nodes: 3 Solution Path: 2 A h=4 1 B h=3 5 2 3 D h=1 3 h=3 Answer the following questions. For visited nodes and solution path write your answer in the following format - S,A,C...G For A* SEARCH what is: Cost of path found (consider the step cost not uniform cost): 1 Is the heuristic in the above graph admissible (Yes/No)? 8 pts G h=0 • If not, indicate the node whose heuristic needs to be changed (A/B/C/D/None):