贪心算法在生活中的应用

阜阳市第三中学 安徽阜阳 236000

贪心算法是一种非常常见的算法，最常应用的有归纳法和反证法，当然还有其它的应用方式。此外，贪心算法是信息竞赛中最为常用的一种解题思路。

1 贪心算法的定义

贪心算法只是当下最优的一种解题方式，与后续无关，有些自私因素在其中，所以被称为贪心算法[1]。因为其局部性，可能从整体来看这种解题方式不够完美、不够准确，但它是目前最快最完美的解答方式。这种方式在信息竞赛中很常见，也是信息竞赛中的一种常见解题思想。

2 贪心算法的基本要素

贪心算法的第一个要素是贪心选择，通常来说就是所求问题的一种最优的解答方式。一般是我们常采用从顶向下，或者是以迭代的方式做出选择，但都是为了同一目的，之后再通过一次次贪心选择，将求解的问题不断做减法，通过简化，缩小规模以找寻最优的一种解题方法。

一般来说，一个问题能否用贪心算法，首选要看它能否做出贪心选择，如果可以通过一步步的贪心选择，最终找到最优方式，那么就可以使用贪心算法。通过数学归纳法来证明，就是每一步的贪心选择最后都是为了达到最优的目的。而使用贪心算法一般都有一定的贪心策略，而证明这个贪心策略的方法有很多，一般最常用的有归纳法、反证法。

3 贪心算法生活中的应用

在日常生活中，比如汽车去加油站加油，如果加满后这辆车可以行驶N千米，但是在途中有很多个加油站，此时我们可以利用贪心算法算出在整个旅途中怎么加油使得加油的次数最少。首先我们要先通过贪心算法设计一个最有效的算法，并要说明应该在哪些个加油站停靠加油[2]。如果加油次数为m，那每一个加油站之间的距离就是a[i]；i=0，1，2，3……n。利用贪心算法，最优的选择应该是若每次加油时油箱里的油不能支撑到下一个加油站，我们才会选择就近的加油站加油。

假设A不是最优的一种方式，那么一定还存在其它解题方式，假设是B，那么B就是和A最接近的一个优解。B和A的前K-1个元素是相同的，也就是说K个元素是不同的，即A的第K个选择是一定满足一个条件，那就是不能不加油就开到另一个加油站。而B的第K个选择的站一定是A的K-1，如果说到K的选择之间的某一个加油站是Y的话，对A来说，X到下一个加油的距离一定小于Y。

如果此时再构造一个C，也就是说C=B-y+x。那么C其实就是这个问题的最优解，同时C也能使得汽车安全到达最终的目的地。在C中，在X站之前的加油站点其实和A站的加油站点是一样的，而在X后的加油站点也和B站的加油站点是一样的，所以就是说C可以顺利通过。而当到打X站的时候，X站的下站又小于Y到下一个加油站的距离，所以在这个过程中不需要加油，所以按照这样的理论来说，那么C就是最优解。

但如果C是最优解，这又与之前的假设K-1矛盾，所以如果之前的所有的假设都是错误，就意味着A是最优解。

4 贪心算法的特点及难点

贪心算法的特点非常鲜明，就是在运用整个贪心算法，通过贪心策略解决问题的过程中不需要考虑前因后果，也不需要不断回溯，而只需要考虑在当前状态下是否是最优的解题方式，因此目的性更强，在解题的时候也更有目标，更准确，更快捷[3]。

但正是因为这种鲜明的特点，问题也随之凸显。比如，利用贪心算法的贪心策略，我们考虑的只是当下，这可能是现阶段最优的一种解决问题的方式，但我们却并不能保证其在最后的解题中是否是最优的一种解题方式。因为这种方式只能从局部考虑，无法从整体上来做出判断，也并不能保证这就是最正确的解题方式。所以对于最终的解题方式来说，这种贪心算法是否会是最优的一种解题方法，我们无法保证。我们也只能用利用贪心算法来解决一些比如最大或者最小的问题。因为在一定程度上来说，贪心算法只能确定一些问题的可行范围，并不能准确解答。它是一种预估的范畴，当面对详细的问题，或者是非常绝对的问题，那么贪心算法就不是最佳的计算方式。所以我们在使用贪心算法的时候，要考虑到它的适用性，不能盲目使用[4]。

贪心算法的难点也很明显，即如何确定能否使用贪心算法。使用贪心算法并不困难，但其是却是在局部中应用的，并不能确定是不是整体的最优解。所以针对一些问题，如果只能在局部使用，我们就应该考虑其它解题方式。

5 结语

贪心算法或许在一些信息竞赛或者是NPC类的问题中具有绝对的优势，但平时可能只能确定一个范围，并不一定是最佳的解题方式。所以在求最优解时，一定要全面考虑，可以运用贪心算法时，一定要充分利用其优势，因为它是最接近我们思维的一种解题方式。同时，我们也一定要考虑到贪心算法的适用范围，在可行的范围最大化利用这一方法。