最短哈密尔顿路径c++

哈密尔顿路径是指包含图中所有节点的路径。最短哈密尔顿路径是指长度最短的哈密尔顿路径。这是一个NP难问题，因此没有已知的多项式时间算法可以解决这个问题。以下是一个朴素的暴力搜索算法，它可以找到最短哈密尔顿路径。

#include <bits/stdc++.h>
using namespace std;

const int N = 18; // 节点数
const int INF = 0x3f3f3f3f;

int n;
int g[N][N]; // 带权邻接矩阵
int dp[1 << N][N]; // dp 状态

int solve() {
    memset(dp, INF, sizeof(dp));
    dp[1][0] = 0;
    for (int S = 1; S < (1 << n); ++S) {
        for (int i = 0; i < n; ++i) {
            if (!(S & (1 << i))) continue;
            for (int j = 0; j < n; ++j) {
                if (!(S & (1 << j))) continue;
                dp[S][i] = min(dp[S][i], dp[S ^ (1 << i)][j] + g[j][i]);
            }
        }
    }
    return dp[(1 << n) - 1][0];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
        }
    }
    cout << solve() << endl;
    return 0;
}

复杂度是 $O(n^22^n)$，可以通过 $n=18$ 的数据。