TSP问题的解决与实现讲解

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=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵。TSP问题就是求出一条通过每个顶点且每个顶点只通过一次的具有最短距离的回路。

（2）基本要求

a. 上网查找TSP问题的应用实例；

b. 分析求TSP问题的全局最优解的时间复杂度； c. 设计一个求近似解的算法； d. 分析算法的时间复杂度。

（3）测试数据

5个城市的TSP问题：

注：由于矩阵所表示的是两个城市之间的距离，所以该矩阵为对称矩阵 路程矩阵如图所示：

0 2 3 1 4

0 ∞ 25 41 32 28 1 25 ∞ 18 31 26 2 41 18 ∞ 7 1 ∞ 11 3 32 31 7 28 26 1 11 ∞ 4

最短路径为v0v1v4v2v3

2.需求分析

（1）本程序用于求解n个结点的最短哈密尔顿回路问题。

（2）程序运行后显示提示信息—“Please insert the number of cities:”，例如用户输入5，则表示结

点n的值为5；接下来程序输出提示信息—“Please insert the distance between one city and

another:”，例如用户输入测试数据中给出的路程矩阵，表示任意两个城市之间的距离，比

如第一个城市到第0个城市之间的距离为25。 (3)

用户输入数据完毕，程序将输出运算结果。

（4）测试数据均为正数，其中用999来表示两个城市之间距离为∞。

3．概要设计

为了实现上述程序功能，使用优先队列来维护结点表，因此需要图和队列两个抽象数据类型。

（1）图的抽象数据类型定义

ADT Graph{ Data:

具有相同类型的数据元素的集合，称为顶点集。

Relation：

顶点偶对的有穷集合。 Operation：

CreateGraph(&G,V,VR)

初始条件：V是图中顶点集合，VR是图中顶点偶对集合。 操作条件：按照V和VR的定义构造图G。 DestroyGraph(&G)

初始条件：图G已经存在。 操作结果：销毁G。 LocateVex(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。

FirstAdjvex(G,v)

初始条件：图G已经存在，v是G中顶点。

操作结果：返回v的第一个邻接顶点。如果v在G中没有邻接顶点，则返回相应信息。

NextAdjvex(G,v,w)

初始条件：图G已经存在，v是G中顶点,w是v的邻接顶点。

操作结果：返回v的下一个邻接顶点。如果w是v的最后一个邻接点，则返回相应信息。

InsertVex(&G,v,w)

初始条件：图G已经存在，v和w是G中顶点。 操作结果：在G中添加v。

DeleteVex(&G,v)

初始条件：图G已经存在，v是G中顶点。 操作结果：删除G中顶点v及其相关的边。

InsertEdge(&G,v,w)

初始条件：图G已经存在，v和w是G中顶点。

操作结果：在G中添加；如果G是无向图，则还增添。

DeleteEdge(&G,v,w)

初始条件：图G已经存在，v和w是G中顶点。

操作结果：在G中删除;如果G是无向图，则还删除。

DFSTraverse(G,v)

初始条件：图G已经存在，v是G中顶点。 操作结果：从v起深度访问G。

BFSTraverse(G,v)

初始条件：图G已经存在，v是G中顶点。 操作结果：从v起广度访问G。

}ADT Graph

（2）队列的抽象数据类型

ADT Queue{ Data:

具有相同数据类型的及先进先出特性的数据元素集合。 Relation：

相邻数据元素具有前驱和后继的关系。 Operation： InitQueue(&Q) 初始条件：无

操作结果：创造一个空队列Q。

DestroyQueue(&Q)

初始条件：队列Q已经存在。 操作结果：销毁Q。

ClearQueue(&Q)

初始条件：队列Q已经存在。 操作结果： 重置Q为空队列。

QueueLength(Q)

初始条件：队列Q已经存在。 操作结果： 返回Q的元素个数。

GetHead(Q，&e)

初始条件：队列Q已经存在并且非空。 操作结果： 用e返回Q的队头元素。

EnQueue(&Q,e)