Submit the

submission.py file. The deliverable for the assignment is this $\text{'}$

submission.py$\text{'}$ file with the necessary functions$/$methods completed.

Also include snapshots of the output of your program and the generated graph showing the search results in your submission.

Your task is to implement an informed search algorithm that will calculate a driving route between two points in Romania with a minimal time and space cost. The search$\_$submission$\_$tests.py file to help you along the way. We will be using an undirected network representing a map of Romania.

$A^{**}$ search

The implemented $A^{**}$ search uses Euclidean distance as the default heuristic, which is implemented in function euclidean$\_$dist$\_$heuristic$().$ It is passed to a$\_$star$()$ as provide null$\_$heuristic$()$ as a baseline heuristic to test against when calling a$\_$star tests.

Notes:

You need to include start and goal in the path.

$2$ If your start and goal are the same then just return $[].$

The above are just to keep your results consistent with our test cases.

You can access all the neighbors of a given node by calling graphinode$),$ or graph.neighbors$($node$)$ ONLY.

You can access the weight of an edge using: graph.get$\_$edge$\_$weight$($node$\_1,$ node$\_2).$ Not using this method will result in your explored nodes count being hig

You can access the $(x,y)$ position of a node using: graph.nodes$[$n$][\text{'}$pos$\text{'}].$ You will need this for calculating the heuristic distance.

Bidirectional $A^{**}$ search

implement bidirectional $A^{**}$ search. Remember that you need to calculate a heuristic for both the start$-$to$-$goal search and the goal$-$to$-$start search. bidirectional$\_$a$\_$star$0$ should return the path from the start node to the goal node, as a list of nodes.

submission.py file:

import heapq

import os