1. 问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并且要求 所走的路程最短该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为 人知的问题2. 基本要求(1) 上网查找TSP问题的应用实例；(2) 分析求TSP问题的全局最优解的时间复杂度；(3) 设计一个求近似解的算法；(4) 分析算法的时间复杂度3. 提交报告课程设计报告提交内容包括：(1) 问题描述； (2) 需求分析； (3) 概要设计； (4) 详细设计； (5) 调试分析； (6) 使用说 明； (7) 测试结果； (8) 附录(带注释的源程序)参见“数据结构课程设计概述.pdf ”和“数据结构课程设计示例.pdf”指导教师(签字)： 系主任(签字)： 批准日期： 2014 年 月 日1．问题描述(1) 题目要求旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次，最终要回到出发的城市，求 出最短路径用图论的术语来说，假如有一个图G=(V,E),其中V是顶点集，E是边集，设D=(dj是由 顶点i和顶点j之间的距离所组成的距离矩阵°TSP问题就是求出一条通过每个顶点且每个顶 点只通过一次的具有最短距离的回路。
2)基本要求a. 上网查找TSP问题的应用实例；b. 分析求TSP问题的全局最优解的时间复杂度;c. 设计一个求近似解的算法；d. 分析算法的时间复杂度3)测试数据5个城市的TSP问题：注：由于矩阵所表示的是两个城市之间的距离，所以该矩阵为对称矩阵0 12 3 4路程矩阵如图所示：82541322825818312641188713231781128261118最短路径为 v0v1v4v2v32.需求分析(1) 本程序用于求解n个结点的最短哈密尔顿回路问题2) 程序运彳丁后显示提示信息—“Please insert the number of cities:”，例如用户输入5,则表示结 点n的值为5；接下来程序输出提示信息一“Please insert the distance between one city and another:”，例如用户输入测试数据中给出的路程矩阵，表示任意两个城市之间的距离，比 如第一个城市到第0 个城市之间的距离为 253) 用户输入数据完毕，程序将输出运算结果4) 测试数据均为正数，其中用999来表示两个城市之间距离为x3．概要设计为了实现上述程序功能，使用优先队列来维护结点表，因此需要图和队列两个抽象数据类 型。
1)图的抽象数据类型定义ADT Graph{Data: 具有相同类型的数据元素的集合，称为顶点集Relation： 顶点偶对的有穷集合Operation：CreateGraph(&G,V,VR)初始条件：V是图中顶点集合,VR是图中顶点偶对集合操作条件：按照V和VR的定义构造图GDestroyGraph(&G)初始条件：图G已经存在操作结果：销毁GLocateVex(G,u)初始条件：图G已经存在，u和G中顶点有相同类型操作结果：如果G中存在u,则返回u在G中的位置；否则返回相应信息GetVex(G,v)初始条件：图G已经存在，v是G中某个顶点操作结果：返回v的值PutVex(&G,v,value)初始条件：图G已经存在，v是G中顶点操作结果：对v赋值valueFirstAdjvex(G,v)初始条件：图G已经存在，v是G中顶点操作结果：返回v的第一个邻接顶点如果在G中没有邻接顶点，则返回相应信息NextAdjvex(G,v,w)初始条件：图G已经存在，v是G中顶点w是v的邻接顶点操作结果：返回v的下一个邻接顶点如果W是v的最后一个邻接点，则返回相应信息InsertVex(&G,v,w)初始条件：图G已经存在，v和w是G中顶点。
操作结果：在G中添加vDeleteVex(&Gv)初始条件：图G已经存在，v是G中顶点操作结果：删除G中顶点v及其相关的边InsertEdge(&G,v,w) 初始条件：图G已经存在，v和w是G中顶点操作结果：在G中添力d;如果G是无向图，则还增添tw,v>oDeleteEdge(&G,v,w)初始条件：图G已经存在，v和w是G中顶点操作结果：在G中删除vv,w>;如果G是无向图，则还删除w,v>DFSTraverse(G,v)初始条件：图G已经存在，v是G中顶点操作结果：从v起深度访问GBFSTraverse(G,v)初始条件：图G已经存在，v是G中顶点 操作结果：从v起广度访问G}ADT Graph2)队列的抽象数据类型ADT Queue{Data:具有相同数据类型的及先进先出特性的数据元素集合Relation：相邻数据元素具有前驱和后继的关系Operation：InitQueue(&Q)初始条件：无操作结果：创造一个空队列QDestroyQueue(&Q)初始条件：队列Q已经存在操作结果：销毁2ClearQueue(&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算法模块辅函数模块4．详细设计(1) 元素类型、结点类型和指针类型、变量和数据结构声明Node*xnode;//父亲结点指针Node*ynode;//儿子结点指针Node*znode;//儿子结点指针Node*qbase;//优先队列首指针ElemType bound；//当前可行解的最优值typedef int ElemType; //元素类型#define MAX_VALUE_OF_TYPE 999; 〃代表城市顶点用数字0, 1, 2,……,n-1编号在搜索的过程中，各个结点的数据是动态变 化的，互不相同，发生回溯时，必须使用结点中原来的数据。
因此，每个结点的数据必须是 局部与该结点的用如下的数据结构来定义结点中所使用的数据：typedef struct Node{ElemType c[100][100];//路程矩阵intinit_row[100];//路程矩阵的当前行映射为原始行intinit_col[100];//路程矩阵的当前列映射为原始列intcur_row[100];//路程矩阵的原始行映射为当前行intcur_col[100];//路程矩阵的原始列映射为当前列intad[100];//回路顶点邻接表intk;//当前路程矩阵的阶ElemType w;//结点的下界struct Node *next;//队列链指针}Node;2)队列类型//数据域//指针域//头指针,指向链队头结点//尾指针,指向链队列最后一个结点typedef struct QNode{ Node *data;struct QNode *next; }QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;程序中所用到的关于优先队列基本操作实现的伪码算法如下void InitQueue(LinkQueue &Q){〃构造一个空链队列.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 *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;}//DeQueue(3)辅助函数的实现(共 7 个)ElemType Row_min(Node *node,int row,ElemType &second){//计算路程矩阵行的最小值if(node->c[row][0]c[row][1]){temp=node->c[row][0];second=node->c[row][1];}else {temp=node->c[row][1];second=node->c[row][0];for(i=2;ik;i++){ if(node->c[row][i]c[row][i];}else if(node->c[row][i]c[row][i];}return temp;}ElemType Col_min(Node *node,int col,ElemType &second){ //计算路程矩阵列的最小值 if(node->c[0][col]c[1][col]){ temp=node->c[0][col];second=node->c[1][col];}else { temp=node->c[1][col];second=node->c[0][col];} for(i=2;ik;i++){ if(node->c[i][col]c[i][col];}else if(node->c[i][col]c[i][col];}return temp;}ElemType Array_red(Node *node){//归约 node 所指向的结点的路程矩阵 sum=0;for(i=0;ik;i++){temp=Row_min(node,i,temp1);for(j=0;jk;j++) node->c[i][j]-=temp; sum+=temp;}for(j。