贪心算法3

23 Jun 2013 by LelouchHe

最小延迟问题

再来看一个类似的问题.假设每个任务i都有一个处理时间t_i和一个处理最后期限d_i,定义任务的延迟l_i = f_i - d_i(如果f_i < d_i则为0).所有这些任务都在一台机器上处理(资源有限),问题是如何安排这些任务,使得任务的最大延迟最小,即l = max(li),找到一种安排任务的方式,使l最小

怎么贪心

和其他的贪心问题一样,第1步需要确定的是贪心的方向(当然,第0步肯定是需要确定问题对于贪心算法是可解的,不过此处就忽略了),书上讲了一些”自然”的方向:

t_i: 即按照任务处理时间进行贪心
d_i - t_i: 即按照任务的可剩余时间,在截止时间之前有多少时间可以等待
d_i: 即按照任务的截止时间

其实选择任意一个方向,都会面临一个问题,即信息的遗失,比如在1中的d_i,2中的t/d绝对值,3中的t_i.正如上一篇所讲的,额外信息是算法设计的一个核心属性,丢失的信息对于算法设计来说是一个损失,甚至会导致算法的失败.

从书中可以看到,1/2都不是合适的贪心方向,而3是.为什么呢?这三个都有信息损失,为什么只有3才能得到最优结果?

如果我们仔细的观察题目,可以看到另一个隐藏的信息,即t_i <= d_i(假设任务都是从0开始的,这也是题目隐含的).在1的情况下,只有t是无法推知d的,因为d可以无限大,但是在3的情况下,即在知道d的情况下,是可以知道t的上限的(不超过d),而在这个问题下,上限是足够的(因为我们试图求的是最优结果)

所以可以看到,3其实并没有丢失信息,或者说没有丢失关键信息,在使用d的同时,我们兼顾了t,保存了可以用来进行最优处理的信息

至于2,我们只能看到,相对信息对于此处最优问题的求解作用不大,要得到最优结果,还是要从绝对值开始看起的.

证明

1/2都可以很容易利用反证法来证明其错误性(反证法是证明利器),3的证明我们需要使用一种通用的证明方法(还记得第一篇中的”stay ahead”么?这是一种方法而已),叫做exchange argument

exchange argument

这个证明方法其实也是非常自然的,正如stay ahead一样,首先假设存在一个最优算法得到一种最优排序,然后证明,这个最优排序可以经过调整,得到我们贪心算法的排序,并且并不损失任何属性(即不会增加最大延迟).如果我们可以做出以上的证明,那么就表示贪心算法的正确性了

举例

拿本篇讨论的最大延迟问题为例:

首先,一个自然的想法是最优排序不会有间隔.试想,如果最优排序存在间隔,那么可以将间隔后的所有任务前移,这样必然会使间隔后的任务延迟减小,而间隔前的任务延迟不变.总的结果是只可能减少最大延迟.所以最优排序是没有间隔的
其次,使用贪心算法,按照任务的截止时间d来进行贪心.需要证明的就是这样的结果是一个最优排序.假设存在一种最优排序,并不是按照d进行排序的,这样必然有连续的两个任务i和j,有d_i > d_j(这是必然的).”exchange argument”的做法就是证明对i/j进行调换之后,可以从最优排序得到现有排序,而且不影响结果.
根据2的假设,对i/j进行调换,可以看到,这样的操作不影响任务j的延迟,因为j被提前了,所以延迟肯定减少了.唯一需要注意的任务i,设调换后的实际结束时间为fn,调换后的延迟为ln,可以得到ln_i = fn_i - d_i.由于i/j总的时间不变(都是t_i + t_j),所以fn_i = f_j,可以得到ln_i = f_j - d_i.又由于d_i >= d_j,可得ln_i <= f_j - d_j = l_j.所以,现在任务i的延迟不超过原来任务j的延迟,这样,i/j的最大延迟肯定是减小了.i/j之前的任务保持不变(因为没有操作过),i/j之后的任务保持不变(因为t_i + t_j不变),所以排序总的最大延迟只能减小.
证明了连续2个任务的可调换,剩下的工作就是递归的证明全部

换一种方式

第一篇中介绍的”stay ahead”能否证明这个问题呢?我稍微尝试了一下,觉得有些困难,因为不像简单Interval Scheduling问题那样,此处牵扯到两个问题,一是延迟计算依赖的两值(f和d),这两个值不是简单的比较就得到的,二是最大延迟的计算不是局部的,而是全局的,单个任务的比较显得很没有意义.所以如果你们有什么好方式来处理这个问题,请告诉我.

其实,这里想讨论的不是怎么用另一种方式来证明,而是如何想到用什么方式来证明.比如面对这个或上述几个问题,在知道了使用贪心和贪心方向的前提下,如何证明贪心的正确性.

不过这个问题也颇大,在探察贪心问题的时候,隐隐的发现贪心问题的背后,应该有固有的结构,来保证”stay ahead”或者”exchange argument”是可以得到贪心最优结果的.这个问题目前还没有进展,在本系列的最后我会试图纠结一下的

代码

这个就不写了,就是按照d排序,简单的qsort即可.

本问题的纠结点主要在判断和证明上