贪心算法Tsp实习报告1

浙江农林大学信息工程学院课 程 实习 报 告课程名称： 数据构造实习 班 级： 电信*班 题 目： TSP问题的贪心算法 组 长： * 成 员： * 指引教师： * 6月 17 日目 录1.课程实习目的11.1贪心算法实习的目的11.2TSP问题的解决及贪心算法的应用11.3贪心算法的概念12.课程实习题目描述和规定12.1TSP问题简介12.2贪心算法的特性22.2.1贪心算法的特性：22.2.2贪心算法的缺陷22.3有关贪心算法的备注23.课程实习报告内容23.1理解并掌握贪心算法23.2设计内容33.2.1问题描述33.2.2设计思想33.3需求分析33.3.1程序的功能：33.3.2输入输出的规定43.4贪心算法解决TSP问题的流程图43.5贪心算法解决TSP问题的环节54.总结55.任务分派51. 课程实习目的1.1 贪心算法实习的目的本次实习通过贪心算法来解决TSP问题。假设有n个都市，任意两个都市之间均有途径相通，并设第i个都市与第j个都市之间的距离为Dij，求从某个都市出发通过所有都市并且只通过一次又回到原点的都短距离。一方面，本文运用VisualC+集成开发环境将贪心算法编程实现，并解决TSP问题。然后通过变化各个参数的值来观测计算成果，接着对运算成果的进行对比分析，从而验证各个参数对贪心算法的影响。1.2 TSP问题的解决及贪心算法的应用旅行商问题(TravelingSalesmanProblem,TSP),是一种出名的组合优化问题，该类问题具有非常广泛的运用背景。如物流的调度问题、数控机床上的最优钻孔路线的选用、电路板的焊接都属于旅行商问题。因此旅行商问题受到了各方面的关注，有效解决TSP问题在计算理论和实际应用上均有很高的价值。目前解决TSP的重要措施有贪心算法、遗传算法、模拟退火算法、蚁群算法、启发式搜索法、Hopfield神经网络算、二叉树描述算法。本次实习重要简介了应用贪心算法来解决TSP问题。1.3 贪心算法的概念贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在目前看来是最佳的选择。也就是说，不从整体最优上加以考虑，她所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范畴相称广泛的许多问题她能产生整体最优解或者是整体最优解的近似解。 为理解决问题，需要寻找一种构成解的候选对象集合，它可以优化目的函数，贪心算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有但愿构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩大集合，并检查该集合与否构成解。如果贪心算法对的工作，那么找到的第一种解一般是最优的。2. 课程实习题目描述和规定2.1 TSP问题简介TSP问题，也称旅行商问题。已知n个都市之间的互相距离，既有一种推销员必须遍访这n个都市，并且每个都市只能访问一次，最后又必须返回出发都市。如何安排她的访问顺序，可使其旅行的总长度最短。用图论的术语来说，假设有一种图g=(v , e),其中v是顶点集，e是边集，设d=dij是由顶点i和顶点j之间距离所构成的距离矩阵，旅行商问题就是规定出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题( dij = dji )任意（i , j=1,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） 有一种函数来检查一种候选对象的集合与否提供了问题的解答。该函数不考虑此时的解决措施与否最优。（4） 尚有一种函数检查与否一种候选对象的集合是可行的，也即与否也许往该集合上添加更多的候选对象以获得一种解。和上一种函数同样，此时不考虑解决措施的最优性。（5） 选择函数可以指出哪一种剩余的候选对象最有但愿构成问题的解。（6） 最后，目的函数给出解的值。2.2.2 贪心算法的缺陷贪心算法（又称贪心算法）是指，在对问题求解时，总是做出在目前看来是最佳的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范畴相称广泛的许多问题她能产生整体最优解或者是整体最优解的近似解。2.3 有关贪心算法贪心算法固然也有对的的时候。求最小生成树的Prim算法和Kruskal算法都是美丽的贪心算法。贪心法的应用算法有Dijkstra的单源最短途径和Chvatal的贪心集合覆盖启发式因此需要阐明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（由于这一类算法普及性不高，并且技术含量是非常高的，需要通过某些反例拟定随机的对象是什么，随机限度如何，但也是不能保证完全对的，只能是极大的几率对的）。3. 课程实习报告内容3.1 理解并掌握贪心算法贪心算法（Greedy algorithm）是一种对某些求最优解问题的更简朴、更迅速的设计技术。用贪心法设计算法的特点是一步一步地进行，常以目前状况为基本根据某个优化测度作最优选择，而不考虑多种也许的整体状况，它省去了为找最优解要穷尽所有也许而必须耗费的大量时间，它采用自顶向下，以迭代的措施做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一种规模更小的子问题，通过每一步贪心选择，可得到问题的一种最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，因此贪心法不要回溯。贪心算法是一种改善了的分级解决措施。其核心是根据题意选用一种量度原则。然后将这多种输入排成这种量度原则所规定的顺序，按这种顺序一次输入一种量。如果这个输入和目前已构成在这种量度意义下的部分最佳解加在一起不能产生一种可行解，则不把此输入加到这部分解中。这种可以得到某种量度意义下最优解的分级解决措施称为贪心算法。对于一种给定的问题，往往也许有好几种量度原则。初看起来，这些量度原则似乎都是可取的，但事实上，用其中的大多数量度原则作贪心解决所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度原则是使用贪心算法的核心。一般状况下，要选出最优量度原则并不是一件容易的事，但对某问题能选择出最优量度原则后，用贪心算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据目前状态做出在目前看来是最佳的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪心选择就将所求问题简化为一种规模更小的子问题，最后可得到问题的一种整体最优解。3.2 设计内容3.2.1 问题描述所谓TSP问题是指旅行家要旅行n个都市，规定各个都市经历且仅经历一次，并规定所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。3.2.2 设计思想对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有也许的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为(n!)，当n大到一定限度后是不可解的。因此我们选用贪心算法，但我们必须清晰地结识到贪心算法仍旧有着其缺陷（即在对问题求解时，总是做出在目前看来是最佳的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范畴相称广泛的许多问题她能产生整体最优解或者是整体最优解的近似解）。3.3 需求分析3.3.1 程序的功能：求一种旅行家要穿过多种都市，已知都市个数，以及都市间距，求出最短途径解和最短途径长度。3.3.2 输入输出的规定输入都市数目N为正整数，都市间距离最小值为0，输入起始都市的数字，输入共有N+2个数值；输出最优解和最优值。3.4 贪心算法解决TSP问题的流程图开始 输入都市数与间距，并输入起始都市遍历第一种可行回路的解和值为目前最优解和最优值继续遍历并与目前最优值和最优解比较，更优则替代达到结束点？ N Y输出最优质和最优解结束3.5 贪心算法解决TSP问题的环节第一步：理解并掌握问题的核心。第二步：建立数学模型来描述问题。第三步：把求解的问题提成若干个子问题。第四步：对每一子问题求解，得到子问题的局部最优解。第五步：把子问题的解局部最优解合成本来解问题的一种解。第六步：得出结论。4. 总结数据构造实习可以锻炼学生综合运用所学知识并运用课外知识，发现、提出、分析并解决实际问题的能力，是对学生实际工作能力的具体训练和考察过程。它不仅考察我们运用数据构造知识解决问题的能力，还考察了我们理解问题，查找资料的能力。在这几天里我不仅巩固了之前所学，还学到了许多课本上没有的知识。在确立问题之后，我通过图书馆查找、上网搜索等多种途径收集课题有关资料并认真整顿掌握算法。并用一段时间的编写代码，虽然第一次运营浮现了问题，但我并没有放弃，仔细地检查，发现并解决了问题。在一番调试后，代码最后能稳定迅速地运营。这次实习让我懂得了理论与实践结合的重要性，让我理解了如何迅速对的的解决问题。虽然编写代码的过程中浮现了某些小插曲，但是这些都将成为我的经验，避免我后来再次浮现这种状况。总之，这次实习让我收获颇丰。5. 任务分派排序姓名任务量承当任务1*100%选题，收集资料，编写调试代码，撰写报告参照文献：1百度百科，贪心算法，课程实习评分表本人 在 中，独立完毕 内容。本人自评级别为 。 签名： 日期：课程实习小组长评分表 同窗在本些课程实习中体现 。级别拟定为_。 签名： 日期：课程实习教师评分表 同窗在本些课程实习中体现 。级别定为_。 签名： 日期：