首页 📔算法学习

题目传送门

最短Hamilton路径


内容引入

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

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


解题思路

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

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

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

在任意时刻还需要知道当前所处的位置,因此我们可以用$F[i,j](0 ≤ i ≤ 2 ^n, 0 ≤ j < n)$来表示点被经过的状态,对应的二进制数为i,且目前处于点j时的最短路径。

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

在任意时刻有:$F[i,j] = min \{ F[i \ xor \ (1 << j), k] + weight(k,j)\}​$,其中 $0 ≤ k < n​$ 。

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


代码实现

#include <bits/stdc++.h>
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;
}



文章评论

目录