There is no need to write codes to solve these problems. We can just solve problems by logical reasoning and mathematical caculating.

We are given the state space graph of a search problem below. The node S corresponds to the initial state, and the nodes labeled G1 and G2 correspond to possible goal states. Action costs are shown along the edges. 1. (6 pts) By inspection, list all state sequences starting at S and ending in a goal state, along with their total costs. Which sequence is cost-optimal? 2. (12 pts) Consider running each of the following search algorithms on this graph, all using a reached table and "late" goal test: depth-first search, breadth-first search, and uniform-cost search. If they occur, ties are broken according to alphabetical order. For each method, list a) the sequence of nodes that are expanded (not including the goal), and b) the sequence of nodes returned as the solution. 3. (6 pts) Suppose a heuristic function is assigned such that h(n) is the length of the shortest path between n and the closest goal. Thus, each goal node has h(n)=0, their parents have h(n)=1, and so on. A node that has no path to a goal has h(n)=. Briefly explain why h is guaranteed to be admissible and consistent on this graph. Propose a simple change to one or more of the action costs that would make h inadmissible. 4. (6 pts) Consider running A search using the heuristic function defined above. List a) the sequence of nodes that are expanded and their g,h and f values at time of expansion, b) the sequence of nodes returned as the solution, and c) the nodes and their g,h, and f values that are still in the frontier when the search concludes