---
tags: Dynamic Programming
title: Travelling Salesperson Problem
---

## 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{cases}
w_{s,1}, &\text{if }C=\{c_1,\dots,c_n\} \\
\min\limits_{t\notin C}\{f(t, C~\cup~\{t\})+w_{s,t}\}, &\text{otherwise}
\end{cases}$

* Time complexity: $O(n^2\cdot2^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)