TSP问题的解决与实现及艾滋病神经系统感染临床与影像学表现.pdf
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=(d)是
ij
由顶点i和顶点j之间的距离所组成的距离矩阵。TSP问题就是求出一条通过每个顶点且每
个顶点只通过一次的具有最短距离的回路。
(2)基本要求
a.上网查找TSP问题的应用实例;
b.分析求TSP问题的全局最优解的时间复杂度;
c.设计一个求近似解的算法;
d.分析算法的时间复杂度。
(3)测试数据
5个城市的TSP问题:
注:由于矩阵所表示的是两个城市之间的距离,所以该矩阵为对
称矩阵
路程矩阵如图所示:01234
0
∞25413228
1
2
25∞183126
3
4118∞71
4
32317∞11
2826111∞
最短路径为vvvvv
01423
2.需求分析
(1)本程序用于求解n个结点的最短哈密尔顿回路问题。
(2)程序运行后显示提示信息—“Pleaseinsertthenumberofcities:”,例如用户输入5,则表
示结点n的值为5;接下来程序输出提示信息—“Pleaseinsertthedistancebetweenonecity
andanother:”,例如用户输入测试数据中给出的路程矩阵,表示任意两个城市之间的距
离,比如第一个城市到第0个城市之间的距离为25。
(3)用户输入数据完毕,程序将输出运算结果。
(4)测试数据均为正数,其中用999来表示两个城市之间距离为∞。
3.概要设计
为了实现上述程序功能,使用优先队列来维护结点表,因此需要图和队列两个抽象数据类
型。
(1)图的抽象数据类型定义
ADTGraph{
Data:
具有相同类型的数据元素的集合