贪心算法2

22 Jun 2013 by LelouchHe

我们再来看一个类似的问题,来进一步了解贪心算法的另一种解法

简单Interval Partitioning问题

我们这里有n个任务,对于每个任务i,都存在一个s_i和f_i,用于表示任务的开始和结束时间,同时,我们有若干机器用于完成这些任务.唯一的条件是重叠的任务不能在同一时间同一机器上处理.亦即,如果i,j两个任务在处理时间上重叠,那么就必须分配在两个不同机器上运行.

问题的目标是在给定n个任务的情况下,如何分配这些任务,使得使用的机器数最少.

从上一篇来的解法

我们从上一篇学会了如何使用贪心算法来在一台机器上安排最多的任务,那么一个很自然的想法就是多次运行上述贪心算法,直到所有的任务都完成了.此时的机器数量,就是我们的可能的”最少”机器数量.

我们可以证明这个数量就是”最少”的机器数量.其实也不需要证明,我们这样的处理,得到的显然是最少的机器,不是么?每台机器都被利用到最大限度,所以肯定是最少数量的机器了.

优化解法

假设最少机器数量为m,如果按照上面的算法,我们需要执行m次贪心算法,每次算法耗时O(n),那么总的复杂度为O(mn).当然,如果m比较小的话,其实复杂度还是线性的.

但是回顾m次重复的算法,有很多可以利用的东西被忽略了.比如当选择了任务i时,可以得到一系列与i重叠的任务,这些任务都是不能同i在这台机器上处理的.如果按照上面的算法,这些任务就被丢弃了.等到选择下次机器选择的时候,我们还得重新来过.但这些任务是有额外信息的,比如他们是按照f_i排序的,这些任务可以直接使用,因为就算下次来过这些任务的排序之类是不会变的.所以如果我们直接把这些任务安排在下一台机器上,那么我们就可以使用这些信息,来优化复杂度了.

算法设计的一个要诀

额外信息

这四个字绝对值得单独开辟一个小节来指出.设计算法时,一定要选择和利用所有的信息,而且如果可能的话,一定要深刻的把握住最为关键的信息.

能够揭示问题本质的信息,一般会带来设计或优化算法的思路.

所以睁大眼睛,看清问题

另一种解法

上面的算法和书上讲的方式不太一样,但本质而言,是一致的

首先考虑一下重叠的情况,如果任务i和任务j重叠,那么1台机器是不可能同时处理的,最少需要2台.进一步泛化下,如果有m个任务在某一个时间点重叠,那么至少需要m台机器来处理这些任务.

一个很自然的想法是,如果有一个算法得到m个机器数量,那么这个算法就是我们想要的(因为已经证明m是下限,不可能存在比m更小的)

然后,又是一个很自然的想法,既然这样,当我们处理任务时,遇到重叠的任务,就把这些任务分到不同机器上去,这样机器的数量,就是不同任务重叠的最大数量,而这个就是需要的最少机器数.

算法比较

算法一和算法二(优化解法)有什么本质区别呢?虽然二者的角度可能不一样,一个从单机器的普通贪婪开始,一个则从更本质的”为什么需要不同机器”开始,起点不同,但最后都归结到了任务重叠上.可以看到,任务重叠是本问题的一个本质属性,从不同角度开始的解法,最后都利用了这一点来完成解答.

一种贪心的证明方法

在上一篇中,介绍了”stay ahead”方法来证明贪心的正确性,此处我们又看到另一种证明方法,即证明算法的结果满足问题的上/下限.上/下限是问题的本质决定的,这个和算法无关,但如果某算法的结果满足了上/下限,那么就不需要再证明什么了,结果已经显示无法获得更优的结果了.

这个其实和贪心关系不大,只要是最优算法,都可以使用类似的证明方式

代码

(待续)