Theory 1. Suppose you decide not to keep the explored set (i.e., the place where the explored nodesare saved) in the A* algorithm.
Computational 3. (a) Use the city “Road Distance” data given. Assume that only these roads between the cities exist. b. Write a Python program to search a road route from any city to any other cityusing this data. It should work for both cities that are directly connected (say, Ahmedabad to Indore) as well as for two cities that are not directly connected (say, Agartala to Hubli). c. Show Uniform Cost Search and A* search on this data. d. You should use Python features such as Lists, Input/ Output, Recursion, Backtracking etc. e. Your code should work for different inputs, i.e., the user should be able to inputany pair of cities as the origin-destination pair from the command line and the program should return the best found path. This means you must not hard-code your solution for a set of pairs. f. Design two different, non-trivial (e.g., a constant h(n) = c is a trivial heuristic) heuristics for A*. (1) The first one should be admissible. Empirically verify that the admissible heuristic yields the optimal solution. (2) Come up with an inadmissible heuristic function that will expand fewer nodes than your admissible heuristic in (1). Show this property for at least two origin-destination pairs in your code.
