Question $1$

$[7\mathrm{.}5$ marks$]$

In the graph shown below, $S$ is the starting node and $G$ is the goal node. The value on each edge

represents the cost of traversing the edge. The value on each node represents the heuristic estimate

of the cost from the node to the goal.

Using a table similar to the one shown below, trance the execution of each of the following

searching techniques until the goal is reached. At the end of the search, state the path found

and the cost of the path.

$($a$)$ Breadth$-$First Search $($BFS$)$

$($b$)$ Depth$-$First Search $($DFS$)$

$($c$)$ Uniform Cost Search $($UCS$)$

$($d$)$ Greedy Best$-$First Search

$($e$)$ A$*$ Search

Notes:

Use the graph version of the algorithm $($in which a node is explored only once$).$

Use alphabetical ordering to resolve any tie.