Consider the following map and the straight-line distance to the city entitled “M” from every other city. Find the shortest path from “A” to “M” using A* searching algorithm. Draw the tree structure...

Consider the following map and the straight-line distance to the city entitled “M” from every other city. Find the shortest path from “A” to “M” using A* searching algorithm.  Draw the tree structure and trace algorithm using open and closed list. Also state the shortest route with cost.

H(n) value of each city is given in the following table. To calculate the final f(n) of each city use the following formula except city M.

g(n)=Straight line distance(n)+last two digits of your registration number i-e
58

F(n)=g(n) + H(n)

Heuristic value H(n) of each city given in the following table