Assume that you are given the responsibility to supply food, water, medicines and other amenities to the flooded areas in the city of Chennai. It is your responsibility to supply the needs to all the areas affected by flood where people are suffering. You are provided with a map of the city with flooded land$-$marks marked $($vertices$).$ You are provided with an autonomous battery$-$operated micro aquatic boat that detects the flooded areas and responds to people who wave to it for help. The autonomous battery$-$operated micro aquatic boat works on a battery and hence it has to take a path such that all the roads $($edges in the graph$)$ are covered, but no road is repeated more than once. After getting the details, the boat agent reports to you, the taken path and the locations where people are requesting for help.

The problem here is to find the shortest route that travels through all the lanes in the area. The places can be visited more than once. The shortest path includes all the roads travelled only once. Help your autonomous battery$-$operated micro aquatic boat in finding such a path given a starting point and the map.

Here the area map is represented as a graph. The algorithm takes the starting point and the graph as the input and produces the shortest path covering all the edges only once.

Use the following algorithms to solve the problem:

$1.$ Greedy Best first search

$2.$ Genetic algorithm

Answer the following:

$1.$ Explain the environment of the agent $[20\%$ weightage$]$

$2.$ Define the heuristic and or fitness function for the given algorithms and the given problem. $[20\%$ weightage$]$

$3.$ Use appropriate data structures and implement given informed and local search algorithm and Print the path taken by the agent. $[40\%$ weightage$]$

$4.$ Find and print space and time complexity using code in your implementation. $[20\%$ weightage$]$