4. Given the road map and the air distances (beeline) between the cities, we want to go from the city A to H using the path with minimum cost Solve the problem using a) Breadth First Search and b) A' Search algorithms. Show all the steps of algouthm on the search tree, - Draw the search tree, Write the cost at each node, - Write a number at each node showing its expansion order (i.e. root's number will be 1 Write solution path 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: Expansio Cost Order Cost(A) = 78 1 A Node Name BEELINE DISTANCES BETWEEN CITIES A D E H G 64 A 30 C 45 16 0 30 57 76 33 49 21 78 57 25 B 10 C 0 45 76 19 0 25 45 49 51 D 16 33 21 35 19 20 34 40 50 20 38 D 30 50 38 30 45 0 29 45 25 30 G 64 64 40 34 49 29 25 HT 178 45 30 0 4. Given the road map and the air distances (beeline) between the cities, we want to go from the city A to H using the path with minimum cost Solve the problem using a) Breadth First Search and b) A' Search algorithms. Show all the steps of algouthm on the search tree, - Draw the search tree, Write the cost at each node, - Write a number at each node showing its expansion order (i.e. root's number will be 1 Write solution path 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: Expansio Cost Order Cost(A) = 78 1 A Node Name BEELINE DISTANCES BETWEEN CITIES A D E H G 64 A 30 C 45 16 0 30 57 76 33 49 21 78 57 25 B 10 C 0 45 76 19 0 25 45 49 51 D 16 33 21 35 19 20 34 40 50 20 38 D 30 50 38 30 45 0 29 45 25 30 G 64 64 40 34 49 29 25 HT 178 45 30 0