Q$2)(35$ pts$)$ Consider the search space below, where $S$ is the start node and $G1,G2,$ and $G3$

satisfy the goal test. Ares are labeled with the cost of traversing them. Inside the boxes attached

to each node, heuristic values are shown.

For each of the following search strategies, indicate which goal state is reached $($if any$)$ and

list, in order, all the states expanded. When all else is equal, nodes should be expanded in

alphabetical order. Don't expand a node if already expanded. Show all your steps clearly.

a$)(11$ pts$)$ Uniform Cost Search

Goal state reached:

States expanded:

b$)(9$ pts$)$ Greedy Best First Search

Goal state reached

States expanded:

c$)$ pts$)A^{**}$ Search