C++旅行商问题.doc

旅行商问题实验报告 学院： 计算机科学与技术 专业：计算机科学与技术 学号： 班级： 姓名： （本程序在Ｍｉｃｒｏｓｏｆｔ　Ｖｉｓｕａｌ　Ｃ＋＋　６．０的环境下实现） 问题描述： 某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。 例如：给定4个城市{a，b，c，d}及其各城市之间的路程,找出其最短路径 二、算法思想： 首先是在图为完全图的前提下，构造各城市间的图的结构，采用邻接数组的形式，将各个城市间的距离存储于图的数组中，用一个函数递归寻找从同一个顶点出发的各个城市的所有路径，再求出各个路径的路程，并与相应的路径输出，对路程数组进行冒泡排序后，经比较找出最短路径并输出。 三．具体实现及分析： 图结构的定义： struct MGraph { char vexs[MAX_VEX_NUM];//顶点向量 int arcs[MAX_VEX_NUM][MAX_VEX_NUM];//邻接矩阵 int vexnum,arcnum;//顶点数，边数 };// AdjMatrix 函数int CreateUDG(MGraph G) 用数组邻接矩阵表示法构造无向图 函数void Perm(Type list[], int k, int m)用于递归生成路径排列，并寻找最佳路径 采用递归实现路径排列是一种比较简便的方法，但其需做(n-1)!/2次循环，时间复杂度为O((n-1)!/2),有待改进。辅助数组Help[ ]对Count[ ]数组进行排序，找出最小值，当旅行商的地点大于等于5时，只比较Count[ ]数组的前半部分会有遗漏。 函数void Swap ( Type a ,Type b)用于递归时的字符交换函数 函数void Inicialize(MGraph G)//用于初始化各个数组，并调用递归函数Perm(); 主函数： void main()//主函数 { int choice;//选择操作变量 while(true) { cout请选择操作： 1: 执行程序！ 0: 退出程序！endl; cinchoice; if (choice==1) { CreateUDG(G);//函数调用 Inicialize(G); coutendl; coutendl; } if (choice==0) break; } } 三．源程序： #includeiostream using namespace std; #define MAX_VEX_NUM 20//最大顶点数 int **Mat;//定义动态二维数组，存储生成的排列 int *list;//定义动态辅助数组 int *Count;//定义动态计数数组 int *Help;//定义动态辅助数组 int e=0;//定义全局变量 struct MGraph { char vexs[MAX_VEX_NUM];//顶点向量 int arcs[MAX_VEX_NUM][MAX_VEX_NUM];//邻接矩阵 int vexnum,arcnum;//顶点数，边数 };// AdjMatrix MGraph G; //声明一个无向图的邻接矩阵类型 int visited[MAX_VEX_NUM];//设置标志数组 int Locatevex(MGraph G,char v)//图的基本操作，寻找顶点V的位置 { int i=0; while(iG.vexnum v!=G.vexs[i]) i++; if(iG.vexnum) return i;//查找成功则返回顶点的下标 else return -1; } int CreateUDG(MGraph G) //数组邻接矩阵表示法构造无向图 { char v1,v2; int weight;//权值 cout请输入图的顶点数和弧数endl; cinG.vexnumG.arcnum; cout请输入顶点值endl; for(int i=0;iG.vexnum;i++)//构造顶点向量 cinG.vexs[i]; for(int q=0;qG.vexnum;q++) { for(int p=0;pG.vexnum;p++) { G.arcs[q][p]=0;//初始化邻接矩阵 } } for(int k=0;kG.arcnum;k++)//构造邻接矩阵