数学建模常用算法—贪婪算法

百年孤独

1.2 算法思想
在贪婪算法（greedy method）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。
例1-4 [找零钱]
一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 美分， 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。
假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，否则硬币的选择将不可行（零钱总数超过6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后加入两个1美分的硬币。
贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习1）。
例1-5 [机器调度] 现有n 件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi ，si < fi 。[si , fi ] 为处理任务i 的时间范围。两个任务i，j 重指两个任务的时间范围区间有重叠，而并非是指i，j 的起点或终点重合。例如：区间[ 1，4 ]与区间[ 2，4 ]重叠，而与区间[ 4，7 ]不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。
假设有n= 7件任务，标号为a 到g。它们的开始与完成时间如图13-1a 所示。若将任务a分给机器M1，任务b 分给机器M2，. . ，任务g 分给机器M7，这种分配是可行的分配，共使用了七台机器。但它不是最优分配，因为有其他分配方案可使利用的机器数目更少，例如：可以将任务a、b、d分配给同一台机器，则机器的数目降为五台。
一种获得最优分配的贪婪方法是逐步分配任务。每步分配一件任务，且按任务开始时间的非递减次序进行分配。若已经至少有一件任务分配给某台机器，则称这台机器是旧的；若机器非旧，则它是新的。在选择机器时，采用以下贪婪准则：根据欲分配任务的开始时间，若此时有旧的机器可用，则将任务分给旧的机器。否则，将任务分配给一台新的机器。
根据例子中的数据，贪婪算法共分为n = 7步，任务分配的顺序为a、f、b、c、g、e、d。第一步没有旧机器，因此将a 分配给一台新机器（比如M1）。这台机器在0到2时刻处于忙状态。在第二步，考虑任务f。由于当f 启动时旧机器仍处于忙状态，因此将f 分配给一台新机器(设为M2 )。第三步考虑任务b, 由于旧机器M1在Sb = 3时刻已处于闲状态，因此将b分配给M1执行，M1下一次可用时刻变成fb = 7，M2的可用时刻变成ff = 5。第四步，考虑任务c。由于没有旧机器在Sc = 4时刻可用，因此将c 分配给一台新机器（M3），这台机器下一次可用时间为fc =7。第五步考虑任务g，将其分配给机器M2，第六步将任务e 分配给机器M1, 最后在第七步，任务2分配给机器M3。（注意：任务d也可分配给机器M2）。
上述贪婪算法能导致最优机器分配的证明留作练习（练习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，其长度为10。这条路径并不是有向图中从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）。
本章的其余部分将介绍几种贪婪算法的应用。在有些应用中，贪婪算法所产生的结果总是最优的解决方案。但对其他一些应用，生成的算法只是一种启发式方法，可能是也可能不是近似算法。
虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。
本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。
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 &aring;i = 1si xi 最大，并满足：n &aring;i=1xi =t 及0≤xi≤ai 。
需要指出的是：如果n &aring;i = 1ai < t，则不可能找到问题的求解方案，因为即使喝光所有的饮料也不能使婴儿解渴。
对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/ 输出作如下形式的描述：
输入：n，t，si ，ai（其中1≤i≤n，n 为整数，t、si 、ai 为正实数）。
输出：实数xi（1≤i≤n），使n &aring;i= 1si xi 最大且n &aring;i=1xi =t（0≤xi≤ai）。如果n &aring;i = 1ai <t，则输出适当的错误信息。
在这个问题中，限制条件是n &aring;i= 1xi =t 且0≤xi≤ai，1≤i≤n。而优化函数是n &aring;i= 1si xi 。任何满足限制条件的一组实数xi 都是可行解，而使n &aring;i= 1si xi 最大的可行解是最优解。
例1-2 [装载问题] 有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量都各不相同。设第i 个货箱的重量为wi（1≤i≤n），而货船的最大载重量为c，我们的目的是在货船上装入最多的货物。
这个问题可以作为最优化问题进行描述：设存在一组变量xi ，其可能取值为0或1。如xi 为0，则货箱i 将不被装上船；如xi 为1，则货箱i 将被装上船。我们的目的是找到一组xi ，使它满足限制条件n &aring;i = 1wi xi ≤c 且x i &Icirc; {0, 1}, 1 ≤i≤n。相应的优化函数是n &aring;i= 1xi 。
满足限制条件的每一组xi 都是一个可行解，能使n &aring;i= 1xi 取得最大值的方案是最优解。
例1-3 [最小代价通讯网络]
城市及城市之间所有可能的通信连接可被视作一个无向图，图的每条边都被赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点（城市）的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解是其中具有最小代价的生成树。
在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足如下限制条件：所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。

百年孤独

1.3练习
1. 证明找零钱问题（例1 3 - 4）的贪婪算法总能产生具有最少硬币数的零钱。
2. 考虑例1 3 - 4的找零钱问题，假设售货员只有有限的2 5美分， 1 0美分，
5美分和1美分的硬币，给出一种找零钱的贪婪算法。这种方法总能找出具有最少硬币数的零钱吗？证明结论。
3. 扩充例1 3 - 4的算法，假定售货员除硬币外还有50, 20, 10, 5, 和1美元的纸币，顾客买价格为x 美元和y
美分的商品时所付的款为u 美元和v 美分。算法总能找出具有最少纸币与硬币数目的零钱吗？证明结论。
4. 编写一个C + +程序实现例1 3 - 4的找零钱算法。假设售货员具有面值为1 0 0，2 0，1
0，5和1美元的纸币和各种硬币。程序可包括输入模块（即输入所买商品的价格及顾客所付的钱数），输出模块（输出零钱的数目及要找的各种货币的数目）和计算模块（计算怎样给出零钱）。
5. 假设某个国家所使用硬币的币值为1 4 , 2 , 5和1分，则例1 3 - 4的贪婪算法总能产生具有最少硬币数的零钱吗？证明结论。
6. 1) 证明例1 3 - 5的贪婪算法总能找到最优任务分配方案。
2) 实现这种算法，使其复杂性为O (nl o gn)（提示：根据完成时间建立最小堆）。
*7. 考察例1 3 -
5的机器调度问题。假定仅有一台机器可用，那么将选择最大数量的任务在这台机器上执行。例如，所选择的最大任务集合为{a,b,e}。解决这种任务选择问题的贪婪算法可按步骤选择任务，每步选择一个任务，其贪婪准则如下：从剩下的任务中选择具有最小的完成时间且不会与现有任务重叠的任务。
1) 证明上述贪婪算法能够获得最优选择。
2) 实现该算法，其复杂性应为O(nl o gn)。（提示：采用一个完成时间的最小堆）

百年孤独

1.3练习
1. 证明找零钱问题（例1 3 - 4）的贪婪算法总能产生具有最少硬币数的零钱。
2. 考虑例1 3 - 4的找零钱问题，假设售货员只有有限的2 5美分， 1 0美分，
5美分和1美分的硬币，给出一种找零钱的贪婪算法。这种方法总能找出具有最少硬币数的零钱吗？证明结论。
3. 扩充例1 3 - 4的算法，假定售货员除硬币外还有50, 20, 10, 5, 和1美元的纸币，顾客买价格为x 美元和y
美分的商品时所付的款为u 美元和v 美分。算法总能找出具有最少纸币与硬币数目的零钱吗？证明结论。
4. 编写一个C + +程序实现例1 3 - 4的找零钱算法。假设售货员具有面值为1 0 0，2 0，1
0，5和1美元的纸币和各种硬币。程序可包括输入模块（即输入所买商品的价格及顾客所付的钱数），输出模块（输出零钱的数目及要找的各种货币的数目）和计算模块（计算怎样给出零钱）。
5. 假设某个国家所使用硬币的币值为1 4 , 2 , 5和1分，则例1 3 - 4的贪婪算法总能产生具有最少硬币数的零钱吗？证明结论。
6. 1) 证明例1 3 - 5的贪婪算法总能找到最优任务分配方案。
2) 实现这种算法，使其复杂性为O (nl o gn)（提示：根据完成时间建立最小堆）。
*7. 考察例1 3 -
5的机器调度问题。假定仅有一台机器可用，那么将选择最大数量的任务在这台机器上执行。例如，所选择的最大任务集合为{a,b,e}。解决这种任务选择问题的贪婪算法可按步骤选择任务，每步选择一个任务，其贪婪准则如下：从剩下的任务中选择具有最小的完成时间且不会与现有任务重叠的任务。
1) 证明上述贪婪算法能够获得最优选择。
2) 实现该算法，其复杂性应为O(nl o gn)。（提示：采用一个完成时间的最小堆）

百年孤独

贪婪算法是应用最广泛，最广泛的算法，没有之一，所以永远不朽，人人都有贪婪之心，所以这个算法一定程度上说相对较好理解同样也非常重要，下面继续拓展一些，站在数据结构上面继续做些介绍。
程序13-6 Kruskal算法所需要的数据类型

template <class T>
class EdgeNode {
p u b l i c :
operator T() const {return weight;}
p r i v a t e :
T weight;//边的高度
int u, v;//边的端点
} ;
为了更简单地使用查找和合并策略，定义了U n i o n F i n d类，它的构造函数是程序8 - 1 6的初始化函数，U n i o n是程序8 - 1 6的加权合并函数，F i n d是程序8 - 1 7的路径压缩搜索函数。
为了编写与网络描述无关的代码，还定义了一个新的类U N e t Wo r k，它包含了应用于无向网络的所有函数。这个类与U n d i r e c t e d类的差别在于U n d i r e c t e d类中的函数不要求加权边，而U N e t Wo r k要求边必须带有权值。U N e t Wo r k中的成员需要利用N e t w o r k类中定义的诸如B e g i n和N e x t Ve r t e x的遍历函数。不过，新的遍历函数不仅需要返回下一个邻接的顶点，而且要返回到达这个顶点的边的权值。这些遍历函数以及有向和无向加权网络的其他函数一起构成了W 、
N e t w o r k类（见程序1 3 - 7）。
程序13-7 WNetwork类
template<class T>
class WNetwork : virtual public Network
{
public :
virtual void First(int i, int& j, T& c)=0;
virtual void Next(int i, int& j, T& c)=0;
} ;
象B e g i n和N e x t Ve r t e x一样，可在A d j a c e n c y W D i g r a p
h及L i n k e d W D i g r a p h类中加入函数F i r s t与N e x t。现在A d j a c e
n c y W D i g r a p h及L i n k e d W D i g r a p h类都需要从W N e t Wo r
k中派生而来。由于A d j a c e n c y W G r a p h类和L i n k e d W G r a p
h类需要访问U N e t w o r k的成员，所以这两个类还必须从U N e t Wo r k中派生而来。U N e t Wo
r k : : K r u s k a l的代码见程序1 3 - 8，它要求将Edges() 定义为N e t Work
类的虚成员，并且把U N e t Wo r k定义为E d g e N o d e的友元）。如果没有生成树，函数返回f a l s
e，否则返回t r u e。注意当返回true 时，在数组t 中返回最小耗费生成树。
程序13-8 Kr u s k a l算法的C + +代码
template<class T>
bool UNetwork<T>::Kruskal(EdgeNode<T> t[])
{// 使用K r u s k a l算法寻找最小耗费生成树
// 如果不连通则返回false
// 如果连通，则在t [ 0 : n - 2 ]中返回最小生成树
int n = Ve r t i c e s ( ) ;
int e = Edges();
/ /设置网络边的数组
InitializePos(); // 图遍历器
EdgeNode<T> *E = new EdgeNode<T> [e+1];
int k = 0; // E的游标
for (int i = 1; i <= n; i++) { // 使所有边附属于i
int j;
T c;
First(i, j, c);
while (j) { // j 邻接自i
if (i < j) {// 添加到达E的边
E[++k].weight = c;
E[k].u = i;
E[k].v = j;}
Next(i, j, c);
}
}
// 把边放入最小堆
MinHeap<EdgeNode<T> > H(1);
H.Initialize(E, e, e);
UnionFind U(n); // 合并/搜索结构
// 根据耗费的次序来抽取边
k = 0; // 此时作为t的游标
while (e && k < n - 1) {
// 生成树未完成，尚有剩余边
EdgeNode<T> x;
H.DeleteMin(x); // 最小耗费边
e - - ;
int a = U.Find(x.u);
int b = U.Find(x.v);
if (a != b) {// 选择边
t[k++] = x;
U . U n i o n ( a , b ) ; }
}
D e a c t i v a t e P o s ( ) ;
H . D e a c t i v a t e ( ) ;
return (k == n - 1);
}
2. Prim算法
与Kr u s k a l算法类似，P r i m算法通过每次选择多条边来创建最小生成树。选择下一条边的贪婪准则是：从剩余的边中，选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。最终，在所有步骤中选择的边形成一棵树。相反，在Kruskal 算法中所有入选的边集合最终形成一个森林。
P r i m算法从具有一个单一顶点的树T开始，这个顶点可以是原图中任意一个顶点。然后往T中加入一条代价最小的边（ u , v）使T&Egrave;{ (u , v) }仍是一棵树，这种加边的步骤反复循环直到T中包含n- 1条边。注意对于边（ u , v），u、v 中正好有一个顶点位于T中。P r i m算法的伪代码如图1 -14所示。在伪代码中也包含了所输入的图不是连通图的可能，在这种情况下没有生成树。图1 - 1 5显示了对图1-12a 使用P r i m算法的过程。把图1 - 1 4的伪代码细化为C + +程序及其正确性的证明留作练习（练习3 1）。
/ /假设网络中至少具有一个顶点
设T为所选择的边的集合，初始化T=
设T V为已在树中的顶点的集合，置T V= { 1 }
令E为网络中边的集合 w h i l e(E< > ) & & (| T | < > n-1) {
令（u , v）为最小代价边，其中u T V, v T V
i f（没有这种边） b re a k
E=E- { (u,v) } / /从E中删除此边
在T中加入边（ u , v）
}
if (| T | = =n- 1 ) T是一棵最小生成树
else 网络是不连通的，没有最小生成树
图13-14 Prim最小生成树算法
如果根据每个不在T V中的顶点v 选择一个顶点n e ar (v)，使得n e ar (v) &Icirc; TV 且c o st (v, n
e ar (v) )的值是所有这样的n e ar (v) 节点中最小的，则实现P r i m算法的时间复杂性为O (n2 )。下一条添加到T中的边是这样的边：其cost (v, near (v)) 最小，且v T V。
3. Sollin算法
S o l l i n算法每步选择若干条边。在每步开始时，所选择的边及图中的n个顶点形成一个生成树的森林。在每一步中为森林中的每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。将所选择的边加入要创建的生成树中。注意一个森林中的两棵树可选择同一条边，因此必须多次复制同一条边。当有多条边具有相同的耗费时，两棵树可选择与它们相连的不同的边，在这种情况下，必须丢弃其中的一条边。开始时，所选择的边的集合为空。若某一步结束时仅剩下一棵树或没有剩余的边可供选择时算法终止。
图1 - 6给出了初始状态为图1-12a 时，使用S o l l i n算法的步骤。初始入选边数为0时的情形如图13-12a 时,森林中的每棵树均是单个顶点。顶点1，2，.，7所选择的边分别是(1.6), (2,7),(3,4), (4,3), (5,4),
(6,1), (7,2)，其中不同的边是( 1 , 6 )，( 2 , 7 )，(3,4) 和( 5 , 4 )，将这些边加入入选边的集合后所得到的结果如图1 3 - 1 6 a所示。下一步具有顶点集{ 1 , 6 }的树选择边( 6 , 5 )，剩下的两棵树选择边( 2 , 3 )，加入这两条边后已形成一棵生成树，构建好的生成树见图1 3 - 6 b。S o l l i n算法的C + +程序实现及其正确性证明留作练习（练习3 2 )。