Problem 1 (60 Points)

The Traveling Salesman Problem. Suppose there are $N+1$ cities $V_0$, $V_1$,$\cdots$,$V_N$ on the map. We are given a symmetric $(N+1) \times (N+1)$ matrix $D$ with positive off-diagonal entries representing the travel cost. Imagine a salesman living in city $V_0$, needing to visit the other $N$ cities once and then to return home. We write $x=(x_0, x_1, x_2, \cdots, x_N, x_{N+1})$ for a possible tour with $x_0=x_{N+1}=V_0$ and $(x_1,x_2,\cdots, x_N)$ is a permutation of $\{V_1, V_2, \cdots, V_N\}$. Clearly, the cost of tour $x$ is

$$f(x) = \sum_{i=0}^{N} D_{x_i,x_{i+1}}$$ (1)

We also write $E$ for all possible tours. In this problem, we will design some numerical algorithm to find the tour with least travel cost. First, let's consider the following four transition matrix $Q$ on the space $E$ of possible tours.

1. $Q^{(1)}$: Choose uniformly $i \in [1,N]$, $j \in [1,N]$ with $i \ne j$ and swap $x_i$ and $x_j$ to get new $x'$, i.e.,
   $$x'=(x_0,x_1,\cdots,x_{i-1},x_j,x_{i+1},\cdots,x_{j-1},x_{i},x_{j+1}, \cdots, x_N,x_{N+1})$$

2. $Q^{(2)}$: Choose uniformly $i \in [1,N-1]$ and swap $x_i$ and $x_{i+1}$ to get new $x'$, i.e.,
   $$x'=(x_0,x_1,\cdots,x_{i-1},x_{i+1},x_i,x_{i+2},\cdots, x_N,x_{N+1})$$

3. $Q^{(3)}$: Choose uniformly $i \in [1,N]$, $j \in [1,N]$ with $i \ne j$ and revers cities between $x_i$ and $x_j$, i.e.,
   $$x'=(x_0,x_1,\cdots,x_{i-1},x_j,x_{j-1}, \cdots, x_{i+1}, x_{i}, x_{j+1}, \cdots, x_N,x_{N+1})$$

4. $Q^{(4)}$: Choose uniformly $i \in [1,N]$, choose uniformly $y \in [0,N]$ with $j\ne i$ and $j\ne i-1$ and put $x_i$ right after $x_j$, i.e.,
   $$x'=(x_0,x_1,\cdots, x_{i-1},x_{i+1},\cdots, x_j,x_i,x_{j+1}, \cdots, x_N, x_{N+1})$$

Questions:

1. (5 Points) Illustrate these four schemes graphically with 5 cities, i.e., draw the effect of the transformation for an instance of trajectory.
2. (5 Points) Which of four transition matrices is irreducible?
3. (10 Points) Which of four transition matrices is reversible? with respect to what distribution?
4. (10 Points) Define distribution $\pi_T$ on $E$ as

   $$\pi_T(x)=\frac{1}{Z}\exp^{-\frac{f(x)}{T}}$$ (2)

   
   
   where $T$ is a positive constant and $Z=\sum_{x \in E} \exp^{-\frac{f(x)}{T}}$ for normalization. Describe how you would approximately smaple from the the distribution $\pi_T$ on $E$.
5. (5 Points) What happens when T goes to 0? What happens when T goes to $+\infty$?
6. (10 Points) According to the previous result, describe a method to find the best tour.
7. (15 Points) Bonus question. Implement your method for 30 cities randomly (uniformly, independently) distributed in $[0,1]^2$.