Search algorithm is an important technique in planning an optimal solution. There are two search technique representation, i$.$e$.$ a search tree and a search graph. Figure $1$ shows a search representation with the start node denoted as $\backslash ($ S $\backslash )$ while the goal node denoted as $\backslash ($ G $\backslash ).$ The heuristic functions are labelled within the nodes while the actual cost functions are labelled on the edges.

a$)$ State the differences between a search tree and a search graph.

$(4$ marks$)$

b$)$ Identify if the search representation in Figure $1$ is a search tree or a search graph? Justify your answer.

$(2$ marks$)$

c$)$ Provide the solutions for the following search algorithms:

i$.$ Breadth First Search

$(3$ marks$)$

ii$.$ Depth First Search

$(3$ marks$)$

iii. Uniform Cost Search

$(3$ marks$)$

iv$.$ Greedy Search $($Best First Search$)$

$(3$ marks$)$

v$.\backslash ($ A$^\{*\}\backslash )$ Search

$(3$ marks$)$

Revision

Page $2$ of $\backslash (\backslash$mathbf$\{8\}\backslash )$

Give your solution in the form of example as follows:

Returned path: $\text{'}$S $-$ N$2-$ G$.\text{'}$

Path cost: $10$

Nodes expended: $10$

d$)$ Compare the strategies in Question $2$c$.$ Comment on their performances based on the completeness, optimality, time and space complexities.

$(4$ marks$)$