Problem 2. (30pts) You are given the initial state (a) and the goal state (b) of an 8-puzzle as shown below. 2 8 3 1 2 3 1 6 4 8 4. 7 5 (a) 7 6 5 (b) a) 10pts Apply A* search using Manhattan distance heuristic function. Draw the search tree including possible expanded states during the algorithm procedure. Compute the triple (g, h, f) for each state. Mark the optimal strategy found. b) 10pts Prove that the Manhattan distance heuristic is admissible