求哈密尔顿回路
顺便完成离散数学的实验二作业
问题描述
北京大学的小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];
}
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;
}
|