旅行商问题：求最短Hamilton路径

旅行商问题：求最短Hamilton路径

题目传送门

最短Hamilton路径

内容引入

总所周知，旅行商问题是一个NP完全问题，即没有一个合适的算法来解决它，只能用朴素算法(也就是通常所说的暴力算法)去进行优化。

Hamilton路径的定义：在一张图中，从点0到点n-1不重不漏的恰好经过每一个点一次的路径。

解题思路

我们很容易联想到朴素算法，即dfs枚举n个点的全排列，计算路径长度去最小值，这样时间复杂度为,如果n的个数过大，那么对于计算机，这也是一个无解问题。

因为n个点，每个点有两种情况，经过和暂时未经过，这样，就有种状态，我们可以使用二进制状态压缩DP来优化这个朴素算法，时间复杂度为，即状态数乘以状态转移复杂度得到。

我们可以使用一个n位二进制数来表示状态，若其第位为1，则表示第个点已经被经过，反之未被经过。

在任意时刻还需要知道当前所处的位置，因此我们可以用来表示点被经过的状态，对应的二进制数为i，且目前处于点j时的最短路径。

在起点时，有,即只经过了点0，目前处于起点0，最短路径长度为0，方便起见，我们将F数组的其余值都设成无穷大。

在任意时刻有：,其中 。

根据上述状态转移方程，我们可以写成下列代码。

代码实现

#include 
using namespace std;
int dp[1 << 20][20];
int weight[25][25];
int hamiton(int n)
{
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    for(int i = 1; i < 1 << n; ++i) 
        for(int j = 0; j < n; ++j)
            if(i >> j & 1)
                for(int k = 0; k < n; ++k) {
                    if(i >> k & 1) {
                        dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][k] + weight[k][j]);
                    }
                }
    return dp[(1 << n) - 1][n - 1];
}

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