Consider the state space shown below, where S is the starting state and G is the goal state. Note that the graph is directed. Step costs are shown next to the edges in the graph. The table below shows, for each state, the estimated cost of the cheapest path from that state to the goal state.

$\backslash$table$[[$State$,\backslash$table$[[$Heuristic$],[$Value$]]],[$S$,3],[$A$,9],[B,1],[$C$,3],[$D$,4],[$E$,8],[$F$,1],[$G$,0]]$

For each of the $6$ search strategies below:

$(1)$ List, in order, the states on the solution path $($including the starting and goal states$).$ Please box this answer.

$(2)$ List, in order, the states popped off from the frontier $($including the starting and goal states$).$ Please box this answer.

$(3)$ In regards to showing work, please show the contents of frontier and explored after each step $($please see examples covered in lecture slides$).$

Please make sure to follow the algorithm definitions$/$pseudocode and tie$-$breaking strategies that we covered during lecture $($please see lecture slides$).$

Regarding iterative deepening search: Note that in iterative deepening search, the same state may be popped off multiple times from the frontier $($because this approach tries different depth limits until it finds the solution$).$ For example, if a state is popped off two times from the frontier, then it should appear twice in your final answer for the following question: "List, in order, the states popped off from the frontier $($including the starting and goal states$)."$

$($a$)$ Breadth First Search

$($b$)$ Depth First Search

$($c$)$ Iterative Deepening Search

$($d$)$ Uniform Cost Search

$($e$)$ Greedy Best$-$First Search

$($f$)$ A$*$ Search