Problem

• Input: number of cites, number of roads, a sequence of roads

• Output: Minimum cost of travelling through all the cities.

Naive: Exhaustive Search

All permutation of cities.

• Time complexity:
  $O(n!)$, where
  $n$ is the number of cities.

Dynamic Programming

$f(s,C):$ the minimum cost to extend a path, which passes all cities in

$C$ and ends at

$s$.

Answer:

$f(1,\{c_1\})$ (if we started at city 1)

$f(s,C)=\{\begin{array}{ll}{w}_{s,1},& \text{if }C=\{c_1,\dots ,c_n\}\\ \underset{t\notin C}{min}\{f(t,C\cup \{t\})+w_{s,t}\},& \text{otherwise}\end{array}$

• Time complexity:
  $O(n^2\cdot 2^n)$

Implementation

int n;
vector<vector<int>> w;
vector<vector<int>> dp; // n * (1 << n)

int travelling_salesperson(int s, int C) {
    if (dp[s][C] != -1) return dp[s][C]
    if (C == (1 << n) - 1) return dp[s][C] = w[s][0];
    
    int ans = 0x3fffffff;
    for (int t = 1; t < n; ++t) {
        if (C & (1 << t)) continue;
        ans = min(ans, TSP(t, C | (1 << t)) + w[s][t]);
    }
    return dp[s][C] = ans;
}

// answer: TSP(0, 1)