Q$4$:The graph below represents the search space of a problem. Nodes are labeled with a

letter and the value of a heuristic function $h$ for the node. Edges are labeled with the cost of

traversing the edge

$(20$ points$)$

Q$-$A: Suppose we want to use the Uniform$-$Cost algorithm on the graph to find the shortest path from node

S to node $G.$

Simulate running the Uniform$-$Cost algorithm on the graph, trace the algorithm step by step. $(5)$

For the solution found by Uniform$-$Cost, give the cost and sequence of nodes comprising the path.

$(5)$

Q$-$B: Suppose we want to use the A$*$ algorithm on the graph to find the shortest path from node S to node

G$.$

Simulate running the $A^{**}$ algorithm on the graph, trace the algorithm step by step. $(5)$

For the solution found by the $A^{**},$ give the cost and sequence of nodes comprising the path. $(5)$