贪心算法4
07 Jan 2014 by LelouchHe
题外话
很长一段时间没有更新blog了,主要原因还是太忙了.虽然组长每天在说”这个项目完了就轻松了”,但这就和学校老师说”今年是最关键的一年”,或者影帝说的”今年是最困难的一年”等等,永远没有尽头.
干了大概一年半,觉得越发的无力了.
哎,还是我自己太弱,找不到好的.
不说了.
贪心法的难点
现在回顾贪心算法,感觉有2个难点:
- 怎么判断一个问题能否用贪心解决?
- 怎么判断某个贪心方向是可行的?
这2个问题是纠缠在一起的,往往判断贪心是否可行的论证,就是找到贪心方向并证明最优,但如果某问题无法贪心,到底是真的无法贪心呢,还是我们太弱,没有找到合适的贪心方向呢?
所以,这也是我最大的疑惑所在.这样看来,由于贪心算法是高效的,只好遇到最优化问题先假设贪心可行,直到碰壁
贪心方向的发现
怎么才算碰壁呢?比如第1个Interval Scheduling问题,光书上的贪心方向就讲了4个.而且,这还是小事,假如我们事先不知道这些方向,怎么把这些挖出来呢?
这就是所谓”证明难,解答更难”.
还是第1个问题,4个贪心方向总得来说分2个角度,一个是时序,按照起始或结束时间贪心,这个比较容易分辨,因为时序角度来看,总是从时刻0开始,其实本来的贪心过程就隐含了起始的判断,如果再次使用起始贪心的话,结束时间这个重要属性就丢弃了,所以我们肯定优先选择结束时间;另一个是相对关系,是按照最小间隔(选择相对时长,而不是绝对时刻),还是按照最小重叠(任务间的相对),首先相对时长感觉本来就不靠谱,毕竟要回归到一段绝对时间段上,而最小重叠的这个,压根就没有把时间考虑进去,在寻找时间段内的最优解时,觉得也可以排除在外了.
综合上面的想法,针对解题而言,应该选择包含了最多的问题相关属性的方向,作为贪心的角度.比如时间段内最多数量,那么绝对时间需要考虑进来,起始和结束时间也都需要考虑,这种情况下,自然结束时间优先是个自然的考量
当然,这样的选择有些想当然尔.比如为什么执着与一维呢?万一贪心方向是双的呢?为什么非要结束时间最早,而不是开始时间最晚呢(比如我们倒着来做)?
不过有一点是肯定的,即充分利用题目的信息,才能有个全面的了解.看以往的题目解析,第一部分总是在分析已知条件,第二部分就是分析这些条件带来的各种属性.所以整体的分析还是最重要的.
贪心的证明
基本的证明分为2种:
- stay ahead: 即证明贪心的每一步都不比最优的差.我们可以假设存在另一种最优选择,然后使用2种方法一步一步的构建问题的2个解,同时证明贪心每一步都比假设中的最优要好.
- exchange: 即证明存在从最优解变换到贪心解的方法,同时不影响解的正确性.通常,我们假设存在最优解,然后按照贪心的方法加以修正,转换为贪心的解,从而说明二者的等价.
二者其实类似,这里的关键还是要想得到.有的时候面对问题一无所措,要时常提醒这些可以做做活动的角度
其实就手段而言,大部分还是归于反证和归纳.手段的基础是对问题已知和导出属性的熟悉,所以还是要认真的分析题目
不能贪心
有时候问题稍微变化下,贪心就会失败了.比如还是问题1,如果每个任务有权重,我们要挑选出权重和最大的一组任务.
我们还是按照旧的路子來看看.
- 这是一个最优化问题(权值最大),考虑下能否贪心(毕竟贪心快)
- 已知的条件有起始/结束时间和权值.我们可以得到一些结论:
- 如果选择了i,那么和i冲突的任务都没办法选择
- 在保证了不冲突的基础上,得到最大的权值和
- 最大权值和不一定表示最大任务数量,比如有的任务权值非常大,那么这1个就满足了最优了
- 问题1的贪心方向可以否?应该是不行的,问题1的4个贪心方向,重点是最大任务数量,而我们已经知道了任务数和权值和是不一致的,所以无法直接使用.贪心方向还有按照权值从大到小贪心,但这个也不成,类似于0/1背包问题,并不是最大的放进去就好,有时候小的加起来比大的大
- 有可以同时把时间和权值统一的贪心方向么?暂时看来是没有的,所以只能悲惨的说,这个问题无法贪心,只能另作想法了.(类似0/1背包,使用DP即可)
仅仅是多了一个权值,就导致了贪心的失败(当然,也许有,只是我没有找到而已),更重要的是,如果每个任务的权值为1,就又退化到了原始问题,又可以用贪心了.由此可见,贪心其实为DP的退化版本,DP考虑的是所有的选择,贪心仅考虑当下最优选择而已.(这些问题另说)
再拿lis(最长增长子串)问题来看,如果一开始我们就尝试贪心(这也是最优化问题嘛),比如从s[0]开始,按增序构建结果,我们一下就能看到反例(比如s[0]超大),从而进行了否定.然后一个很自然的想法就是可能不用从0开始,而是从1/2/3..开始.这样,一种朴素的枚举算法就出来了(每次以i开头,求最长增长子串),如果再改进下表示,就是DP的解答了.这也是从贪心到不能贪心,从贪心自然思考到其他算法的过程.
贪心和DP
二者的核心都是最优子问题,都遵从最优问题的解依赖于最优子问题的解,二者区别在于,贪心面对最优子问题時,选取了当前最优解,而DP则选择了所有的解情况的综合
贪心以抛弃非最优解來达到高效,DP相反,通过牺牲效率來保留所有解,幷通过另一个重要的特征來使效率还过得去(重复子问题).当只存在一个选择的时候,贪心和DP其实是一致的(比如带权值的问题1,权值等同于个数,所以二者均可).