数据结构与算法分析2

数据结构与算法分析2算法设计报告书班级惠普测试学号姓名指导教师庞志永算法设计项目名称：满足三角不等式的TSP问题的近似算法1.问题描述2.基本要求(1)设计满足三角不等式的TSP问题的近似性能比小于2或1.5的多项式时间近似算法，并选择适当的编程语言在计算机上实现。(2)程序能够正常运行，计算结果正确，满足设计要求。3.算法描述4.模块划分(仅供参考)(1)描述及输入原始数据模块(2)求解最小生成树模块(3)构造欧拉图模块(4)搜索欧拉回路模块(5)抄近路计算模块(6)存储及输出结果模块5.本课程设计中遇到的关键问题及其解决方法课题关键：在给定一系列城市和每对城市之间的距离的情况下，求解访问每一座城市一次并回到起始城市的最短回路。解答本课题的思路：以最小生成树T求解旅游回路：复制树的每条边构建欧拉图，运用深度优先搜索寻找欧拉图的欧拉回路，而树的深度优先搜索序列与此欧拉回路相同，可用深度优先搜索算法优化求解欧拉回路和抄近路算法的过程。6.运行结果及其相关描述要求实例中城市的数量在20—100之间。命令行输入此次实验验证20个城市即为20个顶点，190条边12213323214324334215325335345216326336346356217327337347357367218328338348358368378219329312{,,...,},(,),(,)(,)(,),,min()(1),...,()12,...,mijijjkikijkmmiiiCcccdccZdccdccdcccccCmccdccmmc(1)()()(+1)=1实例:城市集合城市之间距离其中：,。询问:寻找个城市的一个排列,...,，使得：,其中是,的一个全排列,且(1)(1)mc。(1)(,)(2)'(3)'GVEGTTGG，；；对TSP问题实例的赋权完全图调用最小生成树算法，得到的最小生成树复制最小生成树的每条边,形成欧拉图在中寻找欧拉回路；(4)采用抄近路方法,将欧拉回路变成TSP旅游回路。393493593693793892110321033103410351036103710381039102111321133113411351136113711381139113101121123212331234123512361237123812391231012311122113321333133413351336133713381339133101331113312132114321433143414351436143714381439143101431114312143131421153215331534153515361537153815391531015311153121531315314152116321633163416351636163716381639163101631116312163131631416315162117321733173417351736173717381739173101731117312173131731417315173161721183218331834183518361837183818391831018311183121831318314183151831618317182119321933193419351936193719381939193101931119312193131931419315193161931719318192120322033203420352036203720382039203102031120312203132031420315203162031720318203192027.其他需要说明的问题（一）以二十个城市为例算法路径为39（二）以五个城市为例算法路径：8最短路径：6：1-2-3-4-5-18.课程设计总结在求解关于图的问题时选择合适的数据结构存图对算法的时间空间复杂度有很大影响。满足三角不等式的TSP问题的最小生成树算法可在O（n²）的时间内找到并构建相应完全赋权图的最小生成树，该树的权值不大于最短旅游回路的权值，DFS序列回路的权值不大于实际最短旅游回路的权值的2倍即近似性能比小于2。附录：相关模块代码及其描述：#includeiostream#includecstdio#includevector#includequeue#includealgorithm#includebits/stdc++.husingnamespacestd;constintMAXV=1000;constintMAXE=1000;constintMAX=1000;structedge{intu,v;//边的两个端点intcost;//边权}E[MAXE];staticintm;intHead[MAX];intcnt;boolvis[MAX];boolcmp(edgea,edgeb){returna.costb.cost;}voidCreate(intu,intv,intcost){inti=0;E[i].u=u;E[i].v=v;E[i++].cost=cost;}voidJudgeC(){inti=0;scanf(%d,&m);cout依次输入起点，终点，权值)：endl;while(~scanf(%d%d%d,&E[i].u,&E[i].v,&E[i].cost)){Create(E[i].u,E[i].v,E[i].cost);i++;}}intfather[MAXV];intfindFather(intx){inta=x;while(x!=father[x]){x=father[x];}while(a!=father[a]){intz=a;a=father[a];father[z]=x;}returnx;}intst;//起点vectorinttempPath,path;//临时路径vectorintpre[MAX];//前驱intcost[MAX][MAX];//花费矩阵intminCost=10000;//minCost记录最短路径上的最小花费voiddfs(intv){if(v==st){tempPath.push_back(v);inttempCost=0;for(inti=tempPath.size()-1;i0;i--){intid=tempPath[i],idNext=tempPath[i-1];tempCost+=cost[id][idNext];}if(tempCostminCost){//如果当前路径的边权之和最小minCost=tempCost;path=tempPath;}tempPath.pop_back();return;}tempPath.push_back(v);for(inti=0;ipre[v].size();i++){//DFS(pre[v][i]);}tempPath.pop_back();}//Kruskal,返回最小生成树的边权之和intKruskal(intn,intm){intans=0,Num_Edge=0;for(inti=0;in;i++){//顶点范围[0,n-1]father[i]=i;}sort(E,E+m,cmp);//所有边权从小到大排序for(inti=0;im;i++){intfaU=findFather(E[i].u);//查询测试两个端点所在集合的根节点intfaV=findFather(E[i].v);if(faU!=faV){//如果不在一个集合中father[faU]=faV;//合并集合，把测试边加入最小生成树中ans+=E[i].cost;//边权之和增加测试边的边权Num_Edge++;//当前生成树的边数加1if(Num_Edge==n-1)break;}}if(Num_Edge!=n-1)return-1;elsereturnans;//返回最小生成树的边权之和}voidMinRoad(){cout1;for(inti=1;im;i++){if(E[i].cost==2){coutE[i].u;}}coutE[0].vendl;}intmain(){memset(vis,0,sizeof(vis));intst;intn;cout请输入图的顶点和边:endl;scanf(%d,&n);JudgeC();cout最短路线:endl;MinRoad();intans=Kruskal(n,m);cout算法路径为:ansendl;return0;}