Consider the following graph. S is the start state and G is the goal state. Edges are

annotated with their cost.

For each of the following search strategies, give $(1)$ the solution path that will be returned, or write none if no path will be returned; $(2)$ the frontier list, and $(3)$ the explored$/$extended nodes in the order expanded. If there are ties, assume alphabetical tiebreaking $($i$.$e$.,$ nodes for states earlier in the alphabet are expanded first$).$

A$)$ BFS$$

Solution:

Frontier:

Explored:

B$)$ DFS

Solution:

Frontier:

Explored:

C$)$ IDS

Solution:

Frontier:

Explored:

D$)$ UCS

Solution:

Frontier:

Explored: