$($a$)$ Search graph

$($b$)$ Soarch tree

Figure $2$: Search graph and search tree

Informed search algorithms $(8$ points$)$

Based on the search tree in Figure $2($b$),$ provide the trace to find a path from the start

node S to a goal node T for the following three informed search algorithms. The search

graph has been provided for your information as well in Figure $2($a$).$

The actual costs $g(x)$ have been annotated in black and the heuristic costs $h(x)$ have

been annotated in red.

For each algorithm, ensure that you use the correct metric $,$ or $f(x)).$

I would encourage to use green for the f $-$cost $f(x)$ as seen in class. Further, I would

suggest breaking down the steps where the elements are added$/$removed from the

queue and the queue is sorted.

When two nodes have the same value in the queue, use lexicographical ordering. For

example, consider a partial path SQR with value $4$ and a partial path $SU$ with value $4.$

Then SQR is then placed before SU in the queue as Q precedes $U.$

For beam search, when two nodes have the same value and some nodes must be

removed due to the WIDTH, consider the same lexicographical ordering.

a$.$ Optimal uniform cost search $(2$ points$)$

b$.$ Beam search with WIDTH $=2(2$ points$)$

c$.$ A$*{?}^{*}$ search $(4$ points$)$