概述
贪心算法应该算是那种“只闻其声不见其人”的算法,我们可能在好多地方都会听到贪心算法这一概念,并且它的算法思想也比较简单就是说算法只保证局部最优,进而达到全局最优。但我们实际编程的过程中用的并不是很多,究其原因可能是贪心算法使用的条件比较苛刻,所要解决的问题必须满足贪心选择性质---所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。
贪心算法
由于贪心算法本身的特殊性,我们在使用贪心算法之前必须要进行证明,保证算法满足贪心选择性质。具体的证明方法无外乎就是通过数学归纳法来进行证明。但大部分人可能并不喜欢枯燥的公式,因而我这里提供一个使用贪心算法的小技巧。由于贪心算法某种程度上算是动态规划算法的特例,使用条件比较苛刻,因而能够用动态规划解决的问题尽量都是用动态规划来进行先解决,如果在用完动态规划之后,提交时发现问题超时,并且进行状态压缩之后仍然超时,此时我们就可以考虑使用贪心算法来进行解决。最后强调一下,我们在使用贪心算法之前,如果要保证解法的绝对正确,一定要对问题进行证明,切记,切记!!
下边我们以区间调度问题为例,来讲一下贪心算法到底该如何取用。
区间调度问题
问题描述:
给你很多形如 [start, end] 的闭区间,请你设计一个算法,算出这些区间中最多有几个互不相交的区间。
举个例子,intvs = [[1,3], [2,4], [3,6]],这些区间最多有 2 个区间互不相交,即 [[1,3], [3,6]],你的算法应该返回 2。注意边界相同并不算相交。
这个问题大眼一看好像有很多贪心策略可供选择,比如我们可以选择区间最短的?或者选择开始最早的?。。。
但是上面几种策略,我们都可以比较容易的举出反例来排除,同时这也是贪心算法的另一个小技巧--虽然好多时候直接证明贪心策略的正确性很难,但是我们可以从反证法入手,对贪心策略进行证伪,排除许多错误的贪心策略。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)