C++旅行商问题

旅行商问题实验报告学院：计算机科学与技术专业：计算机科学与技术学号：班级：姓名：（本程序在ＭｉｃｒｏｓｏｆｔＶｉｓｕａｌＣ＋＋６．０的环境下实现）一、问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。例如：给定4个城市{a，b，c，d}及其各城市之间的路程,找出其最短路径二、算法思想：首先是在图为完全图的前提下，构造各城市间的图的结构，采用邻接数组的形式，将各个城市间的距离存储于图的数组中，用一个函数递归寻找从同一个顶点出发的各个城市的所有路径，再求出各个路径的路程，并与相应的路径输出，对路程数组进行冒泡排序后，经比较找出最短路径并输出。三．具体实现及分析：图结构的定义：structMGraph{charvexs[MAX_VEX_NUM];//顶点向量intarcs[MAX_VEX_NUM][MAX_VEX_NUM];//邻接矩阵intvexnum,arcnum;//顶点数，边数};//AdjMatrix函数intCreateUDG(MGraph&G)用数组邻接矩阵表示法构造无向图ADCB235178函数voidPerm(Typelist[],intk,intm)用于递归生成路径排列，并寻找最佳路径采用递归实现路径排列是一种比较简便的方法，但其需做(n-1)!/2次循环，时间复杂度为O((n-1)!/2),有待改进。辅助数组Help[]对Count[]数组进行排序，找出最小值，当旅行商的地点大于等于5时，只比较Count[]数组的前半部分会有遗漏。函数voidSwap(Type&a,Type&b)用于递归时的字符交换函数函数voidInicialize(MGraph&G)//用于初始化各个数组，并调用递归函数Perm();主函数：voidmain()//主函数{intchoice;//选择操作变量while(true){cout请选择操作：1:执行程序！0:退出程序！endl;cinchoice;if(choice==1){CreateUDG(G);//函数调用Inicialize(G);coutendl;coutendl;}if(choice==0)break;}}三．源程序：#includeiostreamusingnamespacestd;#defineMAX_VEX_NUM20//最大顶点数int**Mat;//定义动态二维数组，存储生成的排列int*list;//定义动态辅助数组int*Count;//定义动态计数数组int*Help;//定义动态辅助数组inte=0;//定义全局变量structMGraph{charvexs[MAX_VEX_NUM];//顶点向量intarcs[MAX_VEX_NUM][MAX_VEX_NUM];//邻接矩阵intvexnum,arcnum;//顶点数，边数};//AdjMatrixMGraphG;//声明一个无向图的邻接矩阵类型intvisited[MAX_VEX_NUM];//设置标志数组intLocatevex(MGraphG,charv)//图的基本操作，寻找顶点V的位置{inti=0;while(iG.vexnum&&v!=G.vexs[i])i++;if(iG.vexnum)returni;//查找成功则返回顶点的下标elsereturn-1;}intCreateUDG(MGraph&G)//数组邻接矩阵表示法构造无向图{charv1,v2;intweight;//权值cout请输入图的顶点数和弧数endl;cinG.vexnumG.arcnum;cout请输入顶点值endl;for(inti=0;iG.vexnum;i++)//构造顶点向量cinG.vexs[i];for(intq=0;qG.vexnum;q++){for(intp=0;pG.vexnum;p++){G.arcs[q][p]=0;//初始化邻接矩阵}}for(intk=0;kG.arcnum;k++)//构造邻接矩阵{cout输入该弧依附的顶点和权值：endl;cinv1v2weight;inta=Locatevex(G,v1);intb=Locatevex(G,v2);G.arcs[a][b]=weight;G.arcs[b][a]=G.arcs[a][b];}cout图的顶点：;for(intn=0;nG.vexnum;n++)//输出顶点coutG.vexs[n];coutendl;coutendl;cout该图的邻接矩阵表示为：\n;for(intx=0;xG.vexnum;x++){for(inty=0;yG.vexnum;y++){coutG.arcs[x][y];//输出邻接矩阵}coutendl;}coutendl;coutendl;return1;}//CreateUDGtemplateclassTypevoidPerm(Typelist[],intk,intm)//递归函数，生成排列，寻找最佳路径{intc=1;inta=m;while(a1)//定义Mat数组的行数{c=c*a*(a-1);a-=2;}intd=m+1;//定义Mat数组的列数if(k==m&&list[0]==0){for(inti=0;i=m;i++){Mat[e][i]=list[i];//符合条件时生成排列，存储在数组Mat中}e++;}if(Mat[c-1][m]!=-1&&e==c)//当找出所有可能路径时，计算所有路径长度，并找到最短路径{for(intg=0;gc;g++){for(inth=0;hd;h++){intx=Mat[g][h];//获取路径坐标inty=Mat[g][h+1];Count[g]=Count[g]+G.arcs[x][y];//计算路径长度}}cout所有路径及其路径长度：endl;for(g=0;gc;g++)//输出所有路径及其路径长度{for(inth=0;h=d;h++){intk=Mat[g][h];coutG.vexs[k]-;}coutCount[g]endl;}for(g=0;gc;g++)Help[g]=Count[g];//赋值for(inti=0;ic;i++)//对辅助数组冒泡排序，找最小值{for(intj=1;jc;j++){if(Help[i]Help[j]){inttemp=Help[i];Help[i]=Help[j];Help[j]=temp;}}}intMin_way=Help[0];//Min_way为最短路径for(i=0;ic;i++){if(Count[i]==Min_way){cout旅行商最佳路径为：;for(intj=0;j=d;j++){intk=Mat[i][j];coutG.vexs[k]-;//输出最短路径}cout路径长度为：Min_way;coutendl;}}}else{for(inti=k;i=m;i++)//递归生成排列组合{Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}}templateclassTypeinlinevoidSwap(Type&a,Type&b)//字符交换函数{Typetemp=a;a=b;b=temp;}voidInicialize(MGraph&G)//初始化各个数组函数{inta=G.vexnum;//图的顶点数，列数intb=a-1;//辅助变量intc=a-1;intn=1;//辅助变量,行数while(b1){n=n*b*(b-1);b-=2;}Mat=newint*[n];for(inti=0;in;i++){Mat[i]=newint[a];for(intj=0;j=a;j++){if(ja){Mat[i][j]=-1;//数组初始化}else{Mat[i][j]=0;}}}list=newint[a];for(i=0;ia;i++)//数组初始化list[i]=i;Count=newint[n];for(i=0;in;i++)Count[i]=0;//数组初始化Help=newint[n];for(i=0;in;i++)Help[i]=0;//数组初始化Perm(list,1,c);//函数调用}voidmain()//主函数{CreateUDG(G);//函数调用Inicialize(G);}四．运行结果：1当顶点为4时：2测试当顶点为5时：