贪婪算法（三）

上述贪婪算法能导致最优机器分配的证明留作练习（练习7）。可按如下方式实现一个复杂性为O (nl o gn)的贪婪算法：首先采用一个复杂性为O (nl o gn)的排序算法（如堆排序）按Si 的递增次序排列各个任务，然后使用一个关于旧机器可用时间的最小堆。

例1-6 [最短路径] 给出一个有向网络，路径的长度定义为路径所经过的各边的耗费之和。要求找一条从初始顶点s 到达目的顶点d 的最短路径。

贪婪算法分步构造这条路径，每一步在路径中加入一个顶点。假设当前路径已到达顶点q，

且顶点q 并不是目的顶点d。加入下一个顶点所采用的贪婪准则为：选择离q 最近且目前不在路径中的顶点。

这种贪婪算法并不一定能获得最短路径。例如，假设在图1 3 - 2中希望构造从顶点1到顶点5的最短路径，利用上述贪婪算法，从顶点1开始并寻找目前不在路径中的离顶点1最近的顶点。到达顶点3，长度仅为2个单位，从顶点3可以到达的最近顶点为4，从顶点4到达顶点2，最后到达目的顶点5。所建立的路径为1 , 3 , 4 , 2 , 5，其长度为1 0。这条路径并不是有向图中从1到5的最短路径。事实上，有几条更短的路径存在，例如路径1，4，5的长度为6。

根据上面三个例子，回想一下前几章所考察的一些应用，其中有几种算法也是贪婪算法。例如，霍夫曼树算法，利用n- 1步来建立最小加权外部路径的二叉树，每一步都将两棵二叉树合并为一棵，算法中所使用的贪婪准则为：从可用的二叉树中选出权重最小的两棵。L P T调度规则也是一种贪婪算法，它用n 步来调度n 个作业。首先将作业按时间长短排序，然后在每一步中为一个任务分配一台机器。选择机器所利用的贪婪准则为：使目前的调度时间最短。将新作业调度到最先完成的机器上（即最先空闲的机器）。

注意到在机器调度问题中，贪婪算法并不能保证最优，然而，那是一种直觉的倾向且一般情况下结果总是非常接近最优值。它利用的规则就是在实际环境中希望人工机器调度所采用的规则。算法并不保证得到最优结果，但通常所得结果与最优解相差无几，这种算法也称为启发式方法（ h e u r i s t i c s )。因此L P T方法是一种启发式机器调度方法。定理9 - 2陈述了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）。

本章的其余部分将介绍几种贪婪算法的应用。在有些应用中，贪婪算法所产生的结果总是最优的解决方案。但对其他一些应用，生成的算法只是一种启发式方法，可能是也可能不是近似算法。用的规则就是在实际环境中希望人工机器调度所采用的规则。算法并不保证得到最优结果，但通常所得结果与最优解相差无几，这种算法也称为启发式方法（ h e u r i s t i c s )。因此L P T方法是一种启发式机器调度方法。定理9 - 2陈述了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）。

本章的其余部分将介绍几种贪婪算法的应用。在有些应用中，贪婪算法所产生的结果总是最优的解决方案。但对其他一些应用，生成的算法只是一种启发式方法，可能是也可能不是近似算法。