贪婪算法[精彩]
贪婪算法
贪婪算法
虽然设计一个好的求解算法更像是一门艺术,而不像是技术,但仍然存在一些行之有效的能够用于解决许多问
的算法设计
,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。
本章首先引入最优化的概念,然后介绍一种直观的问题求解方法:贪婪算法。最后,应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解
。
1.1 最优化问题
本章及后续章节中的许多例子都是最优化问题( optimization
problem),每个最优化问题都包含一组限制条件( c o n s t r a i
n t)和一个优化函数( optimization function),符合限制条件的问题求解方案称为可行解( feasible solution),使优化函数取得最佳值的可行解称为最优解(optimal solution)。
例1-1 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿,她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水,即婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验,此婴儿知道这其中某些饮料更合自己的胃口,因此,婴儿采取如下方法为每一种饮料赋予一个满意度值:饮用1盎司第i 种饮料,对它作出相对评价,将一个数值si 作为满意度赋予第i 种饮料。
通常,这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要,但是不幸的是:具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i 种饮料的总量(以盎司为单位),而此婴儿需要t 盎司的饮料来解渴,那么,需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢,
设各种饮料的满意度已知。令xi 为婴儿将要饮用的第i 种饮料的量,则需要解决的问题是:
找到一组实数xi(1?i?n),使n ?i = 1si xi 最大,并满足:n ?i=1xi =t 及0?xi?ai 。
需要指出的是:如果n ?i = 1ai < t,则不可能找到问题的求解方案,因为即使喝光所有的饮料也不能使婴儿解渴。
对上述问题精确的数学描述明确地指出了程序必须完成的工作,根据这些数学公式,可以对输入/ 输出作如下形式的描述:
输入:n,t,si ,ai(其中1?i?n,n 为整数,t、si 、ai 为正实数)。
输出:实数xi(1?i?n),使n ?i= 1si xi 最大且n ?i=1xi =t(0?xi?ai)。如果n ?i = 1ai
k。寻找[ 1 ,n]范围内最小的整数j,使
得xj?yj 。若没有这样的j 存在,则n ?i= 1xi =n ?i = 1yi 。
如果有这样的j 存在,则j?k,否则y 就不是一个可行解,因为
xj?yj ,xj = 1且yj = 0。令yj = 1,若结果得到的y 不是可行
解,则在[ j+ 1 ,n]范围内必有一个l 使得yl = 1。令yl = 0,由
于wj?wl ,则得到的y 是可行的。而且,得到的新y 至少与原来
的y 具有相同数目的1。
经过数次这种转化,可将y 转化为x。由于每次转化产生的新y 至少与前一个y 具有相同数目的1,因此x 至少与初始的y 具有相同的数目1。货箱装载算法的C + +代码实现见程序1 3 - 1。由于贪婪算法按货箱重量递增的顺序装载,程序1 3 - 1首先利用间接寻址排序函数I n d i r e c t S o r t对货箱重量进行排序(见3 . 5节间接寻址的定义),随后货箱便可按重量递增的顺序装载。由于间接寻址排序所需的时间为O (nl o gn)(也可利用9 . 5 . 1节的堆排序及第2章的归并排序),算法其余部分所需时间为O (n),因此程序1 3 - 1的总的复杂性为O (nl o gn)。
程序13-1 货箱装船
template
void ContainerLoading(int x[], T w[], T c, int n)
{// 货箱装船问题的贪婪算法
// x[i] = 1 当且仅当货箱i被装载, 1<=i<=n
// c是船的容量, w 是货箱的重量
// 对重量按间接寻址方式排序
// t 是间接寻址表
int *t = new int [n+1];
I n d i r e c t S o r t ( w, t, n);
// 此时, w[t[i]] <= w[t[i+1]], 1<=i规定从每种货物中最多只能拿一件,车子的容量为c,物品i 需占用wi 的空间,价值为pi 。你的目标是使车中装载的物品价值最大。当然,所装货物不能超过车的容量,且同一种物品不得拿走多件。这个问题可仿照0 / 1背包问题进行建模,其中车对应于背包,货物对应于物品。
0 / 1背包问题有好几种贪婪策略,每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。一种贪婪准则为:从剩余的物品中,选出可以装入背包的价值最大的物品,利用这种规则,价值最大的物品首先被装入(假设有足够容量),然后是下一个价值最大的物品,如此继续下去。这种策略不能保证得到最优解。例如,考虑n=2, w=[100,10,10], p =[20,15,15],
c = 1 0 5。当利用价值贪婪准则时,获得的解为x= [ 1 , 0 , 0 ],这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ],其总价值为3 0。
另一种方案是重量贪婪准则是:从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解,但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100],
c= 2 5。当利用重量贪婪策略时,获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
还可以利用另一方案,价值密度pi /wi 贪婪算法,这种选择准则为:从剩余物品中选择可
装入包的pi /wi 值最大的物品,这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。
我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧, 0 / 1背包问题是一个N P-复杂问题。对于这类问题,也许根本就不可能找到具有多项式时间的算法。虽然按pi /wi 非递(增)减的次序装入物品不能保证得到最优解,但它是一个直觉上近似的解。我们希望它是一个好的启发式算法,且大多数时候能很好地接近最后算法。在6 0 0个随机产生的背包问题中,用这种启发式贪婪算法来解有2 3 9题为最优解。有5 8 3个例子与最优解相差1 0 %,所有6 0 0个答案与最优解之差全在2 5 %以内。该算法能在O (nl o gn)时间内获得如此好的性能。我们也许会问,是否存在一个x (x<1 0 0 ),使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点,考虑例子n =2, w = [ 1 ,y], p= [ 1 0 , 9y], 和c= y。贪婪算法结果为x=[1,0], 这种方案的值为1 0。对于y?1 0 / 9,最优解的值为9 y。因此,贪婪算法的值与最优解的差对最优解的比例为( ( 9y - 1 0)/9y* 1 0 0 ) %,对于大的y,这个值趋近于1 0 0 %。但是可以建立贪婪启发式方法来提供解,使解的结果与最优解的值之差在最优值的x% (x<100) 之内。首先将最多k 件物品放入背包,如果这k 件物品重量大于c,则放弃它。否则,剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序装入。通过考虑由启发法产生的解法中最多为k 件物品的所有可能的子集来得到最优解。
例13-9 考虑n =4, w=[2,4,6,7], p=[6,10,12,13], c = 11。当k= 0时,背包按物品价值密度非递减顺序装入,首先将物品1放入背包,
然后是物品2,背包剩下的容量为5个单元,剩下的物品没有一个合适的,因此解为x = [ 1 , 1 , 0 , 0 ]。此解获得的价值为1 6。
现在考虑k = 1时的贪婪启发法。最初的子集为{ 1 } , { 2 } , { 3 } ,
{ 4 }。子集{ 1 } , { 2 }产生与k= 0时相同的结果,考虑子集{ 3 },置x3 为1。此时还剩5个单位的容量,按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1,它适合,因此取x1 为1,这时仅剩下3个单位容量了,且剩余物品没有能够加入背包中的物品。通过子集{ 3 }开始求解得结果为x = [ 1 , 0 , 1 , 0 ],获得的价值为1 8。若从子集{ 4 }开始,产生的解为x = [ 1 , 0 , 0 , 1 ],获得的价值为1 9。考虑子集大小为0和1时获得的最优解为[ 1 , 0 , 0 , 1 ]。这个解是通过k= 1的贪婪启发式算法得到的。
若k= 2,除了考虑k< 2的子集,还必需考虑子集{ 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 }和{ 3 , 4 }。首先从最后一个子集开始,它是不可行的,故将其抛弃,剩下的子集经求解分别得到如下结果:[ 1 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 0 ] , [ 1 ,
0 , 0 , 1 ] , [ 0 , 1 , 1 , 0 ]和[ 0 , 1 , 0 , 1 ],这些结果中最后一个价值为2 3,它的值比k= 0和k= 1时获得的解要高,这个答案即为启发式方法产生的结果。 这种修改后的贪婪启发方法称为k阶优化方法(k - o p t i m a l)。也就是,若从答案中取出k 件物品,并放入另外k 件,获得的结果不会比原来的好,而且用这种方式获得的值在最优值的( 1 0 0 / (k + 1 ) ) %以内。当k= 1时,保证最终结果在最佳值的5 0 %以内;当k= 2时,则在3 3 . 3 3 %以内等等,这种启发式方法的执行时间随k 的增大而增加,需要测试的子集数目为O (nk ),每一个子集所需时间为O (n),因此当k >0时总的时间开销为O (nk+1 )。实际观察到的性能要好得多。
1.3.3 拓扑排序
一个复杂的工程通常可以分解成一组小任务的集合,完成这些小任务意味着整个工程的完成。例如,汽车装配工程可分解为以下任务:将底盘放上装配线,装轴,将座位装在底盘上,上漆,装刹车,装门等等。任务之间具有先后关系,例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动( Activity On Vertex, AOV)网络。有向图的顶点代表任务,有向边(i, j) 表示先后关系:任务j 开始前任务i 必须完成。图1 - 4显示了六个任务的工程,边( 1 , 4)表示任务1在任务4开始前完成,同样边( 4 , 6)表示任务4在任务6开始前完成,边(1 , 4)与(4 , 6)合起来可知任务1在任务6开始前完成,即前后关系是传递的。由此可知,边(1 , 4)是多余的,因为边(1 , 3)和(3 , 4)已暗示了这种关系。
在很多条件下,任务的执行是连续进行的,例如汽车装配问题或平时购买的标有“需要装配”的消费品(自行车、小孩的秋千装置,割草机等等)。我们可根据所建议的顺序来装配。在由任务建立的有向图中,边( i, j)表示在装配序列中任务i 在任务j 的前面,具有这种性质的序列称为拓扑序列(topological orders或topological sequences)。根据任务的有向图建立拓扑序列的过程称为拓扑排序(topological sorting)。图1 - 4的任务有向图有多种拓扑序列,其中的三种为1 2 3 4 5 6,1 3 2 4 5 6和2 1 5 3 4 6,序列1 4 2 3 5 6就不是拓扑序列,因为在这个序列中任务4在3的前面,而
任务有向图中的边为( 3 , 4),这种序列与边( 3 , 4)及其他边所指示的序列相矛盾。可用贪婪算法来建立拓扑序列。算法按从左到右的步骤构造拓扑序列,每一步在排好的序列中加入一个顶点。利用如下贪婪准则来选择顶点:从剩下的顶点中,选择顶点w,使得w 不存在这样的入边( v,w),其中顶点v 不在已排好的序列结构中出现。注意到如果加入的顶点w违背了这个准则(即有向图中存在边( v,w)且v 不在已构造的序列中),则无法完成拓扑排序,因为顶点v 必须跟随在顶点w 之后。贪婪算法的伪代码如图1 3 - 5所示。while 循环的每次迭代代表贪婪算法的一个步骤。
现在用贪婪算法来求解图1 - 4的有向图。首先从一个空序列V开始,第一步选择V的第一个顶点。此时,在有向图中有两个候选顶点1和2,若选择顶点2,则序列V = 2,第一步完成。第二步选择V的第二个顶点,根据贪婪准则可知候选顶点为1和5,若选择5,则V = 2 5。下一步,顶点1是唯一的候选,因此V = 2 5 1。第四步,顶点3是唯一的候选,因此把顶点3加入V
得到V = 2 5 1 3。在最后两步分别加入顶点4和6 ,得V = 2 5 1 3 4 6。
1. 贪婪算法的正确性
为保证贪婪算法算的正确性,需要证明: 1) 当算法失败时,有向图没有拓扑序列; 2) 若
算法没有失败,V即是拓扑序列。2) 即是用贪婪准则来选取下一个顶点的直接结果, 1) 的证明见定理1 3 - 2,它证明了若算法失败,则有向图中有环路。若有向图中包含环qj qj + 1.qk qj , 则它没有拓扑序列,因为该序列暗示了qj 一定要在qj 开始前完成。
定理1-2 如果图1 3 - 5算法失败,则有向图含有环路。
证明注意到当失败时| V |
记录 拓扑次序
// 如果不存在拓扑次序,则返回f a l s e
int n = Ve r t i c e s ( ) ;
// 计算入度
int *InDegree = new int [n+1];
InitializePos(); // 图遍历器数组
for (int i = 1; i <= n; i++) // 初始化
InDegree[i] = 0;
for (i = 1; i <= n; i++) {// 从i 出发的边
int u = Begin(i);
while (u) {
I n D e g r e e [ u ] + + ;
u = NextVe r t e x ( i ) ; }
}
// 把入度为,的顶点压入堆栈
LinkedStack