Qn$7(20$ points, $5$ points each$)$ Consider the search graph below, where $S$ is the start state. Let us assume in this case

that we have three goals instead of one: G$1,$ G$2,$ and G$3.$ Searching with multiple goals is similar to searching with a

single goal. The only difference is that the algorithm stops when any of the goal states is reached. The edges are

labeled with the cost of moving from one state to another and the heuristic cost to any of the goals is reported inside

the node.

Assuming that successor states are generated in alphabetical order. For each of the following search strategies, show

in detail $($similar to what we did in class$)$ how the search proceeds, and which of the $3$ goal state is reached $($if any$).$

Make sure to list in order all the states visited during the search. Please use the state's name $($A before B$,...)$ to break

any ties during informed traversal. Please note the answers to questions using BFS are provided for your reference

a$.$ Breadth$-$first search.

b$.$ Depth$-$first search.

c$.$ Iterative deepening search $($depth $=3)$

d$.$ Best$-$first search $($Greedy search using $f=h)$

e$.A^{**}$ search $($using $f=g+h)$