4. (60 points) In the folowing 8-puzzle problem, the initial state, the goal state and the cost function are given below. Find the actions (which states) to reach the goal state. Solve the problem using a) Breadth First Search (24 points) and b) A* Search (36 points) algorithms. Show all the steps of algorithm on the search tree. Draw the search tree, (30% points) Write the cost at each node, (30% points) Write a number at each node showing its expansion order (i.e. root's number will be 1) (30% points) Write solution path (10% points) SHOW THE EXECUTION OF THE ALGORITHMS STEP BY STEP, Assume that the algorithms keep an explored set to handle repeated states. Use the following labeling method to show the expansion order and cost at each node. For example: Cost(A) 178 Acana Cost Node Namo be Take h(n) = number of misplaced tiles. Initial State Goal State 2 8 3 3 6 1 7 4 5 1 2 8 76 4 5