《贪心算法Tsp实习总结报告.pdf》由会员分享，可在线阅读，更多相关《贪心算法Tsp实习总结报告.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、浙江农林大学信息工程学院课 程 实习 报 告课程名称：数据结构实习 班 级：电信*班 题 目：TSP 问题的贪心算法 组 长：*成 员：*指导教师：*2014 年 6 月 17 日目 录浙江农林大学信息工程学院课程大作业报告11.课程实习目的1.1贪心算法实习的目的此次实习通过贪心算法来解决 TSP 问题。假设有 n 个城市，任意两个城市之间都有路径相通，并设第 i 个城市与第 j 个城市之间的距离为 Dij，求从某个城市出发经过所有城市并且只经过一次又回到原点的都短距离。首先，本文运用 Visual C+集成开发环境将贪心算法编程实现，并解决 TSP 问题。然后通过改变各个参数的值来观察计算
2、结果，接着对运算结果的进行对比分析，从而验证各个参数对贪心算法的影响。1.2TSP 问题的解决及贪心算法的应用旅行商问题(Traveling Salesman Problem,TSP),是一个著名的组合优化问题，该类问题具有非常广泛的运用背景。如物流的调度问题、数控机床上的最优钻孔路线的选取、电路板的焊接都属于旅行商问题。因此旅行商问题受到了各方面的关注，有效解决 TSP 问题在计算理论和实际应用上都有很高的价值。目前解决 TSP 的主要方法有贪心算法、遗传算法、模拟退火算法、蚁群算法、启发式搜索法、Hopfield 神经网络算、二叉树描述算法。此次实习主要介绍了应用贪心算法来解决 TSP 问
3、题。1.3贪心算法的概念贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪心算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集
4、合是否构成解。如果贪心算法正确工作，那么找到的第一个解通常是最优的。2.课程实习题目描述和要求2.1TSP 问题介绍TSP 问题，也称旅行商问题。已知 n 个城市之间的相互距离，现有一个推销员必须遍访这 n 个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他的访问顺序，可使其旅行的总长度最短。用图论的术语来说，假设有一个图 g=(v,e),其中 v 是顶点集，e 是边集，设 d=dij是由顶点 i 和顶点 j 之间距离所组成的距离矩阵，旅行商问题就是要求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题(dij=dji)任意（i,j=1,
5、2,3,n）和非对称旅行商问题(dijdji)任意 i,j=（1,2,3,n）。城 市v=v1,v2,v3,vn的 一 个 访 问 顺 序 为t(t1,t2,t3,ti,tn),其中 tiv(i=1,2,3,n)，且记 t(n+1)=t1，则旅行商问题的数学模型为：min=d(t(i),t(i+1)（i=0,9）。2.2贪心算法的特性2.2.1贪心算法的特性：（1）有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。（2）随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。（3）有
6、一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。（4）还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。（5）选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。（6）最后，目标函数给出解的值。2.2.2贪心算法的缺陷贪心算法（又称贪心算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优
7、解或者是整体最优解的近似解。2.3关于贪心算法贪心算法当然也有正确的时候。求最小生成树的 Prim 算法和 Kruskal算法都是漂亮的贪心算法。贪心法的应用算法有 Dijkstra的单源最短路径和 Chvatal 的贪心集合覆盖启发式所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）。3.课程实习报告内容3.1了解并掌握贪心算法贪心算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技
8、术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费浙江农林大学信息工程学院课程大作业报告3的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心法不要回溯。贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如
9、果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪心算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪心算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪心算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来
10、是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪心选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。3.2设计内容3.2.1问题描述所谓 TSP 问题是指旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。3.2.2设计思想对于 TSP 问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解 TSP问题的时间复杂度为(n!)，当 n 大到一定程度后是不可解的。所以我们
11、选取贪心算法，但我们必须清楚地认识到贪心算法依旧有着其缺陷（即在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解）。3.3需求分析3.3.1程序的功能：求一个旅行家要穿过多个城市，已知城市个数，以及城市间距，求出最短路径解和最短路径长度。3.3.2输入输出的要求输入城市数目 N 为正整数，城市间距离最小值为 0，输入起始城市的数字，输入共有 N+2个数值；输出最优解和最优值。3.4贪心算法解决 TSP 问题的流程图
12、 N Y输入城市数与间距，并输入起始城市遍历第一个可行回路的解和值为当前最优解和最优值继续遍历并与当前最优值和最优解比较，更优则替换到达结束点？开始输出最优质和最优解结束浙江农林大学信息工程学院课程大作业报告53.5贪心算法解决 TSP 问题的步骤第一步：了解并掌握问题的关键。第二步：建立数学模型来描述问题。第三步：把求解的问题分成若干个子问题。第四步：对每一子问题求解，得到子问题的局部最优解。第五步：把子问题的解局部最优解合成原来解问题的一个解。第六步：得出结论。4.总结数据结构实习能够锻炼学生综合运用所学知识并利用课外知识，发现、提出、分析并解决实际问题的能力，是对学生实际工作能力的具体训
13、练和考察过程。它不但考察我们运用数据结构知识解决问题的能力，还考察了我们了解问题，查找资料的能力。在这几天里我不仅巩固了之前所学，还学到了许多书本上没有的知识。在确立问题之后，我通过图书馆查找、上网搜索等多种途径收集课题相关资料并认真整理掌握算法。并用一段时间的编写代码，虽然第一次运行出现了问题，但我并没有放弃，仔细地检查，发现并解决了问题。在一番调试后，代码最终能稳定快速地运行。这次实习让我懂得了理论与实践结合的重要性，让我了解了如何快速正确的解决问题。虽然编写代码的过程中出现了一些小插曲，但是这些都将成为我的经验，防止我以后再次出现这种情况。总之，这次实习让我收获颇丰。5.任务分配排序姓名任务量承担任务1*100%选题，收集资料，编写调试代码，撰写报告参考文献：1百度百科，贪心算法，http:/ 在 中，独立完成 内容。本人自评等级为 。签名：日期：课程实习小组长评分表 同学在本些课程实习中表现 。等级拟定为_。签名：日期：课程实习教师评分表 同学在本些课程实习中表现 。等级定为_。签名：日期：