???? ???? ?

2.2 (5 points) A* Search Consider the graph shown below. The numbers on the edges represent the cost of the edge while the numbers in parentheses are heuristic estimates. Let A be the start state and G be the goal state. 1. (1 points) Run A* search on this graph. Please fill the table until the algorithm terminates. Then list the final path from A to G selected by the A* search and the final cost of the path. The first steps are filled for demonstration. | Step | Nodes expanded A A 5 2. (1 points) Did the A* algorithm find the optimal path? 3. (1 points) Is the given heuristic admissible? Give your explanation. 4. (3 points) Implement the A* algorithm to solve the given graph problem. Write a Python (or any preferred language) program that takes the graph as input and outputs the optimal path from A to G along with the total cost. Make sure to include the following: 1) Node representation. 2) A priority queue to select the next node based on the cost function (f =g + h). 3) A mechanism to track the visited nodes and the current path. 4) Output the final path and its cost after the algorithm terminates