资源描述:
《算法课程设计-旅行商问题源代码+算法伪代码》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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]=0fori 1to7forj 1toiifi==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;k23、emp=m[k][j]+distance(p,k,i);if(temp