Consider the graph shown below. The numbers on the arcs are the arc lengths.

Draw the search tree and solve the problem of selecting a route for a drone flying between cities towards the goal, G based on the greedy search strategy $($heuristics$).$

Heuristic Function

Flying Distance to the Goal $[$G$]$

$\backslash$table$[[$A$,50],[$B$,25],[$C$,45],[$D$,35]]$

Numbers in Blue are ground$-$travel distance between nodes $($locations$)$

I. Draw the search tree?

II$.$ Perform a best$-$first $($greedy search$),($String Node is S$,$ Goal is G$).$ Show the sequence of nodes that are expanded by the search

III. Simulate A$*$ search with an expanded list on this graph $($String Node is S$,$ Goal is G$).$ At each step, show the path to the state of the node that's being expanded the length of that path, the total estimated cost of the path $($actual $+$ heuristic$),$ and the current value of the expanded list $($as a list of states$).$