1 、贪婪算法
贪婪算法
贪婪算法
转自
http://202.113.96.10/ini/arithetics/No11.htm ;
贪婪算法
虽然设计一个好的求解算法更像是一门艺术,而不像是技术,但仍然存在一些行之有效的能够用于解决许
多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,
为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达
到要求,这时就必须寻求另外的方法来求解该问题。
本章首先引入最优化的概念,然后介绍一种直观的问题求解方法:贪婪算法。最后,应用该算法给出货箱
装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案
。
【发表回复】 【查看 CU
论坛原帖】 【关闭】
--------------------------------------------------------------------------------
无双 回复于: 2003-04-23 20:03:58
1.1 最优化问题
本章及后续章节中的许多例子都是最优化问题( optimization problem ) ,每个最优化问题都包含一组限
制条件( c o n s t r a i n t )和一个优化函数( optimization function ) ,符合限制条件的问题求 解
方案称为可行解 (
feasible solution
) , 使优化函数取得最佳值的可行解称为最优解 (
optimal solutio n
)。
例 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 < P>
在这个问题中,限制条件是 n &i= 1xi =t 且 0 ≤ xi ≤ ai
,
1 ≤ i ≤ n 。而优化函数是 n &i= 1si xi 。任何 满
足限制条件的一组实数 xi 都是可行解,而使 n &i= 1si xi 最大的可行解是最优解。
例 1-2 [ 装载问题 ] 有一艘大船准备用来装载货物。 所有待装货物都装在货箱中且所有货箱的大小都一样
,
但货箱的重量都各不相同。设第 i 个货箱的重量为 wi ( 1 ≤ i ≤ n ) ,而货船的最大载重量为 c ,我们的目 的
是在货船上装入最多的货物。
这个问题可以作为最优化问题进行描述: 设存在一组变量 xi , 其可能取值为 0 或 1 。 如 xi 为 0 , 则货箱 i 将
不被装上船; 如 xi 为 1 , 则货箱 i 将被装上船。 我们的目的是找到一组 xi , 使它满足限制条件 n &i = 1wi
xi ≤ c 且 x i ? {0, 1}, 1 ≤ i ≤ n 。相应的优化函数是 n &i= 1xi 。
满足限制条件的每一组 xi 都是一个可行解,能使 n &i= 1xi 取得最大值的方案是最优解。
例 1-3 [ 最小代价通讯网络 ] 城市及城市之间所有可能的通信连接可被视作一个无向图, 图的每条边都被 赋
予一个权值,权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点(城市)的连
通子图都是一个可行解。设所有的权值都非负,则所有可能的可行解都可表示成无向图的一组生成树,而
最优解是其中具有最小代价的生成树。
在这个问题中,需要选择一个无向图中的边集合的子集,这个子集必须满足如下限制条件:所有的边构成
一个生成树。而优化函数是子集中所有边的权值之和。
--------------------------------------------------------------------------------
无双 回复于: 2003-04-23 20:06:38
[color=blue:575926ef9c][size=18:575926ef9c]
1.2 算法思想
[/size:575926ef9c][/color:575926ef9c]
在贪婪算法( greedy method )中采用逐步构造最优解的方法。在每个阶段,都作出一个看上去最优的决 策
(在一定的标准下) 。 决策一旦作出, 就不可再更改。 作出贪婪决策的依据称为贪婪准则 (
greedy criter ion
)。
[color=blue]
例 1-4 [ 找零钱 ]
[color]
例 1-4 [ 找零钱 ] 一个小孩买了价值少于 1 美元的糖, 并将 1 美元的钱交给售货员。 售货员希望用数目最少 的
硬币找给小孩。假设提供了数目不限的面值为 2 5 美分、 1 0 美分、 5 美分、及 1 美分的硬币。售货员分步骤
组成要找的零钱数,每次加入一个硬币。选择硬币时所采用的贪婪准则如下:每一次选择应使零钱数尽量
增大。为保证解法的可行性(即:所给的零钱等于要找的零钱数) ,所选择的硬币不应使零钱总数超过最 终
所需的数目。
假设需要找给小孩 6 7 美分,首先入选的是两枚 2 5 美分的硬币,第三枚入选的不能是 2 5 美分的硬币,否 则
硬币的选择将不可行(零钱总数超过 6 7 美分) ,第三枚应选择 1 0 美分的硬币,然后是 5 美分的,最后加入
两个 1 美分的硬币。
贪婪算法有种直觉的倾向, 在找零钱时, 直觉告诉我们应使找出的硬币数目最少 (至少是接近最少的数目
)。
可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少(见练习 1
) 。
--------------------------------------------------------------------------------
无双 回复于: 2003-04-23 20:08:27
[color=blue:d3034c61ed]
例 1-5 机器调度
[/color:d3034c61ed]
现有 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 g n)
的贪婪算法: 首先采用一个复杂性为 O (nl o gn) 的排序算法 (如堆排序) 按 Si 的递增次序排列各个任
务,
然后使用一个关于旧机器可用时间的最小堆。
[color=blue:d3034c61ed] 例 1-6 最短路径 [/color:d3034c61ed]
给出一个有向网络,路径的长度定义为路径所经过的各边的耗费之和。要求找一条从初始顶点 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 n a l
g o r i t h m
) 。
本章的其余部分将介绍几种贪婪算法的应用。 在有些应用中, 贪婪算法所产生的结果总是最优的解决方案
。
但对其他一些应用,生成的算法只是一种启发式方法,可能是也可能不是近似算法。
--------------------------------------------------------------------------------
无双 回复于: 2003-04-23 20:09:25
[color=blue:aa7ef0ccf5]
练习
[/color:aa7ef0ccf5]
练习
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) 。 (提示:采用一个完成时间的最小堆)
--------------------------------------------------------------------------------
无双 回复于: 2003-04-23 20:10:09
[color=blue:68805513b9]
[size=18:68805513b9]
1.3 应用
[/size:68805513b9]
[/color:68805513b9]
[color=blue:68805513b9]1.3.1 货箱装船 [/color:68805513b9]