You're in a remote town [S] with your car and are low on gas. Gas stations are present in the nearby towns [GI and G2] and reaching the nearest one is your Goal. You have access to a map that include roads between cities and the distances between each pair of cities with a road between them (available in the. You have to plan to solve this issue using A* heuristic search. One of your friends, who has a good knowledge of roads and has a fair idea of the terrain, can guess the approximate distance of the Goals (nearest petrol pumps) from any town. The distances calculated by your friend to the goal state are the 'heuristic distances'. Distances of paths to the immediately further towns are the 'actual distances. Write a program to arrive at the final path that the algorithm would take using the A* algorithm. Your code should output the fina; path and the total cost of getting from the current city to your goal destination (total distance). The distances calculated by your friend to the goal state are the 'heuristic distances". Distances of paths to the immediately further towns are the 'actual distances". The test case files are present in the folder Q1. Write a program to arrive at the final path that the algorithm would take using the A* algorithm. Your code should output the path and the distance of the path till that step. Input: Refer file 'casel.txt' In the first table you are given the list of towns and the corresponding Heuristic values. Second table comprises the actual path distances from one town to another. Example: Initial State: S 3 paths are possible: SA, SB, SC A* Heuristic values: SA-15+30=45 SB-2+40=42 SC-15+10=25 Queue=[[SA, 45], [SB, 42], [SC, 25]] Choose values with the lowest A* Heuristic value: [SC, 25]. Continue the same steps till a goal state is reached. Expected Output: ['SBDAEG1', 45] Execution Instructions: 1. Please make sure that your code is executable on running the command: For Python: python3 q1.py Example command: python3 q1.py case1.txt For Java: javac q1.java java q1 2. Write the output of the program to a text file in the Q1/Solutions folder with the naming convention - _solution.txt.