4. Consider the 8-puzzle problem. The start state and end stats are given in the following: 3 1 2 4 5 6 7 8 1 2 3 4 5 6 7 End state Start state Assume the evaluation function f(n)=g(n)+h(n). Here, g(n)=-2*d+3*n+17, where n is the node number, d is the depth of the node n and h(n) is given in the following. a) Ifh(n) misplaced tiles, trace the operation of A* search. You have to calculate f, g and h for each node n. (20 points) b) If h(n)= Manhattan distance, trace the operation of A* search. You have to calculate f, g and h for each node n. (20 points)