数据结构实验报告-TSP问题.docx

《数据结构实验报告-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];}}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;}}一，运行与测试二，总结与心得通过对实际问题的解决，巩固了课本知识，提高了编写代码的能力