Figure $2$: Search graph and search tree

Informed search algorithms

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 two informed search algorithms. The search

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

The actual costs $a(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)$

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.

Find the Following

Beam search with WIDTH $=2$

A$*$ search

I need steps and explanations please, last time I asked the instructions did not make sense. As S has $3$ child nodes. Please explain how if used the total or heruistic costs, remember this is a trace to the goal node T$.$ Thank you so much, in advance these problems have been challenging to me$.$