schtonn

schtonn

0%

哈密尔顿回路

Posted on Edited on Valine:

前置知识

图论，动态规划，二进制基础知识。

引入

我们都知道欧拉回路，也就是经过每条边正好一遍的路径。

哈密尔顿回路和欧拉回路很像，但是需要经过每个点正好一遍。

欧拉回路有稳定的解法，然而哈密尔顿回路是 NPC 的，没有多项式时间解法。

我们使用动态规划来解决哈密尔顿回路问题。

思路

想要解决回路的问题，首先要解决路径的问题。若有图 \(G(n,m)\)，需要找出图中的一条哈密尔顿路径。

对于一条长度大于一的哈密尔顿路径，它一定是由一个更短的路径和一条连通边走过来的，所以我们定义数组 F，F[{S}][p] 表示经过了集合 \(S\) 中的所有点，最后到达点 t 有没有路径。

如果 F[{s}][p] 为真，那么一定有 F[{s}-p][q] 为真且 \(q\rightarrow p\) 有边，也就是有一个没有 p 的成立集合，并且最终能加入 p。

初始值设为，对于图中每一个点 i，F[{i}][i]=true。最终寻找：\(\vee^i_{i\in n} F[\{n\}][i]\)（经过所有点，最终到达任意一点）。

此时我们就得到了状态转移方程：

\[F[\{S\}][p](p\in S)=\sum^q_{q\in S}F[\{S\}-p][q]\cdot Edge[q][p]\]

通过枚举 S，q 和 p，就可以求出哈密尔顿路径了。

状态压缩

此时，聪明的小朋友就会问了：你一个数组的下标怎么表示集合？

这时就要请出我们的大法师：状态压缩了。我们把本应是集合的数据压缩成一个下标。

运用二进制，把在集合中的点标记为一，不在集合中的标记为零，这样集合就转成下标了。

比如一共有三个点，其中点一，点二在集合中，那么我们就用 \((011)_2\) 来表示。简直聪明至极！

作为一个n个点的图，S 可以以十进制顺序枚举，从 \((00\cdots 0)_2\) 到 \((11\cdots 1)_2\)，这样确保了前置条件是完整的。内里嵌套两层循环枚举 q 和 p。

作为二进制，当然要有专门用在二进制上的操作。

按位操作

有几种不同的按位二进制操作：

  1. 按位与

    符号：&

    两个都是一就得一，否则得零。

    \((01011101)_2\&(10101011)_2=(00001001)_2\)

  2. 按位或

    符号：|

    只要有一就得一，否则得零。

    \((01000101)_2|(10001011)_2=(11001111)_2\)

  3. 按位异或

    符号：^

    两个不同就得一，否则得零。

    注意和幂区分。

    （\(\LaTeX\)中打不出来这个符号，用另一个符号代替。）

    \((11011010)_2\oplus(10101010)_2=(01110000)_2\)

  4. 左移，右移

    符号：<<和>>

    顾名思义，就是把二进制位移动。边界用0代替。

    \((10101010)_2<<3=(01010000)_2\)

高级操作

  1. 如果我们要判断集合S中第i位是不是1，那就用这个：S&(1<<(i-1))。

  2. 将集合S中已知为1的第i位变为0：S^(1<<(i-1))。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
for(int s=1;s<(1<<n);++s){
    for(int p=1;p<=n;++p){
        if(s&(1<<(p-1))==0)continue;//判断p是否为S中元素
        for(int q=1;q<=n;++q){
            if(s&(1<<(q-1))==0)continue;//判断q是否为S中元素
            if(!e[q][p])continue;//判断有没有q到p的边
            if(dp[s^(1<<(p-1))][q]){//判断dp[{s}-p][q]是否为真
                dp[s][p]=true;
            }
        }
    }
}

扩展

记录

有些题目要求输出哈密尔顿路径。其实并不难，根本上只需要加上这一句：g[s][p]=q;，通过g数组记录路径。

回路

对于哈密尔顿回路，有一个方法是让路径只允许从点1开始，最后看能不能走回点1，也就是初始值设为 F[{1}][1]=true，最终判定 \(F[\{n\}][i]\)。

代码

输出回路的完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include "bits/stdc++.h"
using namespace std;
const int N=1<<20;
int n,m,e[25][25];
bool dp[N][25];//dp[i][j]表示状态为i，最后到达j点有没有路径
int g[N][25];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        e[u][v]=true;
    }
    dp[1][1]=true;
    for(int s=1;s<(1<<n);++s){
        for(int p=1;p<=n;++p){
            if(s&(1<<(p-1))==0)continue;//判断p是否为S中元素
            for(int q=1;q<=n;++q){
                if(s&(1<<(q-1))==0)continue;//判断q是否为S中元素
                if(!e[q][p])continue;//判断有没有q到p的边
                if(dp[s^(1<<(p-1))][q]){//判断dp[{s}-p][q]是否为真
                    dp[s][p]=true;
                    g[s][p]=q;
                }
            }
        }
    }
    int s=(1<<n)-1;
    bool flag=0;
    stack<int>output;
    for(int i=1;i<=n;i++){
        if(dp[s][i]&&e[i][1]){
            int p=i;
            output.push(p);
            do{
                output.push(g[s][p]);
                int t=p;
                p=g[s][p];
                s-=(1<<(t-1));
            }while(s!=1);
					flag=1;
            break;
        }
    }
	if(!flag){
		cout<<"No Answer"<<endl;
		return 0;
	}
    while(!output.empty()){
        cout<<output.top()<<' ';
        output.pop();
    }
    return 0;
}