Question $1[3$ pts$]$: Figure $1$ shows a simplified map of part of Romania, and Table $1$ reports the straightline distance from each city to Bucharest. Use A$*$ search to find path from Lugoj to Bucharest $($using the straight$-$line distance as the heuristic$).$ Show the sequence of expanded nodes and the $g(N),h(N),$ and $f(N)$ scores for nodes in the fringe $($Must report the fringe, including $g(N),h(N)$ values, and node expanded$/$visited using table below$),$ and the final path from Lugoj to Bucharest $[3$ pts$]$

$\begin{array}{cc}\text{F}\text{r}\text{i}\text{n}\text{g}\text{e}\text{:}& \text{N}\text{o}\text{d}\text{e}\text{v}\text{i}\text{s}\text{i}\text{t}\text{e}\frac{d}{e}\text{x}\text{p}\text{a}\text{n}\text{d}\text{e}\text{d}\\ ?& ?\\ ?& ?\\ ?& ?\\ ?& ?\end{array}$

$\backslash$table$[[$Arad$,366,$Mehadia,$241],[$Bucharest$,0,$Neamt,$234],[$Craiova$,160,$Oradea,$380],[$Drobeta$,242,$Pitesti,$100],[$Eforie$,161,$Rimnicu Vilcea,$193],[$Fagaras$,176,$Sibiu,$253],[$Giurgiu$,77,$Timisoara,$329],[$Hirsova$,151,$Urziceni,$80],[$Iasi$,226,$Vaslui,$199],[$Lugoj$,244,$Zerind,$374]]$

Table $1$: straight$-$line distance from each city to Bucharest.