The graph below shows the state$-$space for a problem. The cost of an action to go

from one node, n$1,$ to another node, n$2,$ C$($n$1,$ n$2)$ is indicated by the number near

the edge $($n$1,$ n$2)$ connecting the two nodes. The heuristic value of each node, h$($n$),$

is shown below the graph. You are going to use A$*$ algorithm to solve this

problem.

$(1)$ Illustrate each iteration of the A$*$ tree$-$search algorithm, beginning with

expansion of node S$,$ until the goal node $($G$)$ is expanded. For each iteration

of the algorithm, show the tree for that iteration. Distinguish between

expanded and frontier$/$unexpanded$.$ Show the f$()$ values next to each node.

$(2)$ Is the described heuristic function admissible? If you think it is not, explain

why?

h$($A$)=6$

h$($B$)=3$

h$($C$)=3$

h$($D$)=2$

h$($E$)=5$

h$($F$)=5$

h$($G$)=0$