TSP问题的解决与实现讲解

1、1 .问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并且要求 所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为 人知的问题。2 .基本要求（1）上网查找TSP问题的应用实例；（2）分析求TSP问题的全局最优解的时间复杂度；（3）设计一个求近似解的算法；（4）分析算法的时间复杂度。3 .提交报告课程设计报告提交内容包括：（1）问题描述；（2）需求分析；（3）概要设计；（4）详细设计；（5）调试分析；（6）使用说 明；（7）测试结果；（8）附录（带注释的源程序）。参见“数据结构课程设计概述.pdf”和“数据结构课程设计示例.pdf”。

2、指导教师（签字）：系主任（签字）：批准日期：2014年 月 日1 .问题描述（1）题目要求旅行家要旅行n个城市，要求各个城市经历且仅经历一次，最终要回到出发的城市，求 出最短路径。用图论的术语来说，假如有一个图 G=（V,E）,其中V是顶点集，E是边集，设D=（dj）是由 顶点i和顶点j之间的距离所组成的距离矩阵。TSP问题就是求出一条通过每个顶点且每个顶 点只通过一次的具有最短距离的回路。(2)基本要求a.上网查找TSP问题的应用实例；b.分析求TSP问题的全局最优解的时间复杂度;c.设计一个求近似解的算法；d.分析算法的时间复杂度。(3)测试数据5个城市的TSP问题:路程矩阵如图所示:注：

3、由于矩阵所表示的是两个城市之间的距离，所以该矩阵为对称矩阵OO2541322825OO1831264118OO7132317OO112826111OO0213420134最短路径为V0V1V4V2V32 .需求分析(1)本程序用于求解n个结点的最短哈密尔顿回路问题。(2)程序运行后显示提示信息 一Please insert the number of cities: "，例如用户输入5,则表示结 点n的值为 5;接下来程序输出提示信息 “Please insert the distance between one city and another:"，例如用户输入测试数据中

4、给出的路程矩阵，表示任意两个城市之间的距离，比 如第一个城市到第0个城市之间的距离为25。(3)用户输入数据完毕，程序将输出运算结果。(4)测试数据均为正数，其中用999来表示两个城市之间距离为3 .概要设计为了实现上述程序功能，使用优先队列来维护结点表，因此需要图和队列两个抽象数据类(1)图的抽象数据类型定义ADT GraphData:具有相同类型的数据元素的集合，称为顶点集。Relation :顶点偶对的有穷集合。Operation :CreateGraph(&G ,V,VR)初始条件：V是图中顶点集合，VR是图中顶点偶对集合。操作条件：按照V和VR的定义构造图GoDestroyG

5、raph(&G)初始条件：图G已经存在。操作结果：销毁GoLocateVex(G,u)初始条件：图G已经存在，u和G中顶点有相同类型。操作结果：如果G中存在u,则返回u在G中的位置；否则返回相应信息。GetVex(G,v)初始条件：图G已经存在，v是G中某个顶点。操作结果：返回v的值。PutVex(&G,v,value)初始条件：图G已经存在，v是G中顶点。操作结果：对v赋值value oFirstAdjvex(G ,v)初始条件：图G已经存在，v是G中顶点。操作结果：返回v的第一个邻接顶点。如果v在G中没有邻接顶点，则返回相应信息。NextAdjvex(G,v,w)初始条件：

6、图G已经存在，v是G中顶点,w是v的邻接顶点。操作结果：返回v的下一个邻接顶点。如果w是v的最后一个邻接点，则返回相应信息InsertVex(&G,v,w)初始条件：图G已经存在，v和w是G中顶点。操作结果：在G中添加VoDeleteVex(&G,v)初始条件：图G已经存在，v是G中顶点。操作结果：删除G中顶点v及其相关的边。InsertEdge(&G ,v,w) 初始条件：图G已经存在，v和w是G中顶点。操作结果：在G中添加v,w ;如果G是无向图，则还增添w,vDeleteEdge(&G,v,w)初始条件：图G已经存在，v和w是G中顶点。操作结果：在G中删除

7、v,w;如果G是无向图，则还删除w,v。DFSTraverse(G,v)初始条件：图G已经存在，v是G中顶点。操作结果：从v起深度访问GoBFSTraverse(G,v)初始条件：图G已经存在，v是G中顶点。操作结果：从v起广度访问G。ADT Graph(2)队列的抽象数据类型ADT QueueData:具有相同数据类型的及先进先出特性的数据元素集合。Relation :相邻数据元素具有前驱和后继的关系。Operation：InitQueue(&Q)初始条件：无操作结果：创造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已经存在。操作结果：销毁Q。ClearQu

8、eue(&Q)初始条件：队列Q已经存在。操作结果：重置Q为空队列。QueueLength(Q)初始条件：队列Q已经存在。操作结果： 返回Q的元素个数。GetHead(Q, &e)初始条件：队列Q已经存在并且非空。操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已经存在。操作结果：重置Q为空队列。DeQueue(&Q, &e)初始条件：队列Q已经存在且非空。操作结果：删除Q的队头元素，并用e返回其值。ADT Queue三大模块之间的调用关(3)本程序包含三大模块：主程序模块，TSP算法模块，辅函数模块 系如下。主函数模块TSP算法

9、模块7辅函数模块4 .详细设计Node *xnode;Node *ynode;Node *znode;Node *qbase;ElemType bound;(1)元素类型、结点类型和指针类型、变量和数据结构声明父亲结点指针儿子结点指针儿子结点指针/优先队列首指针当前可行解的最优值typedef int ElemType;#define MAX_V ALUE_OF_TYPE 999;元素类型代表00城市顶点用数字0, 1, 2,，n-1编号。在搜索的过程中，各个结点的数据是动态变 化的，互不相同，发生回溯时，必须使用结点中原来的数据。因此，每个结点的数据必须是 局部与该结点的。用如下的数据结构来

10、定义结点中所使用的数据：typedef struct NodeElemType c100100;intinit_row100;intinit_col100;intcur_row100;intcur_col100;intad100;intk;ElemType w;struct Node *next;Node;/路程矩阵/路程矩阵的当前行映射为原始行/路程矩阵的当前列映射为原始列路程矩阵的原始行映射为当前行/路程矩阵的原始列映射为当前列回路顶点邻接表当前路程矩阵的阶结点的下界队列链指针(2)队列类型Node *data;数据域struct QNode *next;指针域typedef struct

11、 QNodeQNode,*QueuePtr;typedef structQueuePtr front;头指针，指向链队头结点QueuePtr rear;尾指针，指向链队列最后一个结点LinkQueue;程序中所用到的关于优先队列基本操作实现的伪码算法如下:void InitQueue(LinkQueue &Q)/构造一个空链队列QQ.front=Q.rear=new QNode;Q.front->next=NULL;/InitQueuevoid EnQueue(LinkQueue &Q,Node *e)插入一个指针e到链队列Q中，成为新的队尾指针QueuePtr p;p=

12、new QNode;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;/EnQueueNode *DeQueue(LinkQueue &Q)/若链队列Q为空，则返回NULL ;否则返回指向数据的指针QNode *p;Node *e;if(Q.front->next=NULL)return NULL;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;delete p;return e;/DeQueu

13、e(3)辅助函数的实现(共7个)ElemType Row_min(Node *node,int row,ElemType &second)计算路程矩阵行的最小值if(node->crow0<node->crow1)temp=node->crow0;second=node->crow1;else temp=node->crow1;second=node->crow0;for(i=2;i<node->k;i+)if(node->crowi<temp)second=temp;temp=node->crowi;)else

14、if(node->crowi<second)second=node->crowi;)return temp;)ElemType Col_min(Node *node,int col,ElemType &second)计算路程矩阵列的最小值if(node->c0col<node->c1col)temp=node->c0col;second=node->c1col;)else temp=node->c1col;second=node->c0col;)for(i=2;i<node->k;i+)if(node->ci

15、col<temp)second=temp;temp=node->cicol;)else if(node->cicol<second)second=node->cicol;)return temp;)ElemType Array_red(Node *node)归约node所指向的结点的路程矩阵sum=0;行归约行归约常数行归约常数累计列归约列归约常数for(i=0;i<node->k;i+)temp=Row_min(node,i,temp1);for(j=0;j<node->k;j+) node->cij-=temp;sum+=temp

16、;for(j=0;j<node->k;j+)temp=Col_min(node,j,temp1);for(i=0;i<node->k;i+) node->cij-=temp;sum+=temp;return sum;ElemType Edge_sel(Node *node,int &vk,int v1)计算Dkl,选择搜索分支的边d=0;ElemType *row_value=new ElemTypenode->k;ElemType *col_value=new ElemTypenode->k;for(i=0;i<node->k;i

17、+)每一行的次小值Row_min(node,i,row_valuei);for(i=0;i<node->k;i+)每一列的次小值Col_min(node,i,col_valuei);for(i=0;i<node->k;i+)for(j=0;j<node->k;j+)if(node->cij=0)temp=row_valuei+col_valuei;if(temp>d)d=temp;vk=i;v1=j;/对路程矩阵所有的0元素值计算相应的temp值求最大的temp值于d/保存相应的行、列号元素上移元素左移元素上移及左移当前行转换为原始行 vk1/原

18、始行vk1置删除标志/vk1之后的原始行，其对应的当前行号减1当前列v1转换为原始列vl1原始列vl1置删除标志/vl1之后的原始列，其对应的当前列号减1/修改vk及其后的当前行的对应原始行号修改v1及其后的当前列的对应原始行号当前矩阵的阶数减1当前行号转换为原始行号当前列号转换为原始列号/登记回路顶点邻接表delete row_value;delete col_value;return d;)void Del_rowcol(Node *node,int vk,int v1)删除路程矩阵的第vk行和第v1列的所有元素for(i=vk;i<node->k-1;i+)for(j=0;j

19、<v1;j+)node->cij=node->ci+1j;for(j=v1;j<node->k-1;j+)for(i=0;i<vk;i+)node->cij=node->cij+1;for(i=vk;i<node->k-1;i+)for(j=v1;j<node->k-1;j+)node->cij=node->ci+1j+1;vk1=node->init_rowvk;node->row_curvk1=-1;for(i=vk1+1;i<n;i+)node->row_curi-;vl1=nod

20、e->init_colv1;node->col_curvl1=-1;for(i=vl1+1;i<n;i+)node->col_cur-;for(i=vk;i<node->k;i+)node->init_rowi=node->init_rowi+1;for(i=v1;i<node->k;i+)node->init_coli=node->init_coli+1;node->k-;)void Edge_byp(Node *node,int vk,int vl)登记回路顶点邻接表，旁路有关的边vk=init_rowvk;vl

21、=init_colvl;node->advk=vl;k=node->row_curvl;l=node->col_curvk;if(k>=0)&&(l>=0)node->ckl=MAX_V ALUE_OF_TYPE;Node * Initial(ElemType c,int n)初始化Node *node=new Node;for(i=0;i<n;i+)for(j=0;j<n;j+)node->cij=cij;for(i=0;i<n;i+)node->init_rowi=i;node->init_coli=i

22、;/vl转换为当前行号 k/vk转换为当前列号l当前行、列号均处于当前矩阵中旁路相应的边分配结点缓冲区复制路程矩阵的初始数据/建立路程矩阵原始行、列号与初始行、列号对应的关系node->row_cur=i;node->col_cur=i;for(i=0;i<n;i+)回路顶点邻接表初始化为空node->adi=-1;node->k=n;return node;返回结点指针(4)TSP、可题分支限界算法voidTSP(ElemType c100100,int n,int *ad)初始化队列初始化父亲结点x结点归约路程矩阵/选择分支方向并计算 Dkl/建立分支结点z结

23、点（右儿子结点）*znode=*xnode;bound=MAX_V ALUE_OF_TYPE;InitQueue(qbase);xnode=Initial(c,n);xnode->w=Array_red(xnode);while(xnode->k!=0)d=Edge_sel(xnode,vk,vl);znode=new Node;/x结点数据复制给z结点旁路结点的边归约z结点路程矩阵计算z结点的下界若下界小于当前可行解最优值将z结点插入优先队列否则，剪去该结点/建立分支节点-y结点（左儿子结点）/x结点数据复制到 y结点登记回路邻接表，旁路有关的边删除结点y路程矩B$当前vk行vl

24、歹U归约y结点路程矩阵计算y结点的下界/路程矩B$只剩2阶若下界小于当前可行解最优值/y结点插入优先队列更新当前可行解最优值ALUE_OF_TYPE;znode->cvkvl=MAX_V Array_red(znode);znode->w=xnode->w+d;if(znode->w<bound)EnQueue(qbase,znode); else delete znode; ynode=new Node; *ynode=*xnode;Edge_byp(ynode,vk,vl); Del_rowcol(ynode,vk,vl); ynode->w=Array

25、_red(xnode); ynode->w+=xnode->w;if(ynode->k=2)if(ynode->c00=0)&&(ynode->c11=0)ynode->adynode->init_row0=ynode->init_col0;ynode->adynode->init_row1=ynode->init_col1; else ynode->adynode->init_row0=ynode->init_col1;ynode->adynode->init_row1=ynode

26、->init_col0;登记最后的两条边ynode->k=0; if(ynode->w<bound)EnQueue(qbase,ynode);if(ynode->k=0)释放队列节点缓冲区bound=ynode->w;else delete ynode;xnode=DeQueue(qbase);w=xnode->w;for(i=0;i<n;i+)adi=xnode->adi;delete xnode;while(qbase.front!=qbase.rear)否则剪去y结点取优先队列首元素保存最短路线长度保存路线的顶点邻接表释放x结点缓冲区

27、xnode=DeQueue(qbase);delete xnode;)cout<<"The way is:"for(int m=0;m<n;m+)cout<<adm;cout<<endl;cout<<"The length of the way is:"<<w<<endl;)(5)主函数的伪码算法void main()cout<< " Please insert the number of cities:“ ；cin>>n;cout<&l

28、t; " Please insert the distance between one city and another: for(i=0;i<n;i+)for(j=0;j<n;j+)cin>>cij;cout<< " ” ; cout<<endl;TSP(c, n, ad);/main(6)函数调用关系图main5 .调试分析(1)使用分支限界法求解的过程中，将动态地生成很多结点，用结点表来存放动态生成的结 点信息。因此必须按路程的下界来确定搜索的方向，因此可以用优先队列或堆来维护结点表。 在此使用优先队列来维护结点表。(2

29、)算法的时间复杂度分析TSP算法的时间估计如下：a.初始化父亲结点，归约父亲结点路程矩阵，都需要O(n2)时间。b. while循环体的执行次数取决于所搜索的结点个数，假定所搜索的借点数为c。在while循环内部，选择分支方向需要 O(n2)时间。c.把x结点数据复制到z结点(这里包括整个路程矩阵的复制工作)，归约z结点的路 程矩阵，都需要O(n2)时间。d.把z结点插入到优先队列，在最坏的情况下需要 0(c)时间。e.把x结点复制到y结点，同样需要O(n2)时间。f.登记回路邻接表，旁路有关的边，只需 O(1)时间。g.删除y结点路程矩阵当前vk行vl歹I，归约y结点的路程矩阵，这些操作都需

30、要O(n2) 时间。h.把y结点插入队列，删除队列首元素，都需要O(c)时间。i.其余的花费为O(1)时间。j.因此，整个while循环在最坏的情况下需要 O(cn2)时间。k.最后，在算法白尾部，for循环保存路线的顶点邻接表于数组 ad中作为算法的返回值， 需要O(n)时间。l.释放队列缓冲区的while循环在最坏情况下需要O(c)时间。所以，整个算法的时间复杂度为 O(cn2)(3)算法的空间复杂度分析算法所需要的空间，主要花费在结点的存储空间。每个结点需要O(n2)空间存放路程矩阵， 而存放路程矩阵的原始行、列号和当前行、列号的对应关系的映射表，以及回路的顶点邻接 表仅需要O(n)空间

31、。因此，每个结点相应需要 O(n2)空间。所以，算法的空间复杂度为O(cn2)空间。6 .使用说明程序运行后用户根据提示输入城市的数目n,城市彼此之间的距离(存放在 cnn数组中)。程序将串联起所有城市并回到最初起点的最短回路以及整个路线的长度输出出来。7 .测试结果(1)输入数据：5, 999, 25, 41, 32, 28, 25, 999, 18, 31, 26, 41 , 18, 999, 7, 1, 32, 31,7, 999, 11, 28, 26, 1 ,11, 999 (999代表输出结果:nnX(2)输入数据：5, 1 , 1, 1, 1, 1, 1, 1, 1, 1, 1,

32、 1 , 1 , 1 , 1, 1, 1 , 1 , 1 , 1, 1 , 1 , 1 , 1 ,1 , 1输出结果：(3)输入数据：3, 1 , 1 , 1 , 1, 1, 1, 1, 1, 1输出结果：999;代表8用此数据结构来定义结点中所使用的数据/路程矩阵/路程矩阵的当前行映射为原始行/路程矩阵的当前列映射为原始列路程矩阵的原始行映射为当前行/路程矩阵的原始列映射为当前列回路顶点邻接表当前路程矩阵的阶结点的下界8.附录（带注释的源程序）(1)文件 others.h#include<iostream>using namespace std;typedef int ElemT

33、ype;#define MAX_V ALUE_OF_TYPEtypedef struct Node_dataElemType c100100;intinit_row100;intinit_col100;int row_cur100;intcol_cur100;int ad100;intk;ElemType w;struct Node_data *next;队列链指针Node;typedef struct QNodeNode *data;/ 数据域struct QNode *next;指针域QNode,*QueuePtr;typedef structQueuePtr front;头指针，指向链队

34、头结点QueuePtr rear;尾指针，指向链队列最后一个结点LinkQueue;void InitQueue(LinkQueue &Q)/构造一个空链队列 QQ.front=Q.rear=new QNode;Q.front->next=NULL;/InitQueuevoid EnQueue(LinkQueue &Q,Node *e)插入一个指针e到链队列Q中，成为新的队尾指针QueuePtr p;p=new QNode;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;/EnQueueNode *DeQue

35、ue(LinkQueue &Q)/若链队列Q为空，则返回NULL ;否则返回指向数据的指针QNode *p;Node *e;if(Q.front->next=NULL)return NULL;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;delete p;return e;/DeQueueElemType Row_min(Node *node,int row,ElemType &second)计算路程矩阵行的最小值ElemType temp;in

36、t i;if(node->crow0<node->crow1)temp=node->crow0;second=node->crow1;else temp=node->crow1;second=node->crow0;for(i=2;i<node->k;i+)if(node->crowi<temp)second=temp;temp=node->crowi;else if(node->crowi<second)second=node->crowi;return temp;ElemType Col_min(No

37、de *node,int col,ElemType &second)计算路程矩阵列的最小值ElemType temp;int i;if(node->c0col<node->c1col)temp=node->c0col;second=node->c1col;else temp=node->c1col;second=node->c0col;)for(i=2;i<node->k;i+)if(node->cicol<temp)second=temp;temp=node->cicol;)else if(node->ci

38、col<second) second=node->cicol;)return temp;)ElemType Array_red(Node *node)归约node所指向的结点的路程矩阵int i,j;ElemType temp,temp1,sum=0;行归约行归约常数行归约常数累计列归约列归约常数for(i=0;i<node->k;i+)temp=Row_min(node,i,temp1);for(j=0;j<node->k;j+) node->cij-=temp;sum+=temp;)for(j=0;j<node->k;j+)temp=C

39、ol_min(node,j,temp1);for(i=0;i<node->k;i+)node->cij-=temp;sum+=temp;)return sum;)ElemType Edge_sel(Node *node,int &vk,int v1)计算Dkl,选择搜索分支的边int i,j;ElemType temp,d=0;ElemType *row_value=new ElemTypenode->k;ElemType *col_value=new ElemTypenode->k;for(i=0;i<node->k;i+)Row_min(n

40、ode,i,row_valuei);for(i=0;i<node->k;i+)Col_min(node,i,col_valuei);for(i=0;i<node->k;i+)for(j=0;j<node->k;j+)if(node->cij=0)temp=row_valuei+col_valuei;if(temp>d)d=temp;vk=i;v1=j;delete row_value;delete col_value;return d;void Del_rowcol(Node *node,int vk,int v1)每一行的次小值每一列的次小值/

41、对路程矩阵所有的0元素值计算相应的temp值求最大的temp值于d保存相应的行、列号删除路程矩阵的第vk行和第v1列的所有元素int i,j,vk1,vl1;for(i=vk;i<node->k-1;i+)元素上移for(j=0;j<v1;j+)node->cij=node->ci+1j;for(j=v1;j<node->k-1;j+)元素左移for(i=0;i<vk;i+)node->cij=node->cij+1;for(i=vk;i<node->k-1;i+)元素上移及左移for(j=v1;j<node->

42、;k-1;j+)当前行号转换为原始行号当前列号转换为原始列号登记回路顶点邻接表/vl转换为当前行号 k/vk转换为当前列号l当前行、列号均处于当前矩阵中旁路相应的边node->cij=node->ci+1j+1;vk1=node->init_rowvk;node->row_curvk1=-1;for(i=vk1+1;i<5;i+)node->row_curi-;vl1=node->init_colv1;node->col_curvl1=-1;for(i=vl1+1;i<5;i+)node->col_curi-;for(i=vk;i&l

43、t;node->k;i+)node->init_rowi=node->init_rowi+1;for(i=v1;i<node->k;i+)node->init_coli=node->init_coli+1;node->k-;void Edge_byp(Node *node,int vk,int vl)登记回路顶点邻接表，旁路有关的边int k,l;vk=node->init_rowvk;vl=node->init_colvl;node->advk=vl;k=node->row_curvl;l=node->col_cu

44、rvk;if(k>=0)&&(l>=0)node->ckl=MAX_V ALUE_OF_TYPE;Node * Initial(ElemType c100100,int n)初始化Node *node=new Node; /分配结点缓冲区int i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)node->cij=cij;当前行转换为原始行 vk1原始行vk1置删除标志/vk1之后的原始行，其对应的当前行号减当前列v1转换为原始列vl1原始列vl1置删除标志/vl1之后的原始列，其对应的当前列号减1修改vk及其后的当前行的对

45、应原始行号修改v1及其后的当前列的对应原始行号当前矩阵的阶数减1复制路程矩阵的初始数据for(i=0;i<n;i+)/建立路程矩阵原始行、列号与初始行、列号对应的关系node->init_rowi=i;node->init_coli=i;node->row_curi=i;node->col_curi=i;)for(i=0;i<n;i+)node->adi=-1;node->k=n;return node;)(2)文彳tsp.h#include "others.h回路顶点邻接表初始化为空返回结点指针void TSP(ElemType c1

46、00100,int n,int *ad) int i,vk=0,vl=0;ElemType d,w,bound=MAX_V ALUE_OF_TYPE;Node *xnode;Node *ynode;Node *znode;父亲结点指针儿子结点指针儿子结点指针LinkQueue qbase;InitQueue(qbase);优先队列首指针初始化队列ALUE_OF_TYPE;初始化父亲结点x结点归约路程矩阵/选择分支方向并计算 Dkl/建立分支结点z结点（右儿子结点）/x结点数据复制给z结点旁路结点的边归约z结点路程矩阵计算z结点的下界若下界小于当前可行解最优值xnode=Initial(c,n);xnode->w=Array_red(xnode);while(xnode->k!=0)d=Edge_sel(xnode,vk,vl);znode=new Node;*znode=*xnode;znod