在贪婪算法(greedy method)中采用逐步构造最优解的方法在每个阶段都作出一个看上去最优的决策(在一定的标准下)决策一旦作出就不可再更改作出贪婪决策的依据称为贪婪准则(greedy criterion)
例 [找零钱] 一个小孩买了价值少于美元的糖并将美元的钱交给售货员售货员希望用数目最少的硬币找给小孩假设提供了数目不限的面值为 美分 美分美分及美分的硬币售货员分步骤组成要找的零钱数每次加入一个硬币选择硬币时所采用的贪婪准则如下每一次选择应使零钱数尽量增大为保证解法的可行性(即所给的零钱等于要找的零钱数)所选择的硬币不应使零钱总数超过最终所需的数目
假设需要找给小孩 美分首先入选的是两枚 美分的硬币第三枚入选的不能是 美分的硬币否则硬币的选择将不可行(零钱总数超过 美分)第三枚应选择 美分的硬币然后是美分的最后加入两个美分的硬币
贪婪算法有种直觉的倾向在找零钱时直觉告诉我们应使找出的硬币数目最少(至少是接近最少的数目)可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少(见练习)
例 [机器调度] 现有n 件任务和无限多台的机器任务可以在机器上得到处理每件任务的开始时间为si完成时间为fi si < fi [si fi ] 为处理任务i 的时间范围两个任务ij 重指两个任务的时间范围区间有重叠而并非是指ij 的起点或终点重合例如区间[ ]与区间[ ]重叠而与区间[ ]不重叠一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器因此在可行的分配中每台机器在任何时刻最多只处理一个任务最优分配是指使用的机器最少的可行分配方案
假设有n= 件任务标号为a 到g它们的开始与完成时间如图a 所示若将任务a分给机器M任务b 分给机器M 任务g 分给机器M这种分配是可行的分配共使用了七台机器但它不是最优分配因为有其他分配方案可使利用的机器数目更少例如可以将任务abd分配给同一台机器则机器的数目降为五台
一种获得最优分配的贪婪方法是逐步分配任务每步分配一件任务且按任务开始时间的非递减次序进行分配若已经至少有一件任务分配给某台机器则称这台机器是旧的;若机器非旧则它是新的在选择机器时采用以下贪婪准则根据欲分配任务的开始时间若此时有旧的机器可用则将任务分给旧的机器否则将任务分配给一台新的机器 根据例子中的数据贪婪算法共分为n = 步任务分配的顺序为afbcged第一步没有旧机器因此将a 分配给一台新机器(比如M)这台机器在到时刻处于忙状态在第二步考虑任务f由于当f 启动时旧机器仍处于忙状态因此将f 分配给一台新机器(设为M )第三步考虑任务b 由于旧机器M在Sb = 时刻已处于闲状态因此将b分配给M执行M下一次可用时刻变成fb = M的可用时刻变成ff = 第四步考虑任务c由于没有旧机器在Sc = 时刻可用因此将c 分配给一台新机器(M)这台机器下一次可用时间为fc = 第五步考虑任务g将其分配给机器M第六步将任务e 分配给机器M 最后在第七步任务分配给机器M(注意任务d 也可分配给机器M)
上述贪婪算法能导致最优机器分配的证明留作练习(练习)可按如下方式实现一个复杂性为O (nl o gn)的贪婪算法首先采用一个复杂性为O (nl o gn)的排序算法(如堆排序)按Si 的递增次序排列各个任务然后使用一个关于旧机器可用时间的最小堆
例 [最短路径] 给出一个有向网络路径的长度定义为路径所经过的各边的耗费之和要求找一条从初始顶点s 到达目的顶点d 的最短路径
贪婪算法分步构造这条路径每一步在路径中加入一个顶点假设当前路径已到达顶点q且顶点q 并不是目的顶点d加入下一个顶点所采用的贪婪准则为选择离q 最近且目前不在路径中的顶点
这种贪婪算法并不一定能获得最短路径例如假设在图 中希望构造从顶点到顶点的最短路径利用上述贪婪算法从顶点开始并寻找目前不在路径中的离顶点最近的顶点到达顶点长度仅为个单位从顶点可以到达的最近顶点为从顶点到达顶点最后到达目的顶点所建立的路径为 其长度为 这条路径并不是有向图中从到的最短路径事实上有几条更短的路径存在例如路径的长度为
根据上面三个例子回想一下前几章所考察的一些应用其中有几种算法也是贪婪算法例如霍夫曼树算法利用n 步来建立最小加权外部路径的二叉树每一步都将两棵二叉树合并为一棵算法中所使用的贪婪准则为从可用的二叉树中选出权重最小的两棵L P T调度规则也是一种贪婪算法它用n 步来调度n 个作业首先将作业按时间长短排序然后在每一步中为一个任务分配一台机器选择机器所利用的贪婪准则为使目前的调度时间最短将新作业调度到最先完成的机器上(即最先空闲的机器)
注意到在机器调度问题中贪婪算法并不能保证最优然而那是一种直觉的倾向且一般情况下结果总是非常接近最优值它利用的规则就是在实际环境中希望人工机器调度所采用的规则算法并不保证得到最优结果但通常所得结果与最优解相差无几这种算法也称为启发式方法( h e u r i s t i c s )因此L P T方法是一种启发式机器调度方法定理 陈述了L P T调度的完成时间与最佳调度的完成时间之间的关系因此L P T启发式方法具有限定性 能( bounded performance )具有限定性能的启发式方法称为近似算法( a p p r o x i m a t i o na l g o r i t h m)
本章的其余部分将介绍几种贪婪算法的应用在有些应用中贪婪算法所产生的结果总是最优的解决方案但对其他一些应用生成的算法只是一种启发式方法可能是也可能不是近似算法
