贪心算法Tsp实习报告1

1、浙江农林大学信息工程学院课程实习报告课程名称:班 级:课程名称:班 级:题 目:组 长:成 员:指导教师:电信*班TSP问题的贪心算法*2014年6月17日 TOC o 1-5 h z HYPERLINK l bookmark26 o Current Document 课程实习目的1 HYPERLINK l bookmark30 o Current Document 贪心算法实习的目的1 HYPERLINK l bookmark33 o Current Document TSP问题的解决及贪心算法的应用1 HYPERLINK l bookmark36 o Current Document 贪心

2、算法的概念1 HYPERLINK l bookmark39 o Current Document 课程实习题目描述和要求1 HYPERLINK l bookmark43 o Current Document TSP问题介绍1 HYPERLINK l bookmark47 o Current Document 贪心算法的特性2贪心算法的特性：2贪心算法的缺陷2 HYPERLINK l bookmark58 o Current Document 关于贪心算法的备注2 HYPERLINK l bookmark61 o Current Document 课程实习报告内容2 HYPERLINK l bo

3、okmark65 o Current Document 了解并掌握贪心算法2 HYPERLINK l bookmark69 o Current Document 设计内容3 HYPERLINK l bookmark72 o Current Document 问题描述3 HYPERLINK l bookmark76 o Current Document 设计思想3 HYPERLINK l bookmark80 o Current Document 需求分析3程序的功能：3输入输出的要求4 HYPERLINK l bookmark84 o Current Document 贪心算法解决TSP问题的

4、流程图4 HYPERLINK l bookmark87 o Current Document 贪心算法解决TSP问题的步骤5 HYPERLINK l bookmark90 o Current Document 总结5 HYPERLINK l bookmark94 o Current Document 任务分配5课程实习目的1.1贪心算法实习的目的此次实习通过贪心算法来解决TSP问题。假设有n个城市，任意两个城市之间都有路 径相通，并设第i个城市与第j个城市之间的距离为Dij，求从某个城市出发经过所有城市 并且只经过一次又回到原点的都短距离。首先，本文运用Visual C+集成开发环境将贪心 算

5、法编程实现，并解决TSP问题。然后通过改变各个参数的值来观察计算结果，接着对运 算结果的进行对比分析，从而验证各个参数对贪心算法的影响。1.2 TSP问题的解决及贪心算法的应用旅行商问题(Traveling Salesman Problem, TSP)是一个著名的组合优化问题，该类问题具 有非常广泛的运用背景。如物流的调度问题、数控机床上的最优钻孔路线的选取、电路板的 焊接都属于旅行商问题。因此旅行商问题受到了各方面的关注，有效解决TSP问题在计算 理论和实际应用上都有很高的价值。目前解决TSP的主要方法有贪心算法、遗传算法、模 拟退火算法、蚁群算法、启发式搜索法、Hopfield神经网络算、

6、二叉树描述算法。此次实习 主要介绍了应用贪心算法来解决TSP问题。1.3贪心算法的概念贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算 法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解 或者是整体最优解的近似解。为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪心算 法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择 函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行， 那

7、么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是 否构成解。如果贪心算法正确工作，那么找到的第一个解通常是最优的。课程实习题目描述和要求TSP问题介绍TSP问题，也称旅行商问题。已知n个城市之间的相互距离，现有一个推销员必须遍访 这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他的访问顺 序，可使其旅行的总长度最短。用图论的术语来说，假设有一个图g=(v , e),其中v是顶点集， e是边集，设d=dij是由顶点i和顶点j之间距离所组成的距离矩阵，旅行商问题就是要求出 一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对

8、称旅行 商问题(dij = dji)任意(i, j=1,2,3，n)和非对称旅行商问题皿尹dj)任意i , j=(1,2,3,，n)。 城市v=v1,v2,v3, ,vn的一个访问顺序为t(t1,t2,t3, ,ti,tn),其中tiev(i=1,2,3,n)，且记t（n+i）=ti，则旅行商问题的数学模型为：min = ad（t，t（iKR=0, ,9）。2.2贪心算法的特性贪心算法的特性：（1） 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的 集合：比如不同面值的硬币。（2） 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选 对象，另一个包

9、含已经被考虑过但被丢弃的候选对象。（3） 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时 的解决方法是否最优。（4） 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添 加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优 性。（5） 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。（6） 最后，目标函数给出解的值。贪心算法的缺陷贪心算法（又称贪心算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算 法不是对所有问题都能得到整体

10、最优解，但对范围相当广泛的许多问题他能产生整体最优解 或者是整体最优解的近似解。2.3关于贪心算法贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的 贪心算法。贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式所以需 要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一 类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么， 随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）。课程实习报告内容了解并掌握贪心算法贪心算法（Greedy algorithm）是一种对某

11、些求最优解问题的更简单、更迅速的设计技 术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作 最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费 的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将 所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解， 虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以 贪心法不要回溯。贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将 这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输

12、入一个量。如果这个输入和 当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加 到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪心算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取 的，但实际上，用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问 题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪心算法的 核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度 标准后，用贪心算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来 达到，

13、根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这 个选择后产生的相应的子问题。每做一次贪心选择就将所求问题简化为一个规模更小的子问 题，最终可得到问题的一个整体最优解。3.2设计内容问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求 所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为 人知的问题。设计思想对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有 可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为O(n!)， 当n大到一定程度后是不可解的。所以我

14、们选取贪心算法，但我们必须清楚地认识到贪心算 法依旧有着其缺陷(即在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不 从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有 问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最 优解的近似解)。3.3需求分析程序的功能：求一个旅行家要穿过多个城市，已知城市个数，以及城市间距，求出最短路径解和最短 路径长度。3.3.2 输入输出的要求输入城市数目N为正整数，城市间距离最小值为0，输入起始城市的数字，输入共有 N+2个数值；输出最优解和最优值。3.4贪心算法解决TSP问题的流程图3.5

15、贪心算法解决TSP问题的步骤第一步：了解并掌握问题的关键。第二步：建立数学模型来描述问题。第三步：把求解的问题分成若干个子问题。第四步：对每一子问题求解，得到子问题的局部最优解。第五步：把子问题的解局部最优解合成原来解问题的一个解。第六步：得出结论。总结数据结构实习能够锻炼学生综合运用所学知识并利用课外知识，发现、提出、分析并解 决实际问题的能力，是对学生实际工作能力的具体训练和考察过程。它不但考察我们运用数 据结构知识解决问题的能力，还考察了我们了解问题，查找资料的能力。在这几天里我不仅 巩固了之前所学，还学到了许多书本上没有的知识。在确立问题之后，我通过图书馆查找、 上网搜索等多种途径收集课题相关资料并认真整理掌握算法。并用一段时间的编写代码，虽 然第一次运行出现了问题，但我并没有放弃，仔细地检查，发现并解决了问题。在一番调试 后，代码最终能稳定快速地运行。这次实习让我懂得了理论与实践结合的重要性，让我了解了如何快速正确的解决问题。 虽然编写代码的过程中出现了一些小插曲，但是这些都将成为我的经验，防止我以后再次出