Q$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)($e$1)$

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

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

$($c$)[6]A^{**}$ algorithm using $h1$ heuristic function

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

$($d$)[6]A^{**}$ algorithm using $h2$ heuristic function

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

$($e$)[7]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?