状态压缩动态规划进阶——旅行商TSP问题

旅行商问题，即 TSP 问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访 n 个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP 是一道经典的 NP-完全问题，在规模比较小的时候可以用动态规划求解。

有 n n n个城市，两两之间均有道路直接相连。给出每个城市 i i i 和 j j j 之间的道路长度 d i s t ( i , j ) dist(i,j) dist(i,j)，求一条经过每个城市一次 且仅一次，最后回到起点的路线，使得经过的道路总长度最短。 n ≤ 16 n le16 n≤16，城市编号为 0 ∼ n − 1 0sim n-1 0∼n−1

将状压dp的状态dp[i][j]设为i是一个二进制数，如果当前这位为1，则这个编号对应的城市去过，否则没有去过，j表示最后到达的城市编号，为了方便起见，编号从0开始。
在读入城市距离的过程中，将无法到达的城市距离设为无穷大，这样就能保证在后续的min中不可能能考虑到该情况。
初始化时将dp数组中的每一位都设为无穷大，将dp[1][0]设为0，方便设置从1出发的情况。
第一层 s s s循环分别枚举0~(1< 其中有两个必须满足的条件

• 必须确保 i i i和 j j j都在 s s s当中
• 必须确保i不等于j，否则就是从一个城市到达它本身

s ( 1 < < i ) s^(1< 所以 d p [ s ( 1 < < i ) ] [ j ] + d i s t [ j ] [ i ] dp[s^(1< 所以动态转移方程就应该是
d p [ s ] [ i ] = m i n ( d p [ s ] [ i ] , d p [ s 1 < < i ] [ j ] + d i s t [ j ] [ i ] ) ; dp[s][i]=min(dp[s][i],dp[s^1< 示例代码

#include 
#include 
#include 
using namespace std;

const int INF = 0x3f3f3f3f;
int dist[20][20];
int dp[1 << 16][20];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
            if (dist[i][j] == -1) dist[i][j] = INF;
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    for (int s = 0; s < (1 << n); s++) {
        for(int i=0;i
            if(s&(1<
                for(int j=0;j
                    if(j!=i && (s&(1<
                        dp[s][i]=min(dp[s][i],dp[s^1<
        ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);
    }
    if (ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}