Problem Statement

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.

$*$ Goal Test: The goal test is satisfied when the agent reaches the starting point after visiting all nodes in the graph, covering each edge only once.

Answer the Following:

$1.$ Draw the complete State transition tree using Greedy Best First Search Algorithm, and tabular it as openList, ClosedList, Goal Test, Successors, visited node

$2.$ Represent and initialize the node and graph in python using dictionary or array based grid

$3.$ Question doesn$$t come up with heuristic, So design a heuristic like Manhattan based or Euclidean and explain

$4.$ Write python code along with data structure for heuristic function