贪心算法Tsp实习报告1

浙江农林大学信息工程学院课程实习报告

课程名称：数据结构实习

班级：电信****班

题目： TSP问题的贪心算法

组长： ******* 成员： ******* 指导教师： *******

2014年6月17 日

目录

1.课程实习目的 (1)

1.1贪心算法实习的目的 (1)

1.2TSP问题的解决及贪心算法的应用 (1)

1.3贪心算法的概念 (1)

2.课程实习题目描述和要求 (1)

2.1TSP问题介绍 (1)

2.2贪心算法的特性 (2)

2.2.1贪心算法的特性： (2)

2.2.2贪心算法的缺陷 (2)

2.3关于贪心算法的备注 (2)

3.课程实习报告内容 (2)

3.1了解并掌握贪心算法 (2)

3.2设计内容 (3)

3.2.1问题描述 (3)

3.2.2设计思想 (3)

3.3需求分析 (3)

3.3.1程序的功能： (3)

3.3.2输入输出的要求 (4)

3.4贪心算法解决TSP问题的流程图 (4)

3.5贪心算法解决TSP问题的步骤 (5)

4.总结 (5)

5.任务分配 (5)

1.课程实习目的

1.1贪心算法实习的目的

此次实习通过贪心算法来解决TSP问题。假设有n个城市，任意两个城市之间都有路径相通，并设第i个城市与第j个城市之间的距离为Dij，求从某个城市出发经过所有城市并且只经过一次又回到原点的都短距离。首先，本文运用Visual C++集成开发环境将贪心算法编程实现，并解决TSP问题。然后通过改变各个参数的值来观察计算结果，接着对运算结果的进行对比分析，从而验证各个参数对贪心算法的影响。

1.2TSP问题的解决及贪心算法的应用

旅行商问题(Traveling Salesman Problem, TSP),是一个著名的组合优化问题，该类问题具有非常广泛的运用背景。如物流的调度问题、数控机床上的最优钻孔路线的选取、电路板的焊接都属于旅行商问题。因此旅行商问题受到了各方面的关注，有效解决TSP问题在计算理论和实际应用上都有很高的价值。目前解决TSP的主要方法有贪心算法、遗传算法、模拟退火算法、蚁群算法、启发式搜索法、Hopfield神经网络算、二叉树描述算法。此次实习主要介绍了应用贪心算法来解决TSP问题。

1.3贪心算法的概念

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪心算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪心算法正确工作，那么找到的第一个解通常是最优的。

2.课程实习题目描述和要求

2.1TSP问题介绍

TSP问题，也称旅行商问题。已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他的访问顺序，可使其旅行的总长度最短。用图论的术语来说，假设有一个图g=(v , e),其中v是顶点集，e是边集，设d=d ij是由顶点i和顶点j之间距离所组成的距离矩阵，旅行商问题就是要求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题( d ij = d ji )任意（i , j=1,2,3,···,n）和非对称旅行商问题(d ij≠d ji)任意i , j=（1,2,3,···,n）。城市v={v1,v2,v3,···,v n的一个访问顺序为t(t1,t2,t3,···,ti,···,tn),其中ti∈v(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问题的流程图

3.5贪心算法解决TSP问题的步骤

第一步：了解并掌握问题的关键。

第二步：建立数学模型来描述问题。

第三步：把求解的问题分成若干个子问题。

第四步：对每一子问题求解，得到子问题的局部最优解。

第五步：把子问题的解局部最优解合成原来解问题的一个解。

第六步：得出结论。

4.总结

数据结构实习能够锻炼学生综合运用所学知识并利用课外知识，发现、提出、分析并解决实际问题的能力，是对学生实际工作能力的具体训练和考察过程。它不但考察我们运用数据结构知识解决问题的能力，还考察了我们了解问题，查找资料的能力。在这几天里我不仅巩固了之前所学，还学到了许多书本上没有的知识。在确立问题之后，我通过图书馆查找、上网搜索等多种途径收集课题相关资料并认真整理掌握算法。并用一段时间的编写代码，虽然第一次运行出现了问题，但我并没有放弃，仔细地检查，发现并解决了问题。在一番调试后，代码最终能稳定快速地运行。

这次实习让我懂得了理论与实践结合的重要性，让我了解了如何快速正确的解决问题。虽然编写代码的过程中出现了一些小插曲，但是这些都将成为我的经验，防止我以后再次出现这种情况。总之，这次实习让我收获颇丰。

5.任务分配

参考文献：

［1］百度百科，贪心算法，https://www.wendangku.net/doc/aa18349274.html,/view/298415.htm?fr=aladdin

课程实习评分表

本人在中，独立完成内容。本人自评等级为。

签名：

日期：

课程实习小组长评分表

同学在本些课程实习中表现。等级拟定为____。

签名：

日期：

课程实习教师评分表

同学在本些课程实习中表现。等级定为____。

签名：

日期：