题目链接

算法竞赛进阶指南-3.最短Hamilton路径

汉密尔顿路径是一道旅行商问题，已被证明是NP-Hard问题，无法在多项式级别的复杂度求出。

如果用暴力来做，首先要枚举所有路径，${0，n - 1}$ 相当于求n个点的全排列，即$n!$，
然后枚举完之后要遍历一次，求整体的路径长度， 即 ${O(n! * n)}$，这个时间复杂度太高了。

Method : 状态压缩DP

不难发现状态是比较多的，但对于每一个节点，都只关心0(未访问)和1(已访问)这两种状态。

因此可以考虑用一个N位2进制数来表示状态集合，用$[0, 2 ^N - 1]$之间的一个十进制数形式表示DP状态的其中一维。

状态表示 ：所有从0走到j，走过的所有点的情况是i的所有路径， 求min。

状态划分 ：枚举上一个状态，即0->·····–>k–>j中k的所有可能情况。

状态转移：枚举走到j点前的一个状态=>[i - (1 << j)能把 i的第 j位 置为0]

上一个状态中的所处的位置，可能是 i - (1 << j)中任意一个是1的数位k,从k到j需要花费g[k][j]

因此 f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j])

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;
const int M = 1 << N; // int一共32位

//无向图
int g[N][N];

//状态
int f[M][N];

int n;

int main() {
    cin >> n;
    
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            scanf("%d", &g[i][j]);
        }
    }
    
    // 起点0 => 二进制表示: 00...01
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    
    for (int i = 0; i < 1 << n; i ++) {
        for (int j = 0; j < n; j ++) {
            // 如果i的第j位是1，说明j点可达
            if (i >> j & 1) {
                // 枚举走到j点前的一个状态,以k为终点的最短距离
                for (int k = 0; k < n; k ++) {
                    // i - (1 << j)为走到j点的前一个状态,k是前一个状态中的可达点
                    if (i - (1 << j) >> k & 1) {
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j]);
                    }
                }                
            }
        }
    }
    
    cout << f[(1 << n) - 1][n - 1] << endl;

    return 0;
}

复杂度分析

• 时间复杂度${O(2^n * n^2)}$，其中$2^n$为二进制状态压缩(i层循环)，${n^2}$为枚举j层和枚举k层的两重循环。

• 空间复杂度${O(n^2)}$，用于存储图g[N][N]。