Problem Statement

Keerthana wants to travel from one place to another place. She is using one traveling app like MakeMy trip. There are source and destination cities where the agent has to decide on which path he needs to travel. The following graph will give the cities with their time and fare. Here the Start node is A and the Goal node is G$.$ Note that the edge value from A to B $500/3$hr$$ represents $500$ is maximum fare and $3$hr is the maximum time taken to reach A to B or vice$-$versa. Find the path which takes the least time and cost to reach the destination.

Use the following algorithms to solve the problem in python:

$1.$ IDA$*$

$2.$ Hill Climbing

Answer the following:

$1.$ Explain the environment of the agent

$2.$ Define the heuristic and or fitness function for the given algorithms and the given problem.

$3.$ Use appropriate data structures and implement given informed and local search algorithm and Print the path taken by the agent to the destination.

$4.$ Find and print space and time complexity using code in your implementation.