数据结构与算法分析

《数据结构与算法分析》由会员分享，可在线阅读，更多相关《数据结构与算法分析（7页珍藏版）》请在装配图网上搜索。

1、数据结构与算法分析2算法设计报告书班级 惠普测试 学号 姓名 指导教师 庞志永 算法设计项目名称：满足三角不等式的TSP问题的近似算法1.问题描述2.基本要求(1)设计满足三角不等式的TSP问题的近似性能比小于2或1.5的多项式时间近似算法，并选择适当的编程语言在计算机上实现。(2)程序能够正常运行，计算结果正确，满足设计要求。3.算法描述4.模块划分(仅供参考)(1)描述及输入原始数据模块(2)求解最小生成树模块(3)构造欧拉图模块(4)搜索欧拉回路模块(5)抄近路计算模块(6)存储及输出结果模块5.本课程设计中遇到的关键问题及其解决方法课题关键：在给定一系列城市和每对城市之间的距离的情况下

2、，求解访问每一座城市一次并回到起始城市的最短回路。 解答本课题的思路：以最小生成树T求解旅游回路：复制树的每条边构建欧拉图，运用深度优先搜索寻找欧拉图的欧拉回路，而树的深度优先搜索序列与此欧拉回路相同，可用深度优先搜索算法优化求解欧拉回路和抄近路算法的过程。6.运行结果及其相关描述要求实例中城市的数量在20100之间。命令行输入此次实验验证20个城市即为20个顶点，190条边1 2 2 1 3 3 2 3 2 1 4 3 2 4 3 3 4 2 1 5 3 2 5 3 3 5 3 4 5 2 1 6 3 2 6 3 3 6 3 4 6 3 5 6 2 1 7 3 2 7 3 3 7 3 4 7

3、 3 5 7 3 6 7 2 1 8 3 2 8 3 3 8 3 4 8 3 5 8 3 6 8 3 7 8 2 1 9 3 2 9 3 3 9 3 4 9 3 5 9 3 6 9 3 7 9 3 8 9 2 1 10 3 2 10 3 3 10 3 4 10 3 5 10 3 6 10 3 7 10 3 8 10 3 9 10 2 1 11 3 2 11 3 3 11 3 4 11 3 5 11 3 6 11 3 7 11 3 8 11 3 9 11 3 10 11 2 1 12 3 2 12 3 3 12 3 4 12 3 5 12 3 6 12 3 7 12 3 8 12 3 9 12

4、3 10 12 3 11 12 2 1 13 3 2 13 3 3 13 3 4 13 3 5 13 3 6 13 3 7 13 3 8 13 3 9 13 3 10 13 3 11 13 3 12 13 2 1 14 3 2 14 3 3 14 3 4 14 3 5 14 3 6 14 3 7 14 3 8 14 3 9 14 3 10 14 3 11 14 3 12 14 3 13 14 2 1 15 3 2 15 3 3 15 3 4 15 3 5 15 3 6 15 3 7 15 3 8 15 3 9 15 3 10 15 3 11 15 3 12 15 3 13 15 3 14 15

5、 2 1 16 3 2 16 3 3 16 3 4 16 3 5 16 3 6 16 3 7 16 3 8 16 3 9 16 3 10 16 3 11 16 3 12 16 3 13 16 3 14 16 3 15 16 2 1 17 3 2 17 3 3 17 3 4 17 3 5 17 3 6 17 3 7 17 3 8 17 3 9 17 3 10 17 3 11 17 3 12 17 3 13 17 3 14 17 3 15 17 3 16 17 2 1 18 3 2 18 3 3 18 3 4 18 3 5 18 3 6 18 3 7 18 3 8 18 3 9 18 3 10 1

6、8 3 11 18 3 12 18 3 13 18 3 14 18 3 15 18 3 16 18 3 17 18 2 1 19 3 2 19 3 3 19 3 4 19 3 5 19 3 6 19 3 7 19 3 8 19 3 9 19 3 10 19 3 11 19 3 12 19 3 13 19 3 14 19 3 15 19 3 16 19 3 17 19 3 18 19 2 1 20 3 2 20 3 3 20 3 4 20 3 5 20 3 6 20 3 7 20 3 8 20 3 9 20 3 10 20 3 11 20 3 12 20 3 13 20 3 14 20 3 15

7、 20 3 16 20 3 17 20 3 18 20 3 19 20 2 7.其他需要说明的问题（一）以二十个城市为例算法路径为39（二）以五个城市为例 算法路径：8最短路径：6：1-2-3-4-5-18.课程设计总结在求解关于图的问题时选择合适的数据结构存图对算法的时间空间复杂度有很大影响。满足三角不等式的TSP问题的最小生成树算法可在O（n）的时间内找到并构建相应完全赋权图的最小生成树，该树的权值不大于最短旅游回路的权值，DFS序列回路的权值不大于实际最短旅游回路的权值的2倍即近似性能比小于2。附录：相关模块代码及其描述：#include#include#include#include#

8、include#includeusing namespace std;const int MAXV=1000;const int MAXE=1000;const int MAX=1000;struct edgeint u,v;/边的两个端点 int cost;/边权 EMAXE;static int m;int HeadMAX;int cnt;bool visMAX;bool cmp(edge a,edge b)return a.costb.cost; void Create(int u,int v,int cost)int i=0;Ei.u=u;Ei.v=v;Ei+.cost=cost;vo

9、id JudgeC()int i=0;scanf(%d,&m);cout 依次输入起点，终点，权值)： endl;while(scanf(%d%d%d,&Ei.u,&Ei.v,&Ei.cost)Create(Ei.u,Ei.v,Ei.cost);i+;int fatherMAXV;int findFather(int x)int a=x;while(x!=fatherx)x=fatherx;while(a!=fathera)int z=a;a=fathera;fatherz=x;return x;int st;/起点 vector tempPath,path;/临时路径 vector preM

10、AX;/前驱 int costMAXMAX;/花费矩阵 int minCost=10000;/minCost记录最短路径上的最小花费 void dfs(int v)if(v=st)tempPath.push_back(v);int tempCost=0;for(int i=tempPath.size()-1;i0;i-)int id=tempPathi,idNext=tempPathi-1;tempCost+=costididNext;if(tempCostminCost)/如果当前路径的边权之和最小 minCost=tempCost;path=tempPath; tempPath.pop_b

11、ack();return; tempPath.push_back(v);for(int i=0;iprev.size();i+)/DFS(previ);tempPath.pop_back();/Kruskal,返回最小生成树的边权之和int Kruskal(int n,int m)int ans=0,Num_Edge=0;for(int i=0;in;i+)/顶点范围0,n-1 fatheri=i;sort(E,E+m,cmp);/所有边权从小到大排序for(int i=0;im;i+)int faU=findFather(Ei.u);/查询测试两个端点所在集合的根节点int faV=find

12、Father(Ei.v);if(faU!=faV)/如果不在一个集合中 fatherfaU=faV;/合并集合，把测试边加入最小生成树中ans+=Ei.cost;/边权之和增加测试边的边权Num_Edge+;/当前生成树的边数加1if(Num_Edge=n-1)break; if(Num_Edge!=n-1)return -1;elsereturn ans;/返回最小生成树的边权之和 void MinRoad()cout1 ;for(int i=1;im;i+)if(Ei.cost=2)coutEi.u ;coutE0.vendl;int main() memset(vis,0,sizeof(vis);int st;int n;cout请输入图的顶点和边:endl;scanf(%d,&n);JudgeC();cout最短路线:endl;MinRoad();int ans=Kruskal(n,m);cout算法路径为:ansendl; return 0;