Note: This is individual assignment, so collaboration is not allowed. Late submission is not acceptable.

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.

Note: This is individual assignment, so collaboration is not allowed. Late submission is not acceptable.

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.

Question $2[2\mathrm{.}5$ marks$]$

The "Moving Magic Puzzle" is played on a $33$ grid with each cell containing one of the digits $1$ to

The digit $9$ is the "movable digit". It can be moved in four possible directions $($up$,$ down, left,

or right$),$ and swapped with the digit in that direction.

The goal is to arrange the digits such that sum of every row, every column and each of the two

diagonals sums up to $15.$ The are many possible configurations that can satisfy the goal, wo of

which are shown below:

Starting with the initial state shown below, answer each of the following:

$($a$)$ Formulate this as a Search Problem.

$($b$)$ Complete the Search Tree shown below, generated by the Breadth$-$First Search $($BFS$)$ for this

problem, until a valid goal is reached.

Notes:

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

ii$.$ Apply the actions is the order Up $($U$),$ Down $($D$),$ Left $($L$)$ and then Right $($R$).$

iii. Label the states as $($a$),($b$),$ etc. in the order they are visited by the BFS$,$ based on the

ordering specified in $($ii$)$ above.