欢迎来到天天文库
浏览记录
ID:59194490
大小:44.89 KB
页数:3页
时间:2020-09-10
《数据结构实验报告-TSP问题.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、TSP问题一,实验目的熟悉图的数据结构,学会解决实际问题二,实验内容旅行商问题,即TSP问题(TravellingSalesmanProblem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。三,设计与编码#includeusingnamespacestd;constintMaxSize=10;constintMax=100;intMin(intarr[],intn);class
2、MGraph{public:MGraph(charcity[],intn,inte);~MGraph(){}voidTSP(intv);private:charvertex[MaxSize];intarc[MaxSize][MaxSize];intvertexNum,arcNum;};intvisited[MaxSize]={0};intmain(){charcity[]={'A','B','C','D','E'};MGraphMG(city,5,10);MG.TSP(0);return0;}voidMGraph::TSP(intv){cout<3、=1;inti=0,j=0,s=0;intlog=0;for(;log"<=p[start])){k=start;min=p[k];}}returnk4、;}//构造函数MGraph::MGraph(charcity[],intn,inte){vertexNum=n;arcNum=e;//存储顶点信息for(inti=0;i>i>>j>>weight;arc[i][5、j]=weight;arc[j][i]=weight;}}一,运行与测试二,总结与心得通过对实际问题的解决,巩固了课本知识,提高了编写代码的能力
3、=1;inti=0,j=0,s=0;intlog=0;for(;log"<=p[start])){k=start;min=p[k];}}returnk
4、;}//构造函数MGraph::MGraph(charcity[],intn,inte){vertexNum=n;arcNum=e;//存储顶点信息for(inti=0;i>i>>j>>weight;arc[i][
5、j]=weight;arc[j][i]=weight;}}一,运行与测试二,总结与心得通过对实际问题的解决,巩固了课本知识,提高了编写代码的能力
此文档下载收益归作者所有