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.$)$