「Algorithm」状压DP解决Hamilton回路问题

算法

发布日期: 2021-10-01

文章字数: 2.1k

阅读时长: 8 分

序言

刚看到这个哈密顿回路的题时，第一感觉就是可以采用回溯法并通过 深度优先搜索(DFS) 解决，笔者初次就是使用这个方法并结合状态压缩AC了这道题。但是因为要使用递归，“翻译”成MIPS汇编代码的时候需要使用大量堆栈保存返回地址、函数参数、还有在调用过程中使用过的并希望保存的寄存器（笔者曾因为堆栈处理不当陷入了十分抓狂的境地）。

后来听翔宇哥哥说这个题可以采用 状压DP 的方法解决（xyggyyds！），于是笔者便开始~~面向百度和CSDN~~，最后终于用非递归的方法解决了这道题，于是便写了本篇文章分享一下心得。
***

为什么可以使用状压DP？

首先，本题满足DP算法的三个条件——

重复子问题
最优子结构
无后效性

在此就不具体展开，有兴趣的同学可以参考CSDN上这篇博客。如果暂时不想了解也可以跳过，相信不会影响对本题算法的理解。

其次，“状压”顾名思义就是“状态压缩”，也就是 “将一个阶段或集合的状态压缩到一个二进制整数，其中 0 和 1 分别表示两种不同的状态，从而达到节省储存空间和提高查找效率的作用。以本题为例，我们把图中每个顶点的状态压缩到二进制的位，用 1 表示该点被访问过，0 表示该点没有被访问过。于是，我们就可以用一个二进制正数表示 所有被访问过的点构成的集合S（以下简称“点集”）。例如，当S=39时，二进制表示为100111，说明此时编号为0、1、2、6的点在集合中。

既然状态压缩使用二进制数，那么必然和位运算脱不了干系。以下是常用的状态压缩操作和相应的位运算表示——

操作	位运算表示
取出整数n在二进制表示下的第k位	（n>>k）&1
取出整数n在二进制表示下的第0~k-1位（后k位）	n&((1<<k)-1)
取出整数n在二进制表示下的第k位取反	n^(1<<k)
取出整数n在二进制表示下的第k位赋值为1	n\|(1<<k)
取出整数n在二进制表示下的第k位赋值为0	n&(~(1<<k))

解题思路

为判断图中的是否存在 哈密顿回路，我们可以先判断是否存在 哈密顿路径（即沿着边访问每个顶点，每个顶点恰好访问一次），然后再判断 最后访问的点 和 最初访问的点 之间是否有通路即可。为方便判断，我们选取 0号点 为最初访问的点。

判断是否存在哈密顿路径（状压DP）

解决本题我们需要两个数组——

#define N 8
int edge[N][N];
int dp[N][N];

其中，edge 是储存无向图的邻接矩阵，edge[u][v] = 1 表示点v和点u之间有通路；dp 表示状态，以 dp[S][v] 为例，S 表示点集，即此时已经被访问的所有点的集合，v 表示该点集中最后一个被访问的点的序号。

例如，dp[39][2]表示 点集“100111”中最后被访问的点的序号是2。访问顺序可以是 "0->6->1->2"，也可以是 "0->1->6->2"。也就是说，dp[39][2] 之前的状态可以是 dp[35][6]（点集S为”100011“，最后访问的点是6号点），也可以是 dp[35][1]（点集S为”100011“，最后访问的点是1号点）

dp[S][v]的值只能是0和1。1 表示此时S中的点可以形成 哈密顿路径，而且该哈密顿路径的终点为 v；0 表示此时S中的点无法形成哈密顿路径。

因为我们默认最早访问的点为0号点，所以我们首先规定

dp[1][0] = 1;    //表示0号点第一个被访问

为找出状态转移方程，我们可以先从小问题入手分析：

Q：图中现在有4个点（标号为0，1，2，3），我们怎么判断存在哈密顿路径呢？
A：只需要求得 dp[0b1111][1] = 1 或者 dp[0b1111][2] = 1 或者 dp[ob1111][3] = 1 即可。
Q：那我们怎么求 dp[0b1111][1] 的值呢？？？（其他同理）
A：此时我们转移到上一个状态（点集S = ”1101“）。只需要0号点，2号点和3号点可以形成哈密顿路，并且其中至少有一个点（除了0号点）与1号点之间存在通路，即 "dp[0b1101][2] = 1 并且 edge[2][1] = 1" 或者 "dp[0b1101][3] = 1 并且 edge[3][1] = 1" ，那么 dp[0b1111][1] 的值就是1，否则为0。
Q：那我们怎么求 dp[0b1101][2] 的值呢？？？（其他同理）
A：我们再次转移到上一个状态（点集S = ”1001“）。只需要0号点与3号点之间有哈密顿路径，并且3号点和2号点之间有通路（因为0号点是初始点，所以没有必要判断0号点和2号点之间是否有通路），即 "dp[0b1001][3] = 1 并且 edge[3][2] = 1"，那么 dp[ob1101][2] 的值就是1，否则是0。
Q：我们怎么求 dp[0b1001][3] 的值呢？？？
A：呃……好像结束了，只需要判断 edge[0][3] 就行了。

经过以上的Q&A，你大概可以发现，每一个状态的计算都依赖他的上一个状态（即子过程）的值，状态转移方程可以写作

\(\mathsf{DP[S][v]=\bigcup_{i=1}^n \ (DP[S\_prev][u_i]} \ \ \&\ \ \mathsf{road[u_i][v])}\)

相信你已经对状态转移的具体过程有了大致的了解，那么我们结合下面的代码来进一步分析

for(S = 1; S < (1 << n); S++){
    for(v = 0; v < n; v++){
        if((S >> v) & 1){
            int S_prev = S ^ (1 << v);
            for(u = 0; u < n; u++){
                if((S_prev >> u) & 1) 
                    dp[S][v] | = (dp[S_prev][u] & edge[u][v]);
            }
        }
    }
}

在最外层的循环 for(S = 1; S < (1 << n); S++) 中，我们让 子集S 从 1 (0b00000001) 到 1<<8 (0b1111111) （假设n=8）进行遍历。因为表示子集状态的值S是从小到大变化的，所以可以保证当计算当前状态时，其子状态一定被计算过。

在第二层循环 for(v = 0; v < n; v++) 中，我们遍历所有的点，通过 (S >> v) & 1 来判断序号为 v 的点是否在点集 S 中，如果结果为1，我们便找出计算对象 dp[S][v]，并找出上一状态对应的点集 S_prev = S ^ (1 << v) ，然后进入第三层循环。

在第三层循环 for(u = 0; u < n; u++) 中，我们继续遍历所有点，找出可以作为上一状态终点的所有点的序号 u，进一步可以找出 dp[S_prev][u] 的值（因为 S_prev < S，因此之前必然计算过 dp[S_prev][u] 的值）。

最后我们让 dp[S][v] 或上 dp[S_prev][u] & edge[u][v] 即可。因为只要存在一个 u 使得 dp[S_prev][u] & edge[u][v] = 1，就说明 0号点到v号点之间有哈密顿路径（0号点到u号点之间存在哈密顿路径，u号点和v号点之间有通路）。

判断是否有哈密顿回路

经过上面的计算，我们已经得出点集"11111111"（假设点的个数n = 8）中存在的所有哈密顿路径，现在只要存在某个哈密顿路径的终点与0号点（起点）之间有通路即可。该过程仅需一个循环便可解决

for(int i = 0; i < n; i++){
    if(dp[(1<<n)-1][i] & edge[i][0]) {
        cout << "1" << endl;
        return 0;
    }
}
cout << "0" << endl;
return 0;