Question $2$

Search & Game Theory

$[16$ Marks$]$

Let $C$ be the cost of traversing an edge between nodes, and let $h$ be the heuristic estimate of a given node to the goal. Consider the graph below, where nodes are labelled with integers and directed edges are indicated by lines with arrows. Each edge is labelled with a cost $C,$ and each node with a heuristic value $h.$

Assume that we wish to search for the goal node $16$ starting at node $1$ using the A$*$ search algorithm. Further, assume that if there are ties in the priority queue, they are resolved by removing the node with the smallest label first $($e$.$g$.$ if two nodes $2$ and $1$ both have priority $10,$ then $1$ will be removed before $2).$

Given this, detail each step of the search algorithm. At each iteration, describe what node is popped from the queue and then what nodes are added to the queue subsequently $($and their corresponding priority$).$

$[4]$