tsp.rar_salesman_tsp动态规划_动态规划tsp

旅行商问题(TSP)是组合优化中研究最多的问题之一。 问题的叙述极为简单:一个推销员要找到一条通过n个城市的最短巡回。 因为推销员问题的约束条件是每个城市都要走到，而且每个城市都只能走一次， 因而是一个城市的排列问题。如果把每种可能都计算一次,那么计算量将随n的增加而增加,是一个NP完全问题。 旅行社问题一直以来都是业界比较著名的问题，有很多算法都可以解决旅行商问题， 问题描述简单，评价函数也不复杂，问题的解可以直观地显示出来，具有各种如局部极值多等典型的性质， 这些都成为算法练兵的好处，可以清晰地比较各个算法的优劣，发现算法的缺陷。 可以说旅行商问题就是一个练兵场，一个学校，为算法提供了成长的场所。 为算法能够应用到其他复杂领域打好基础。本文阐述的主要是《算法设计》课程中回溯法解TSP问题的具体实现。 1.城市网络的存储形式 #define VRType double #define INTMAX -1 #define Status int //最大值“无穷” #define MAX_VERTEX_NUM 50 //最大顶点个数 int start; //定义全局变量，起始城市的存储编号 double MinDis; //全局变量，表示当前最优路径 double length; //全局变量，当前路径代价 typedef struct ArcCell { VRType adj;//VRType是顶点关系的类型。 //此时为权值类型 }ArcCell,AdjMatrix; typedef struct { char name[20]; }CityNames; typedef struct Urban { int vexnum,arcnum;//图的当前顶点数和弧数 AdjMatrix arcs; //邻接矩阵 CityNames CityName; //城市名称 }MGraph; //2.核心代码 int SumOptimalPath(MGraph G, int k, int *flag, int *Sp, int &stf, int *SpTemp){ int i,j;//计数器 int f = 0;//标志位 int temp;//用于暂存数据 for(i = 0; i < G.vexnum; ++i){//判断所有的城市是否都已经被访问过 if( flag == 0){ f = 1; break; } } if(f == 0){ //如果所有城市都被访问 if(G.arcs.adj != -1){ //如果最后被访问的城市到起始城市有路 length += G.arcs.adj; //将最后被访问的城市到起始城市的距离追加到路径长度上 if(length < MinDis || MinDis == -1){ //若当前路径比前面所得的路径短，则修改最短路径 MinDis = length; for (j = 0; j < G.vexnum; j++) { Sp = SpTemp; } } //否则将当前路径长度减去当前城市到起始城市的距离 length -= G.arcs.adj; } return 0; //返回上一级 } //尚有城市未被访问 f = 0; for(i = 0; i < G.vexnum; i++){ //判断当前城市是否已无可达城市 if(G.arcs.adj != -1 && G.arcs.adj != 0){ if(flag == 0){ //尚有城市可达，跳出循环 f = 1; break; } } } if(f == 0){//若已无可达城市，返回上一级 return 1; } for(i = 0; i < G.vexnum; i++){ //遍历所有未被访问且可达的城市 if(flag == 0){//若有城市未被访问 if(G.arcs.adj != -1 && G.arcs.adj != 0){//若当前城市可达该城市 length += G.arcs.adj; //将当前城市到下一个可达城市的距离追加到当前路径长度上 if(length > MinDis && MinDis != -1){ //若当前路径长度已经大于当前最短路径长度，则不必往下一级走 length -= G.arcs.adj; //将当前路径长度减掉当前城市到最后一个被访问的城市的距离 } else{ flag = 1; //表示该城市已经被访问 SpTemp = i; //将当前访问的城市存储编号存入当前路径数组 stf++; //路径数组计数器加1 temp = SumOptimalPath(G, i, flag, Sp, stf, SpTemp);//递归调用，访问下一个可达城市 if(temp == 0){ //若下一个城市为最后一个被访问的城市 length -= G.arcs.adj; //将当前路径长度减掉当前城市到最后一个被访问的城市的距离 flag = 0; //表示刚被访问的城市尚可访问 stf--; //路径数组计数器减1 return 1; //返回上一级 } if (temp == 1) { flag = 0; stf--; //路径数组计数器减1 length -= G.arcs.adj; } } } } } return 1; //返回上一级 } //3.main部分代码 void main() { int InfoSign = 1;//输入信息判断标志 char StartCityNa[20]; int flag; //访问标志数组 int ShortPath = {0}; //用于记录当前最短路径 int SpTemp = {0}; //用于记录当前路径 int stf = 1; MGraph G; MinDis = -1;//最优路径初始化为-1，表示无穷 length = 0.0;//当前路径长度初始化为0 cout<<"Please input the first city's name："; do { cin>>StartCityNa;//输入起始城市名称 start = LocateVex(G,StartCityNa); if (start == -1) { InfoSign = 1; cout<<"The city's name is error or the city doesn't exist,please input again:"; } else{ InfoSign = 0; } } while (InfoSign == 1); //初始化标志数组 for (i = 0; i < G.vexnum; i++) { flag = 0; } flag = 1; SpTemp[0] = start; SumOptimalPath(G, start, flag, ShortPath, stf, SpTemp); if (MinDis == -1) { cout<<"Sorry，starting from"<<G.CityName.name<<"doesn't have loop!"<<endl; } else{ ShortPath[0] = start; cout<<"\n"; cout<<G.CityName[ShortPath[0]].name; cout<<"--"; cout<<G.arcs[ShortPath[0]][ShortPath[1]].adj<<"Km"; cout<<"-->"; for (i = 1; i < G.vexnum - 1; i++) { cout<<G.CityName[ShortPath].name; cout<<"--"; cout<<G.arcs[ShortPath][ShortPath[i + 1]].adj<<"Km"; cout<<"-->"; if ((i % 5) == 0) { cout<<"\n"; } } cout<<G.CityName[ShortPath].name; cout<<"--"; cout<<G.arcs[ShortPath].adj<<"Km"; cout<<"-->"; cout<<G.CityName.name; cout<<"\nThe shortest route is:"<<MinDis<<"Km\n"<<endl; } //将SumOptimalPath用到的所有数据复原为初始值 MinDis = -1; length = 0; stf = 1; for (i = 0; i < MAX_VERTEX_NUM; i++) { SpTemp = 0; ShortPath = 0; flag = 0; } system("pause"); } 综述 本人在遇到TSP问题时也搜索过其它算法，诸如遗传算法、蚁群算法等配套模拟退火算法的实现方法， 也考虑到了《算法设计》上的贪心法、动态规划法等，但基于时间限制仅实现了回溯法，毕竟比较简单， 当然这也是效率最差的一种算法。 朋友们很容易看出我用了《数据结构》上无向图（邻接矩阵存储）的创建， 我个人认为这样更能模拟一个城市网络，毕竟两个城市间可能无路，也可能有路并且是无向的。 当然，TSP问题是一个NP难题，随着城市数N的增长，时间复杂度呈指数增长， 倘若创建的是完全图且城市数目很大，那么运行时间将不可想象。据说1050已是一个不可达数字， 若是有1000个城市的完全图便是10001000那我们的程序得运行多久，有兴趣的朋友可以试一下。