1. Consider the following search problem represented as a graph. The start state is S and the goal states are G1 and G2. Note that the following questions variously reference both tree search and graph search. For questions that require a heuristic, use the one given in the figure. The number annotated on the arc represents the traversing cost. 0 2 S A B Heuristic C D 3 2 m GI G2 10 5 5 3 2 4 O O Answer the following questions. You must indicate which goal state is reached. In all cases, assume ties break based on alphabetical order. a) (3 points) What path will BFS tree search return? b) (3 points) What path will DFS tree search return? c) (3 points) What path will Uniform Cost Search (UCS) tree search return? d) (3 points) What path will UCS graph search' return? e) (5 points) For UCS graph search, write the ordered sequence of states put on the explored node list up to termination. Path Expanded Explored nodes Frontier (a priority queue ordered by path cost) S S S-A(3), S-B(7)