数据结构课设TSP贪婪算法

1、数据结构课程设计设计说明书题目TSP问题贪心算法起止日期：2014年 11月 10 日 至2014 年 11月17日学生姓名滕 文 亮班 级113301 班成 绩指导教师(签字)运算机科学与工程学院2014年11月9日课程设计任务书一、设计目的熟悉各类数据结构和运算，会利用数据结构的大体操作解决一些实际问题。二、设计要求在本课程设计进程中要求学生：（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）依照课程设计的题目要求， 独立地完成各项任务， 严禁剽窃；凡发觉剽窃，剽窃者与被剽窃者皆以零分计入本课程设计成绩。凡发觉实验报告或源程序类似，涉及的全数人员皆以零分计

2、入本课程设计成绩。（3）学生在同意设计任务后，依照要求认真完成。（4）认真编写课程设计报告。三、设计内容TSP问题（贪婪法求解）1) 问题描述所谓 TSP问题是指旅行家要旅行 n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。2) 大体要求(1) 上网查找 TSP问题的应用实例；(2) 分析求 TSP问题的全局最优解的时刻复杂度；(3) 设计一个求近似解的算法；(4) 分析算法的时刻复杂度。3) 设计思想关于 TSP问题，一种最容易想到的也确信能取得最正确解的算法是穷举法，即考虑所有可能的旅行线路，从当选择

3、最正确的一条。可是用穷举法求解TSP问题的时刻复杂度为 (n!)，当 n大到必然程度后是不可解的。4）设计思想关于 TSP 问题，一种最容易想到的也确信能取得最正确解的算法是穷举法，即考虑所有可能的旅行线路，从当选择最正确的一条。可是用穷举法求解TSP 问题的时刻复杂度为( n !) ，当 n 大到必然程度后是不可解的。本实验只要求近似解，能够采纳贪婪法求解：任意选择某个城市作为起点，然后前去最近的未访问的城市，直到所有的城市都被访问而且仅被访问一次，最后返回到起点。为便于查找离某极点最近的邻接点，能够采纳邻接矩阵存储该图。算法用伪代码描述如下：1. 任意选择某个极点 v 作为起点；2. 执行

4、下述进程，直到所有极点都被访问：v= 最后一个被访问的极点；在极点 v 的邻接点中查找距离极点v 最近的未被访问的邻接点j ；访问极点j ；3. 从最后一个访问的极点直接回到起点v；四、参考文献1. 王红梅，数据结构，清华大学出版社；2. 王红梅，数据结构学习辅导与实验指导，清华大学出版社；3. 王晓东，运算机算法设计与分析，电子工业出版社。一、 TSP 问题TSP问题（ Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题， 是数学领域中闻名问题之一。假设有一个旅行商人要造访n个城市， 他必需选择所要走的途径，途径的限制是每一个城市只能造访一

5、次，而且最后要回到原先动身的城市。途径的选择目标是要求得的途径路程为所有途径当中的最小值。TSP问题是一个组合优化问题。该问题能够被证明具有NPC计算复杂性。 TSP问题能够分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都能够用一个图（Graph）来描述：V=c1, c2, , ci, , cn， i = 1,2, , n，是所有城市的集合.ci表示第 i个城市，n为城市的数量；E=(r, s): r,s V 是所有城市之间连接的集合；C = crs: r,s V 是所有城市之间连接的本钱气宇（一样为城市之间的

6、距离）；若是 crs = csr,那么该 TSP问题为对称的，不然为非对称的。一个 TSP问题能够表达为：求解遍历图 G = (V, E, C)，所有的节点一次而且回到起始节点，使得连接这些节点的途径本钱最低。二、贪婪算法贪婪算法，又名贪婪算法，是一种经常使用的求解最优化问题的简单、迅速的算法。贪婪算法老是做出在当前看来最好的选择，它所做的每一个在当前状态下某种意义上是最好的选择即贪婪选择，并希望通过每次所作的贪婪选择致使最终取得问题最优解。必需注意的是，贪婪算法不是对所有问题都能取得整体最优解，选择的贪婪策略必需具有无后效性，即某个状态以后的进程可不能阻碍以前的状态，只与当前状态有关。一、贪

7、婪算法的大体思路从问题的某一个初始解触发慢慢逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。大致步骤如下：1）成立数学模型来描述问题；2）把求解的问题分成若干个子问题3）对每一个子问题求解，得到子问题的局部最优解4）把子问题的局部最优解合成原问题的一个解二、贪婪算法的实现框架贪婪算法没有固定的算法框架，算法设计的关键是贪婪策略的选择，而贪婪策略适用的前提是：局部最优策略能致使产生全局最优解。从问题的某一初始解动身；while（能朝给定总目标前进一步）利用可行的决策，求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；3、贪婪算法存在的问题1）

8、不能保证求得的最后解是最正确的；2）不能用来求最大最小解问题；3）只能在某些特定条件约束的情况下使用，例如贪心策略必须具备无后效性等。4、典型的贪婪算法利用领域马踏棋盘、背包、装箱等。三、问题求解：TSP问题，要求先画一个旅行的线路图的图示，然后假设有个人，遍历所有的旅行的城市，考虑所有可能的旅行线路，从当选择最正确的一条。突出其顶用到的中间数据是：数组形式，初始数据是各个城市间的距离。假设咱们进行咱们的旅行打算，共五个城市，然后前去最近的未访问的城市，直到所有的城市都被访问而且仅被访问一次，最后返回到起点。要求这时遍历各城市的距离为最短距离。当咱们要求整体的最优解时，能够从它的局部最优解求的

9、，抱着如此的思想咱们从起始城市1动身比较与之最近的城市的距离是2（2号城市），由于不能返回，因此从 2号城市继续寻觅与之最近的城市（1号城市除外）的距离是4（ 3号城市），以此类推，最终在返回起始城1。补充：上面的最短距离要记录下来，求和，那么取得最短途径。若是城市数量增加，那么重复第一个城市到第二个城市那个步骤。在运算机中实现那个程序，那么要记住每一个最优城市的标号。寄存数组中，再输出最优途径。城市 1城市5城市4城市24城市3四、程序流程图：开始输入城市数与城市间距遍历树并另第一条可行回路的解和值为当前最优解和最优值继续遍历并与当前最优解和最优值比较最优则替换到达结束点NY输出最优值和最优

10、解结束五、核心源程序清单和执行结果package twl;importclass TxTsp private int cityNum; qrt(xi - xj) * (xi - xj) + (yi - yj)* (yi - yj) / ;.");for (int i = 0; i < cityNum; i+) for (int j = 0; j < cityNum; j+) +"");"print end.");public static void main(String args) throws IOException "

11、;Start.");TxTsp ts = new TxTsp(48);("." + "");.路径 :0->8->37->30->43->17->6->27->35->29->5->36->18->26->42->16->45->32->14->11->10->22->13->24->12->20->46->19->39->2->21->15->40->33->28->4->47->38->31->23->9->41->25->3->34->44->1->7->0总距离为 :12842五、总结单从求解结果来看，我个人其实仍是能同意那个解，但认真想一想，事实上那个求解结果有太多运气成份在里面，