A celebrity has planned to give his/her live performance in Mumbai. He/she needs to travel from Kolkata to Mumbai by their own vehicle due to the safety reasons. Write a program in python3 to help them to reach the destination with optimal cost. The cost factor may be attributed by fuel consumption, time taken and/or expected speed on a particular route which are depicted in the below map. By using the information provided for each city.

a) Iterative Deepening A*

Note

1. Latitude and longitude per node are given in the below table. [Hint: Use the haversine formula to calculate the great-circle distance between two points that is, the shortest distance over the earths surface between two points. Using the latitude and longitude data for the cities as shown in following map and create a function which calculates the heuristic distance from each city to the destination city

2. Between every pair of states, parameters = (Fuel-L, Speed-KM/H, time expected-Hours) is given for each edge.

3. Take linear combination of the relevant cost parameters for your cost design without the loss of information.

(10,50,13) Kolkata (15,60,10) (8,100,6) (8,40,5) (5,40,7) (5,55,6) (7,78,5) Mumbai (8,50,67 (8,65,8) (5,46,5) (8,82,7) (7,45,8) (5,57,5) City Latitude Longitude Kolkata 22.5726N 88.3639E 21.1458N 79.0882 E B 19.7645N 74.4762 E C 19.9975N 73.78989 E D 19.8762N 75.3433E E 18.7557N 73.4091 E F 18.5204N 73.8567E Mumbai 19.0760N 72.8777 E