Q$1)(30$ pts$)$ Consider the search tree below where $A$ is the start state and $G$ is the goal state.

For each of the following search strategies, indicate the path found to reach to the goal state,

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

alphabetical order. DO NOT keep a visited$/$expanded list to keep track of the repeated states.

$($No partial points will be given in the case of missing$/$extra states or wrong orders, so please

be careful.$)$

$($a$)(8$ pts$)$ Breadth First Search

Path found:

States expanded:

$($b$)(6$ pts$)$ Depth First Search

Path found:

States expanded:

$($c$)(16$ pts$)$ Iterative Deepening Search

Path found:

States expanded