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.

From diagram, representation of different places using some short forms and graph using dictionary of them as follows:

pu: Purasawalkam

pe: Perumbakkam

v: Velachery

g: Guindy

t: Tambaram

n: Nungambakkam

graph $=\{$

$\text{'}$pu$\text{'}$: $[(\text{'}$pe$\text{'},8),(\text{'}$t$\text{'},9)],$

$\text{'}$pe$\text{'}$: $[(\text{'}$pu$\text{'},8),(\text{'}$t$\text{'},11),(\text{'}$v$\text{'},6),(\text{'}$g$\text{'},7)],$

$\text{'}$v$\text{'}$: $[(\text{'}$g$\text{'},14),(\text{'}$pe$\text{'},6)],$

$\text{'}$g$\text{'}$: $[(\text{'}$pe$\text{'},7),(\text{'}$t$\text{'},10),(\text{'}$n$\text{'},12),(\text{'}$v$\text{'},14)],$

$\text{'}$n$\text{'}$: $[(\text{'}$g$\text{'},12),(\text{'}$t$\text{'},15)],$

$\text{'}$t$\text{'}$: $[(\text{'}$n$\text{'},15),(\text{'}$g$\text{'},10),(\text{'}$pe$\text{'},11),(\text{'}$pu$\text{'},9)]$

$\}$

node$\_$coordinates $=\{$

$\text{'}$pu$\text{'}$: $(0,0),$

$\text{'}$pe$\text{'}$: $(1,1),$

$\text{'}$t$\text{'}$: $(2,2),$

$\text{'}$v$\text{'}$: $(3,3),$

$\text{'}$g$\text{'}$: $(4,4),$

$\text{'}$n$\text{'}$: $(5,5)$

$\}$

For the heuristic, Consider the Manhattan distance heuristic. This heuristic calculates the distance between two points on a grid$-$like path by summing the absolute differences of their coordinates. In our case, each vertex represents a location in a grid$-$like environment, and the distance between them can be approximated by the Manhattan distance.

def manhattan$\_$heuristic$($node$1,$ node$2)$:

x$1,$ y$1=$ node$\_$coordinates$[$node$1]$

x$2,$ y$2=$ node$\_$coordinates$[$node$2]$

# Calculate Manhattan distance

distance $=$ abs$($x$2-$ x$1)+$ abs$($y$2-$ y$1)$

return distance

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.$ Write python code using Greedy Best First Search Algorithm using above heuristic and satisfying the Goal Test

$2.$ Time Complexity and the Space Complexity for this problem