Problem 1 In the following tree, the numbers on the arrows represent the individual action costs. The root state is A and the Goal state is G. Note that that the nodes denoted by G. G2, G refer to the same goal state. We chose this notation to simplify writing the answers a) Write down the sequence of nodes expanded by each of the following search algorithms until it expands a Goal state. For example, if you expand Athen B then your answer should be something like: ABC-G - (Use alphabetical order to break ties) Expansion sequence Search Algorithm Breadth first (BFS) Depth first (DFS) Uniform cost (UCS) b) Write the search solution found by each algorithm (it should be something like A G). Also, write the total cost of the solution and indicate if it is optimal with respect to the total cost or not Algorithm Search solution Total Optimal? (yes or cost no) BFS DFS UCS For USC, write all the steps of the tree search process until reaching the Goal state. USC expansion steps A AB