贪婪算法

下,。决策一旦作出～就不可再更改。作出贪婪决策的依据称为贪婪准则,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～其长度为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,。 本章的其余部分将介绍几种贪婪算法的应用。在有些应用中～贪婪算法所产生的结果总是最优的解决方案。但对其他一些应用～生成的算法只是一种启发式方法～可能是也可能不是近似算法。 练习 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.3.1 货箱装船 这个问题来自例1 - 2。船可以分步装载～每步装一个货箱～且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪准则:从剩下的货箱中～选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小～从而可以装载更多的货箱。根据这种贪婪策略～首先选择最轻的货箱～然后选次轻的货箱～如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。 例1-7 假设n =8, [w1 , ... w8 ]=[100,200,50,90,150,50,20,80], c= 4 0 0。利用贪婪算法时～所考察货箱的顺序为7 , 3 , 6 , 8 , 4 , 1 , 5 , 2。货箱7 , 3 , 6 , 8 , 4 , 1的总重量为3 9 0个单位且已被装载～剩下的装载能力为1 0个单位～小于剩下的任何一个货箱。在这种贪婪解决算法中得到[x1 , ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且,xi = 6。 定理1-1 利用贪婪算法能产生最佳装载。 证明可以采用如下方式来证明贪婪算法的最优性:令x = [x1 , ..., xn ]为用贪婪算法获得的解～令y =[ y1 , ..., yn ]为任意一个可行解～只需证明n ,i= 1xi ?n ,i= 1yi 。不失一般性～可以假设货箱都排好了序:即wi?wi + 1,1?i?n,。然后分几步将y 转化为x～转换过程中每一步都产生一个可行的新y～且n ,i = 1yi 大于等于未转化前的值～最后便可证明n ,i = 1xi ?n ,j = 1yi 。 根据贪婪算法的工作过程～可知在[0, n] 的范围内有一个k～使得xi =1, i?k且xi =0, i>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规定

关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定