TSP问题分析动态规划-分支界限法-蛮力法

1、算法综合实验报告学 号： 1004111115 姓 名： 李宏强 一、实验内容：分别用动态规划、贪心及分支限界法实现对TSP问题（无向图）的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。二、程序设计的基本思想、原理和算法描述：（包括程序的数据结构、函数组成、输入/输出设计、符号名说明等）1、 动态规划法(1)数据结构：利用二进制来表示集合，则集合S可由一个十进制数x相对应，此x所对应的二进制数为y，如果y的第k位为1，则表示k存在集合S中。例如：集合S=0，1（其子集合为0101），我们用二进制数11（所对应十进制数为3）表示S，11中右手边第1个数为1表示0在集合S中

2、，右手边第二个数为1表示1在集合S中，其他位为0表示其它数字不在集合S中；同理,集合S=0,2（其子集合为0202可用二进制数101（所对应十进制数为5）表示（右手边第1个数为1表示0在集合S中，右手边第二个数为0表示1不在集合S中，右手边第3个数为1表示2在集合S中，则说明0，2在集合中，1不在集合中。利用邻接矩阵表示任意两点之间的距离例如：mpij表示点i，j两点之间的距离。(2) 函数组成输入函数in()利用动态规划法算法实现的求解函数solve()主函数main()(3)输入/输出设计本程序可以通过键盘进行输入、屏幕进行输出。（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输

3、出到文件等其它方式）这里采用随机产生输入数据，将数据输出在屏幕上的方式。(4) 符号名说明 n 表示顶点个数。 mpij 表示顶点i和顶点j之间的距离。 dpij 表示顶点i经过集合S(用二进制表示的数为j)后回到起始点的最短路径和。(5) 算法描述某一个点i不经过任意点回到起始点的最短路径和为mpi0(默认初始点为0)dpi0 = mpi0; (1<=i<n)点i经过集合S（二进制表示的数为j）的最短路径和为从点i经过集合S中的某一点k后再从该点出发，经过集合S-k的最小值。dpij=minmpik+dpkj-(1<<(k-1);2、 贪心法(1) 数据结构利用邻接矩

4、阵表示任意两点之间的距离例如：mpij表示点i，j两点之间的距离。(2) 函数组成输入函数in()利用贪心法每次取最近距离的函数dfs(u，k，l),u表示当前在顶点u，k表示已经走过了k个点，l表示所经过的路径和。主函数main()(3)输入/输出设计本程序可以通过键盘进行输入、屏幕进行输出。（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式）这里采用随机产生输入数据，将数据输出在屏幕上的方式。(4) 符号名说明 n 表示顶点个数。 mpij 表示顶点i和顶点j之间的距离。 inqi 表示顶点i已经走过了。(5) 算法描述如果当前在顶点u，则取与顶点u距离最近的点

5、p。dfs(u,k,l)=dfs(p,k+1,l+mpup)3、 分支限界法(1) 数据结构利用邻接矩阵表示任意两点之间的距离例如：mpij表示点i，j两点之间的距离。结构体struct node int visp22;/标记哪些点走了 int st;/起点 int ed;/终点 int k;/走过的点数 int sumv;/经过路径的距离 int lb;/目标函数的值 bool operator <(const node &p )const return lb>p.lb; ;优先级队列priority_queue<node> q;(2) 函数组成in()输入函

6、数。dfs(int u，int k，int l)利用贪心法每次取最近距离的函数,u表示当前在顶点u，k表示已经走过了k个点，l表示所经过的路径和。将贪心法的解作为上界的初始值。get_lb( node p)求对应节点p的目标函数。main()主函数。get_up() 求分支限界法的上界。get_low()求分支界限法的下界。solve()利用分支限界法求解函数(3)输入/输出设计本程序可以通过键盘进行输入、屏幕进行输出。（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式）这里采用随机产生输入数据，将数据输出在屏幕上的方式。(4) 符号名说明 n 表示顶点个数。 mp

7、ij 表示顶点i和顶点j之间的距离。 inqi 表示顶点i已经走过了。(5) 算法描述首先通过贪心法求解的值作为上界，把每个点最近的两条边之和的1/2作为下界。分支限界法通过设定目标函数，每次从优先级队列中取目标函数的值最小的节点。先判断是否已经经过了n-1个点，如果已经经过了n-1个点，那么可直接求出最短路径和，并与在队列里的其他节点的目标函数值比较，如果该路径和比其他所有在队列里的节点的目标函数值都小，那么改路径和就是问题的解。否则，继续计算优先级队列里面的其他节点。3、 源程序及注释：这里默认顶点的个数小于22。1、动态规划法#include<iostream>#includ

8、e<cstdio>#define INF 9999using namespace std;int mp2222;int n;void in() scanf("%d",&n); for(int i=0;i<n;i+) for(int j=0;j<n;j+) if(i=j) mpij=INF; continue; scanf("%d",&mpij); int dp221<<22;int solve() int s=(1<<(n-1); dp00=0; for(int i=1;i<n;i+)

9、 dpi0=mpi0; dp0(s-1)=INF; for(int j=1;j<(s-1);j+)/总共有n-1个点，但不能全部取 for(int i=1;i<n;i+) /把1(n-1)这n-1个点，映射为集合对应的二进制数中的 0(n-2)位 if(j&(1<<(i-1)=0)/i不在集合中 int m=INF; for(int k=1;k<n;k+) if(j&(1<<(k-1)>0)/k在集合中 int tmp=dpk(j-(1<<(k-1)+mpik; if(m>tmp) m=tmp; dpij=m;

10、dp0s-1=INF; for(int i=1;i<n;i+) dp0s-1=min(dp0s-1,mp0i+dpi(s-1)-(1<<(i-1); return dp0s-1;int main() in(); printf("%dn",solve(); return 0;2、贪心法#include<iostream>#include<cstdio>#define INF 9999using namespace std;int n;int mp2222;int inq22;void in() scanf("%d"

11、,&n); for(int i=1; i<=n; i+) for(int j=1; j<=n; j+) if(i=j) mpij=INF; continue; scanf("%d",&mpij); int dfs(int u,int k,int l) if(k=n) return l+mpu1; int minlen=INF , p; for(int i=1; i<=n; i+) if(inqi=0&&minlen>mpui)/*取与所有点的连边中最小的边*/ minlen=mpui; p=i; inqp=1; ret

12、urn dfs(p,k+1,l+minlen);int main() in(); inq1=1; printf("%dn",dfs(1,1,0); return 0;3、分支限界法/分支限界法#include<iostream>#include<algorithm>#include<cstdio>#include<queue>#define INF 100000using namespace std;/* n*n的一个矩阵 */int n;int mp2222;/最少3个点，最多15个点/*输入距离矩阵*/void in()

13、scanf("%d",&n); for(int i=1; i<=n; i+) for(int j=1; j<=n; j+) if(i=j) mpij=INF; continue; scanf("%d",&mpij); struct node int visp22;/标记哪些点走了 int st;/起点 int st_p;/起点的邻接点 int ed;/终点 int ed_p;/终点的邻接点 int k;/走过的点数 int sumv;/经过路径的距离 int lb;/目标函数的值 bool operator <(cons

14、t node &p )const return lb>p.lb; ;priority_queue<node> q;int low,up;int inq22;/确定上界int dfs(int u,int k,int l) if(k=n) return l+mpu1; int minlen=INF , p; for(int i=1; i<=n; i+) if(inqi=0&&minlen>mpui)/*取与所有点的连边中最小的边*/ minlen=mpui; p=i; inqp=1; return dfs(p,k+1,l+minlen);int

15、 get_lb(node p) int ret=p.sumv*2;/路径上的点的距离 int min1=INF,min2=INF;/起点和终点连出来的边 for(int i=1; i<=n; i+) if(p.vispi=0&&min1>mpip.st) min1=mpip.st; ret+=min1; for(int i=1; i<=n; i+) if(p.vispi=0&&min2>mpp.edi) min2=mpp.edi; ret+=min2; for(int i=1; i<=n; i+) if(p.vispi=0) min

16、1=min2=INF; for(int j=1; j<=n; j+) if(min1>mpij) min1=mpij; for(int j=1; j<=n; j+) if(min2>mpji) min2=mpji; ret+=min1+min2; return ret%2=0?(ret/2):(ret/2+1);void get_up() inq1=1; up=dfs(1,1,0);void get_low() low=0; for(int i=1; i<=n; i+) /*通过排序求两个最小值*/ int min1=INF,min2=INF; int tmpA2

17、2; for(int j=1; j<=n; j+) tmpAj=mpij; sort(tmpA+1,tmpA+1+n);/对临时的数组进行排序 low+=tmpA1; int solve() /*贪心法确定上界*/ get_up(); /*取每行最小的边之和作为下界*/ get_low(); /*设置初始点,默认从1开始 */ node star; star.st=1; star.ed=1; star.k=1; for(int i=1; i<=n; i+) star.vispi=0; star.visp1=1; star.sumv=0; star.lb=low; /*ret为问题的

18、解*/ int ret=INF; q.push(star); while(!q.empty() node tmp=q.top(); q.pop(); if(tmp.k=n-1) /*找最后一个没有走的点*/ int p; for(int i=1; i<=n; i+) if(tmp.vispi=0) p=i; break; int ans=tmp.sumv+mpptmp.st+mptmp.edp; node judge = q.top(); /*如果当前的路径和比所有的目标函数值都小则跳出*/ if(ans <= judge.lb) ret=min(ans,ret); break;

19、/*否则继续求其他可能的路径和，并更新上界*/ else up = min(up,ans); ret=min(ret,ans); continue; /*当前点可以向下扩展的点入优先级队列*/ node next; for(int i=1; i<=n; i+) if(tmp.vispi=0) next.st=tmp.st; /*更新路径和*/ next.sumv=tmp.sumv+mptmp.edi; /*更新最后一个点*/ next.ed=i; /*更新顶点数*/ next.k=tmp.k+1; /*更新经过的顶点*/ for(int j=1; j<=n; j+) next.vi

20、spj=tmp.vispj; next.vispi=1; /*求目标函数*/ next.lb=get_lb(next); /*如果大于上界就不加入队列*/ if(next.lb>up) continue; q.push(next); return ret;int main() in(); printf("%dn",solve(); return 0;四、运行输出结果：（贴出程序运行完成时的屏幕截图或者输出文件的内容）这里采用相同的两组数据进行测试。1、动态规划法样例1：样例2：2、贪心法样例1：样例2：贪心法只能求局部最优解，局部最优解不一定是全局最优解。3、分支限界

21、法样例1：样例2：五、调试和运行程序过程中产生的问题及采取的措施：1、动态规划法中输出错误，通过测试数据进行反复验证，并分块输出局部结果，从而发现问题并解决。2、贪心法对第二组样例的解不正确，因为局部最优解不一定是全局最优解。3、分支限界法对于测试样例输出随机值，solve()函数在每次返回的时候结果不一致。通过反复观察代码，发现循环跳出的条件有问题，应该是当前的解小于或等于队列中的目标函数值才跳出。六、对算法的程序的讨论、分析，改进设想，其它经验教训：1、动态规划法算法时间复杂度为O()，在oj上的测试时间如下：（oj上的测试样例n最大值为15）2、贪心法只能求局部最优解，不一定是全局最优解。所以第二组样例的解不正确。3、分支限界法的复杂度是根据数据的不同而不同，搜索的节点越少，复杂度越低，跟目标函数的选择有很大关系。目标函数值的计算也会需要一定时间，比如此文章中的目标函数值求解的复杂度是O()。在oj上的测试时间如下：在设置节点的时候，用数组标记经过的顶点，vispi=1，则说明i点已经经过了，由于是静态分配空间，所以每次创建新的节点，都会增加空间。所以可以考虑动态分配空间，把不用的节点的空间释放掉。4、 对于顶点少的TSP问题，还可以采用蛮力法。时间复杂