求哈密尔顿回路

顺便完成离散数学的实验二作业

问题描述

北京大学的小A 准备趁五一假期从北京出发，拜访以下几个大学的好友后返回北京:西安电子科技大学的B，兰州大学的C，武汉大学的D，浙江大学的E，深圳大学的F，同济大学的G，郑州大学的H，哈尔滨工程大学的I。综合考虑之后小A 同学选择飞机作为城市间的通行工具，但希望这趟旅行的总旅费最低请给小A 设计一个最佳城市旅游方案，并给出旅费预算是多少。(请自行查询城市之间飞机票价)

问题分析

问题建模

图论问题。简言之，就是有一个含V个端点，E条边的带权有向图，求从(0, 0)点经过每个端点后回到(0, 0)点所经过的边的总权重最小值。

这是经典的TSP(Traverling Salesman Problem)问题。

暴力求解

算法描述

利用C++的next_permutation()库函数，枚举出n-1的全排列，然后依次计算总权重，得出最小值及方案。

复杂度分析

对于初始点P1，有V-1种选择，对于第二个点P2，有V-2种选择，易得遍历所有的可能，复杂度为O(V-1)!。

状压dp

算法描述

参考自《挑战程序设计竞赛》p192

递推关系推导

假设现在已经访问过的顶点的集合为S，当前所在的顶点为v，用dp[S][v]表示从v出发访问剩余的所有顶点，最终回到顶点0的权重总和的最小值。可得以下递推式：

dp[V][0] = 0

上式表示，设已经访问过所有的V个顶点，最终回到了0点，权重总和为0

dp[S][v] = min{dp[S∪{u}][u] + d(v, u)|u∉S}

上式表示，dp[S][v]的状态由dp[S∪{u}][u]的状态转移过来。

由于最优子结构，在dp[S∪{u}][u]为最优时，dp[S][v]一定最优。

集合的整数表示

由于dp[S][v]的下标有一个为集合，我们需要把它编码为整数。

这里采用集合的整数表示方法。

下面简单介绍。

假设集合S内可能有n个元素，n1,n2,n3…nn，我们用0表示没这个元素，1表示有这个元素，那么S即可编码为一个整数，我们可以方便地对其进行集合的运算。

例如一个可能含5个元素的集合，若五个元素都有，S为31；若2，4元素没有，S为21。

我们可以用S >> i & 1来判断第i个元素是否属于集合S

有了集合的整数表示的知识，我们就可以把S作为数组的下标，同时S也是一个集合了。

复杂度分析

因为使用dp[S][v]来记忆化存储，S为含有V个元素的集合，所以遍历S有2V的复杂度，状态总共有V*2V种，每个状态都要枚举V次，选出最优，所以总的复杂度为O(V22V)。

性能分析

暴力求解复杂度为O(V-1)!，而状压dp复杂度为O(V22V)。

求解题目中的8个城市的问题复杂度为104数量级，但是求解100个城市的复杂度为1034数量级，按每秒千万次计算，需要4×1026年，不可能在有限时间内算完。

或许100个城市这样的数量级，需要的不是最优解，而是一个近似解。

记忆化搜索代码

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
55
56
57
58
59
60
61
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX_V = 15 + 1;
const int INF = 1e9 + 7;

int n, e;
int d[MAX_V][MAX_V];

int dp[1 << MAX_V][MAX_V];

int rec(int S, int v) {

    //如果访问过，直接返回结果
    if(dp[S][v] >= 0) {
        return dp[S][v];
    }

    //如果遍历过全部顶点且回到顶点0
    if(S == (1 << n) - 1 && v == 0) {
        return dp[S][v] = 0;
    }

    //从没访问过的顶点中选择一个顶点计算
    int res = INF;
    for(int u = 0; u < n; ++u) {
        if(!(S >> u & 1)) {
            res = min(res, rec(S | 1 << u, u) + d[v][u]);
        }
    }

    //把计算过的结果存到数组里
    return dp[S][v] = res;
}

void solve() {
    memset(dp, -1, sizeof(dp));
    printf("%d\n", rec(0, 0));
}

int main() {
    scanf("%d%d", &n, &e);

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            d[i][j] = INF;
        }
    }

    for(int i = 0; i < e; ++i) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        d[x][y] = w;
    }

    solve();
    return 0;
}

状压dp代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX_V = 15 + 1;
const int INF = 1e9 + 7;

int n, e;
int d[MAX_V][MAX_V];

int dp[1 << MAX_V][MAX_V];

void solve() {
    for(int S = 0; S < 1 << n; ++S) {
        fill(dp[S], dp[S] + n, INF);
    }
    dp[(1 << n) - 1][0] = 0;

    for(int S = (1 << n) - 2; S >= 0; --S) {
        for(int v = 0; v < n; ++v) {
            for(int u = 0; u < n; ++u) {
                if(!(S >> u & 1)) {
                    dp[S][v] = min(dp[S][v], dp[S | 1 << u][u] + d[v][u]);
                }
            }
        }
    }
    printf("%d\n", dp[0][0]);
}

int main() {
    scanf("%d%d", &n, &e);

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            d[i][j] = INF;
        }
    }

    for(int i = 0; i < e; ++i) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        d[x][y] = w;
    }

    solve();
    return 0;
}