贪心法思想和其运用

《贪心法思想和其运用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、4贪心法思想及其运用摘要:主要介绍贪心算法（又称贪婪算法）的基本思想，以及如何利用贪心算法来求解问题，如何选择最佳的贪心算法的策略，以及贪心算法在一些数学问题上的运用。关键词：贪心算法最优策略正文：贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对一些问题它能产生整体最优解或者是整体最优解的近似解。贪心算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。一定要注意，选择的贪婪策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略

2、影响，也就是说某个状态以后的过程不会影响以前的状态，只与当前状态有关，也称为这种特性为无后效性。因此，适应用贪婪策略解决的问题类型较少，对所采用的贪婪策略一定要仔细分析其是否满足无后效性。为了说明在使用贪心算法中选择策略是关键，下面这个例子可以充分的说明这个问题：题目：设有n个正整数，将他们连接成一排，组成一个最大的多位整数。例如:n=3时，3个整数13,312,343,连成的最大整数为:34331213第一种策略：把整数按从大到小的顺序连接起来，题目中的例子正好符合这个策略；第二种策略：先把整数化成字符串，然后再比较a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之则把a排在b的

3、后面。许多同学开始看到这个题目的时候会毫不犹豫的选择第一种策略，这种策略表面上看起来是对的，从大到小排列之后，最终的数肯定会是最大的结果，但实际上这种策略师错误的，反例有很多，比如说当n=2时，2个整数为12，121按照第一种策略就会组成12112，而正确的结果为12121，按照第二种策略的结果正是12121。由此可见算法策略的选择是非常关键的，会直接影响到最终结果的正确性。当然上面的例子也可以不用贪心算法来实现，但是我们发现用贪心算法来解决这个问题还是比较简单的，很容易理解其实现过程。由此我们也发现，贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解

4、，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。贪心算法的基本思路是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止，简要归纳为以下几点：1.建立数学模型来描述整个数学问题；2.把求解的问题分成若干个子问题；3.对每一子问题求解，得到子问题的局部最优解；4.把子问题的解局部最优解合成原来解问题的一个解。贪心算法虽然能使一些问题求解比较简单，但是该算法任然存在以下一些问题：1.不能保证求得的最后解是最佳的；41.不能用来求最大或最小解问题；2.只能求满足某些

5、约束条件的可行解的范围。实现该算法的过程可以简要概括为：从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；贪婪算法策略在《数据结构》课程中的算法也有广泛的应用，如霍夫曼树、构造最小生成树的Prim算法和Kruskal算法的决策过程，都是使用的贪婪算法策略。教材上也举出了一些经典的实例，通过这些例子，我们可以感觉到使用贪心算法可以使问题逐步简化，最终达到目标结果。下面举一个贪心算法的经典问题，即背包问题,这个问题我们可以了解到贪心算法的特点及应对某些问题的不足之处。问题如下：有一个背包，背包容量是M=150。有7个物品，物品

6、不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品ABCDEFG重量35306050401025价值10403050354030这个问题当时也是数据结构的一个课后习题，但是我遇到这个问题的第一反应就是要使背包中的物品总价值最大，我可以先计算出每个物品的性价比，然后从性价比高的物品选起，直到达到背包的总容量。我的这个想法看起来还不错，也许刚好能使背包装满，而却物品也不会出现需要拆分，但是实际上是不可行的。一般来讲这个问题有三种策略：第一种策略：选取价值最大者；第二种策略：选取重量最小；第三种策略：选取单位重量价值最大的物品。然而这三种策略都有其不足之处，反例如

7、下：第一种策略反例(M=30)物品ABC重量291515价值352020第二种策略反例（M=30）物品ABC重量291515价值351010第三种策略反例（M=30）物品ABC重量2999价值291010由此可见这三种策略均不完全，不能解决问题。这也说明了用贪心法也不一定能得到最优解，策略在实行前一定要认真考虑其是否全面，是否具有无后向性。对与本题目，在第三种策略上稍作改动还是可以解决的，把第三种策略改为：对