Question $5(30\mathrm{.}0$ marks$)$

Consider the following search problem, represented as a graph. Each node is label by a capital letter and the value of a heuristic function is shown in maroon. Each edge is labelled by the cost to traverse that edge. The start state is $\text{'}S\text{'}$ and the only goal state is $\text{'}G\text{'}.$ Perform the $A^{**}$ search to find the shortest path from node $S$ to node $G.$

i$.$ Is the heuristics specified in the problem $($shown below$)$ admissible? Justify your answer. If the heuristics is admissible, proceed to answer part $($ii$).$ If the heuristics is not admissible, correct it with a sensible value of your choice and proceed to answer part $($ii$).$

$(10\mathrm{.}0$ marks$)$

ii$.$ Perform the $A^{**}$ search to find the shortest path from the start state $(S)$ to the goal state $(G).$

$(20\mathrm{.}0$ marks$)$

Numbers in maroon are the heuristics for the respective nodes. Numbers in black are the weight $($estimated costs.$)$