$(8$ marks$).$

Graph Search Problem $2$

Consider the graph shown below where the numbers on the links are link costs and the

numbers next to the states are heuristic estimates. Note that the arcs are undirected. Let $A$

be the start state and $G$ be the goal state.

Simulate $A^{**}$ search with a strict expanded list on this graph. At each step, show the path to

the state of the node that's being expanded, the length of that path, the total estimated cost

of the path $($actual $+$ heuristic$),$ and the current value of the expanded list $($as a list of states$).$

You are welcome to use scratch paper or the back of the exam pages to simulate the search.

However, please transcribe $($only$)$ the information requested into the table given below.

Expanded List $-$ is a collection of nodes in a graph that have been fully explored during the

search process.