7. [10 pts] Consider the following route-finding problem: Let S be the initial state and G be the goal state. The cost of each action is as indicated.

(a) [6 pts] Consider uniform-cost search implemented with graph-search. Give a trace of uniform-cost search, by showing the nodes in frontier and explored set at each iteration of the main loop.

(b) [4 pts] When A generates G which is a goal state with a path cost of 11, why doesnt the algorithm halt and return the search result now that the goal has been found? With your observation, discuss how uniform-cost search ensures that the shortest path solution is selected.

A 10 15 G 5 B