Question $1.$ Consider the search chart shown at right. S is the starting node and G is the target node.

The edges are explained with their costs. Additionally, three different heuristic function values for

each node are given in a table: h$1,$ h$2$ and h$3.$

For each of the following search strategies, $(1)$ write a path if there is one. $(2)$ Write the nodes added

to the graph. $(3)$ If there are expanded nodes, write them in order.

$($a$)[6]$ Depth$-$first search

$($a$1)($a$2)($a$3)$

$($b$)[6]$ Breadth$-$first search

$($b$1)($b$2)($b$3)$

$($c$)[6]$ A$*$ algorithm using h$1$ heuristic function

$($c$1)($c$2)($c$3)$

$($d$)[6]$ A$*$ algorithm using h$2$ heuristic function

$($d$1)($d$2)($d$3)$

$($e$)[6]$ A$*$ algorithm using h$3$ heuristic function

$($e$1)($e$2)($e$3)$

$($f$)[3]$ Is the heuristic function h$1$ admissible?

$($g$)[3]$ Is the heuristic function h$2$ admissible?

$($h$)[3]$ Is the heuristic function h$2$ admissible?