Problem $1.$ Search. $(16$ points$)$

States, and directed edges are operators $($valid moves$)$ in between the states. The start state

is s

is S$,$ and the goal state is G $.$ There ore costs associated with the edges. The heuristic estimate, h$,$

first alphat the ties $($equivalent choices$)$ are always broken by choosing the state which comes

before the nodically. Also assume we always check for the state repeats and eliminate them

ansion. Please answer the following questions.

Part a$.(4$ points$)$ Give the order in which the depth$-$first search $($DFS$)$ expands the states. Stop

when the goal state is reached. Note: DFS ignores the costs.

S$->$A$->$B$->$D$->$F$->$G$.,$V

Part b$.(4$ points$)$ Give the order in which breadth first search expands the states. You may

assume the algorithm checks for the state repeats. Note: BFS ignores the costs.

S$->$B$->$E$->$G$*$x$,-4$

Part c$.(4$ points$)$ Give the order in which the states are expanded using the uniform cost

search.

Part d$.(4$ points$)$ Give the order in which states are expanded using the A$^(*)$ search.