算法课程设计-旅行商问题源代码+算法伪代码

《算法课程设计-旅行商问题源代码+算法伪代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计课程报告双调欧几里得旅行商问题·双调欧几里得旅行商问题问题描述：在平面商给出n个点的坐标，旅行者从其中一个点出发，遍历该平面的n-1个坐标点，并回到出发点，要求该环路的总距离最短，给出最有的结果。问题分析：本题采用动态规划的思想，1.可以先将7个点按照横坐标由小到大的顺序依次编号,摄像两个人Pipj，两个人同样使用严格的从左向右扫瞄的方式，从第一个点走到最右边的点（本例中为第7个点），并且始终pi走在pj前面，所以PiPj表示从i点向左走到1点，再从一点沿另外一条路线，走到j点的路径长度2.定义一个二维数组m[n][n]，其中m[i][j]存放的是第i个点和第j个点，双调

2、路线的pipj的最短长度。3以下给出递归求解的公式当i==j时（pipj走到同一个点）m[i][j]=m[i][j-1]+

3、pj-1pi

4、当i>j+1时（pi在pj前面至少两个点）m[i][j]=m[i-1][j]+

5、pi-1pi

6、当i=j+1时（pi仅在pj前一步）当j=1即i=2m[i][j]=m[1][2]=

7、p1p2

8、Pipj相邻，判断是否选择直接相邻，还是选择中间节点k若直接相连路线最短则m[i][j]=

9、pipj

10、否则遍历寻找中间节点km[i][j]=m[k][j]+

11、pkpi

12、伪代码：//

13、pipj

14、表示两点之间的直线距离/*以下为本题核心算法，操作结果使m[i][

15、j]存储了ij点最短双调路线距离*/Shortest(pointp[])Intm[8][8]//m[i][j]存放的是第i个点和第j个点之间的最短距离Fori<-1to8m[i][0]&&m[0][i]0//初始化m二维数组m[1][1]=0fori1to7forj1toiifi==jm[i][j]=m[i][j-1]+distance(p,i,j)ifi>j+1//pi在pj前面一个点之前的点m[i][j]m[i-1][j]+

16、Pi-1pi

17、ifi=j+1//pi在pj前面一点的位置ifj=1i=2m[i][j]=m[1][2]=

18、pipj

19、elseiffork=1to

20、j//不直接相连寻找中间节点ktmp=m[k][j]+m[k][i]iftmp#include#include#definen7typedefstruct//定义坐标点{intx;//横坐标inty;//纵坐标}point;intm[8][8];intdistance(pointp[],inti,intj)//操作结果得到p中ij点之间的直线距离{i

21、f(i>=1&&j>=1){intdifx,dify;difx=abs(p[i].x-p[j].x);dify=abs(p[i].y-p[j].y);doubled=sqrt(difx*difx+dify*dify);return(int)d;}elsereturn0;}voidshortest(pointp[])//操作结果使m[i][j]存储了ij点最短双调路线距离{for(inti=1;i<=7;i++){for(intj=1;j<=i;j++){if(i==j)//i和j在同一个点当i=j=7时即为回路的最短路径{m[i][j]=m[i][j-1]+distance(p,

22、i,j-1);//pipj最短路径由pi到前一个点距离和m[i][j-1]}if(i>j+1)//i在j两步之前{m[i][j]=m[i-1][j]+distance(p,i-1,i);}if(i==j+1)//i仅在j前面一步{if(j==1)//j在第1点i在第二点m[i][j]=distance(p,i,j);//计算m[1][2]距离elsem[i][j]=m[i][j-1]+distance(p,j-1,i);//想将m[i][j]的距离初始为当ij直接相连的情况for(intk=1;k

23、emp=m[k][j]+distance(p,k,i);if(temp