五味子

小舟从此逝,江海寄余生

0%

求哈密尔顿回路

求哈密尔顿回路

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

问题描述

北京大学的小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个城市这样的数量级,需要的不是最优解,而是一个近似解。