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