62 The Travelling Salesman Problem

Problem Definition

• Given a set $C$ of $n$ cities $c_1,c_2,\cdots ,c_n$
• A distance function $dist:C\times C\to {\mathbb{R}}^{\ge 0}$ which gives the distance between every pair of cities
• We want to start at $c_1$ and finish at $c_1$ after visiting all cities on the way
• Question is which order should we choose to visit the cities to minimise the total distance traveled.

Brute Force algorithm

• Tries all possible $n!$ orders
• Given an ordering of the cities, we can compute its cost by adding $n$ values.
• Hence, running time of the algorithm is $n!$ which is roughly $(\frac{n}{e}{)}^n$
• Can we do better, say $2^n\cdot n^{O(1)}$?

Setting up the recurrence for dynamic programming:

• For each $S\subseteq \{c_1,c_2,\cdots ,c_n\}$ and each $c_i\in S$ let $\mathrm{OPT}[S,c_i]$ be the minimum length of a tour that
  • Starts at $c_1$
  • visits all cities in $S$
  • ends at $c_i$
• Base case is when $|S|=1$
  • For each $i\ge 2$, we have $\mathrm{OPT}[\{c_i\},c_i]=\mathrm{dist}(c_1,c_i)$
• Now suppose $|S|>1$ and we want to compute $\mathrm{OPT}[S,c_i]$ for some $c_i\in S$
  • That is, we want to compute a minimum length of tour which starts at $c_1$, visits all cities in $S$ and ends at $c_1$
  • Let $c_j$ be the last city visited on this tour before ending at $c_i$
  • We don’t know $c_j$, but it must be a city from $S\setminus c_i$
  • So we guess all possibilities for $c_j$ which gives the following recurrence:

$$\mathrm{OPT}[S,c_i]=\underset{c_j\in (S\setminus \{c_i\})}{\min }\mathrm{OPT}[S\setminus \{c_i\}]+\mathrm{dist}(c_j,c_i)$$

Algorithm

$$\begin{array}{rl}\text{Algorithm }\mathrm{TSP}& \\ \text{Input: }& C=\{c_1,c_2,\dots ,c_n\}\text{ and a distance function }\mathrm{dist}:C\times C\to {\mathbb{R}}^{\ge 0}\\ \text{Output: }& \text{Minimum tour distance starting and ending at }{c}_1\\ & \text{while visiting every city in }C\\ & \text{for }i=2\text{ to }n\text{ do}\\ & \mathrm{OPT}[\{c_i\},c_i]=\mathrm{dist}(c_1,c_i)\\ & \text{end for}\\ & \text{for }k=2\text{ to }n\text{ do}\\ & \text{for }S\subseteq \{c_2,c_3,\dots ,c_n\}\text{ with }|S|=k\text{ do}\\ & \mathrm{OPT}[S,c_i]=\underset{c_j\in (S\setminus \{c_i\})}{\min }(\mathrm{OPT}[S\setminus \{c_i\},c_j]+\mathrm{dist}(c_j,c_i))\\ & \text{end for}\\ & \text{Increase }k\text{ by one}\\ & \text{end for}\\ & \text{return }\underset{2\le i\le n}{\min }(\mathrm{OPT}[\{c_2,c_3,\dots ,c_n\},c_i]+\mathrm{dist}(c_i,c_1))\end{array}$$

Analysis of Runtime

• Number of entries in the dynamic programming table is $O(2^n\cdot n)$
  • We maintain an entry $\mathrm{OPT}[S,c_i]$, for each $S\subseteq \{c_1,c_2,\cdots ,c_n\}$ and each $c_i\in S$
• To compute $\mathrm{OPT}[S,c_i]$, we take min over $|S|$ numbers, look up $|S|-1$ entries and do $|S|-1$ additions
  • Overall time is $O(n)$ since $|S|\le n-1$