Definition $1($Travelling Salesperson Problem$).$ Given a list of cities and the distances $($edges$)$ between each pair of cities $($nodes$),$

what is the optimal route that visits each city exactly once starting from city A and ending at any other city?

$\{A,H,G,F,J,C,D,E,B\}$

Personalize this homework for yourself:

Take the last $3$ digits of your $M$#$,$ and call is $a_{?}$ :

Find $N_1=(amod11)+4,$ which will be a number between $4$ and $14$ :

Find $N_2=(amod12)+1,$ which will be a number between $1$ and $12.$

For example: Let $a=257.$ Then $N_1=(257$mod$11)+4=4+4=8$ and $N_2=(257$mod$12)+1=5+1=6.$

Now update the above given citi$-$distances graph by setting the distance of $AB$ to be $N_1$ and the distance of $AH$ to be $N_2.$

Now, with your personalized graph of cities, answer the following questions: In the search tree, let frontier denote the list

that contains all the discovered but unexpanded nodes.

$(20$ pts$)$ Perform uniform$-$cost search for the above problem formulation. Show all the changes on frontier until a node

containing a four$-$city partial tour is pulled out of the list. Each entry in frontier contains the partial tour and its $g(x)$ value.

$(40pts)$ Perform $A^{**}$ search for the above problem formulation using $h_1(x)$ as the heuristic function.

$($a$)(15$ pts$)$ Show all the changes on frontier until a node containing a four$-$city partial tour is pulled out from the list.

Each entry in frontier contains the partial tour and its $f(x){}_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 nodethat contains a four$-$city partial tour is pulled out

from frointer to expand.

$(30pts)$ Perform $A^{**}$ search for the above problem formulation using $h_2(x)$ as the heuristic function.

$($a$)(15$ pts$)$ Show all the changes on frontier until a node containing a four$-$city partial tour is pulled out from the list.

Each entry in frontier contains the partial tour and its $f(x)g(x),h_2(x)$ values.

$($b$)(15$ pts$)$ Show the search tree of this time step.

$(10$ pts$)$ Are $h_1(x)$ and $h_2(x)$ admissible heuristic functions? Give precise and succinct reasons to justify your answers.