Perform A$$ search for the above problem formulation using h$1($x$)$

as the heuristic function.

$($a$)(15$ pts$)$ Show all the changes on f rontier until a node containing

a four$-$city partial tour is pulled out from the list. Each entry in

f rontier contains the partial tour and its f $($x$),$ g$($x$),$ h$1($x$)$ values.

$($b$)(10$ pts$)$ Only for the two states $\{$AB$\}$ and $\{$AH$\},$ show the subgraphs

and its MCSTs$.$

$($c$)(15$ pts$)$ Show the search tree of this time step, i$.$e$.,$ when a first node

that contains a four$-$city partial tour is pulled out from f rointer to

expand.