This question is designed to test you on your understanding of the mechanics behind the various search algorithms wort For all parts of this question, consider the following state space, with action costs shown on the arcs and h(s) values shon by the states. G is the goal state in this space. For each of the following search algorithms, show the order in which the states will be tested for "goal," followed by the state-sequence of the solution path found by the algorithm. Your answers should be a simple string of capital letters like SBACDCEG. This is not an actual answer, just an example. If this answer was given for the order of the search, this means that the search first tested state S for being a goal, then tested state B for being a goal, then tested state A for being a goal, then tested C, then tested D, then tested C (this just means our search took us to C twice), then E, then finally G. The path for such a string like SBACDCEG might be SCEG, which means that the search algorithm found the path from state S to state C to state E to state G as the solution to the problem. Assume that we do not keep any memory of previously-seen states, and that states are generated in alphabetical order during an expansion after their parent is tested for being a goal. If we have any ties in choosing which state-node to test for goal (and then expand if not a goal), break the ties by picking the alphabetically first state. I'll do the breadth-first expansion and path just to show what I'm looking for. (2 pts for expansion, 2 points for path). BREADTH-FIRST: expansion: SABCBDCEECEBEG; path found: SBEG DEPTH-FIRST: expansion: ; path found: ITERATIVE-DEEPENING: expansion: ; path found: (remember to put the results from each iterative depth all together for the final answer!) UNIFORM-COST: expansion: ; path found: (remember to use the costs along the arcs connecting the states!) GREEDY-SEARCH: expansion: ; path found: (remember to use the h( ) function values!) A* SEARCH: expansion: ; path found: (remember to use the f(s)=h(s)+g(s) for each state!)