78 第四章 贪心算法
§1.贪心算法基本思想
找零钱 假如售货员需要找给小孩67美分的零钱。现在，售货员手中只有25美分、10美分、5美分和1美分的硬币。在小孩的催促下，售货员想尽快将钱找给小孩。她的做法是：先找不大于67美分的最大硬币25美分硬币，再找不大于67－25＝42美分的最大硬币25美分硬币，再找不大于42－25＝17美分的最大硬币10美分硬币，再找不大于17－10＝7美分的最大硬币5美分硬币，最后售货员再找出两个1美分的硬币。至此，售货员共找给小孩6枚硬币。售货员的原则是拿尽可能少的硬币个数找给小孩。
从另一个角度看，如果售货员将捡出的硬币逐一放在手中，最后一起交给小孩，那么售货员想使自己手中的钱数增加的尽量快些，所以每一次都尽可能地捡面额大的硬币。
装载问题 有一艘大船用来装载货物。假设有n 个货箱，它们的体积相同，重量分别是，货船的最大载重量是c。目标是在船上装更多个数的货箱该怎样装？当然，最简单的作法是“捡重量轻的箱子先往上装”，这是一种贪心的想法。如果用表示装第个货箱，而n w w w ,,21"1=i x i 0=i x 表示不装第i 个货箱，则上述问题是解优化问题：
求，使得
n x x x ,,,21" (4.1.1)
∑=n
i i x 1max 满足条件 (4.1.2)
1
w ,0n
i i i i x c x =≤=∑,1贪心算法，顾名思义，是在决策中总是作出在当前看来是最好的选择。例如找零钱问题中，售货员每捡一个硬币都想着使自己手中的钱尽快达到需要找钱的总数。在装载问题中，每装一个货箱都想着在不超重的前提下让船装更多的箱子。但是贪心方法并未考虑整体最优解，它所作出的选择只是在某种意义上的局部最优选择。当然，在采用贪心算法时未必不希望结果是整体最优的。事实上，有相当一部分问题，采用贪心算法能够达到整体最优，如前面的找零钱问题以及后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问题等。为了更好理解贪心算法，我们将装载问题稍加推广，考虑可分割的背包问题。
背包问题 已知容量为M 的背包和件物品。第i 件物品的重量为，价值
n i w
79
是。因而将物品i 的一部分放进背包即获得的价值。问题是：怎样装包使所获得的价值最大？即是如下的优化问题：
i p i x i i x p ∑≤≤n
i i i x p 1max
(4.1.3)
n
i w p x M
x w i i i n i i i ≤≤>>≤≤≤∑≤≤1,0,0,101 (4.1.4)
采用贪心算法，有几种原则可循：a）.每次捡最轻的物品装；b）.每次捡价值最大的装；c）.每次装包时既考虑物品的重量又考虑物品的价值，也就是说每次捡单位价值i i w p 最大的装。按原则a 来装只考虑到多装些物品，但由于单位价值未必高，总价值可能达不到最大；按原则b 来装，每次选择的价值最大，但同时也可能占用了较大的空间，装的物品少，未必能够达到总价值最大。比较合理的原则是c）。事实上，按照原则c）来装，确实能够达到总价值最大。
程序4-1-1 背包问题贪心算法
proc GreedyKnapsack (p, w, M, x, n) //价值数组p[1..n]、重量数组
// w[1..n]，它们元素的排列顺序满足p[i]/w[i]≥p[i+1]/w[i+1]; // M 是背包容量，x 是解向量
float p[1..n], w[1..n], x[1..n], M, rc; integer i, n;
x:= 0; // 将解向量初始化为零 rc:= M; // 背包的剩余容量初始化为M for i to n do
if w[i] > rc then break; end{if} x[i]:=1; rc:=rc-w[i];
end{for} if i ≤n then
x[i]:=rc/w[i];
end{if}
end{GreedyKnapsack}
定理4.1.1 如果][/][]2[/]2[]1[/]1[n w n p w p w p ≥≥≥",则GreedyKnapsack 对于给定的背包问题实例生成一个最优解。
证明 设),,,(21n x x x x "=是GreedyKnapsack所生成的解，但不是最优解。
80 因而必有某个不为1。不妨设是第一个这样的分量。于是，当i x j x j i <≤1时，；当1=i x j i =时，；当10<≤i x n i j ≤<时，0=i x ，而且M x w i i =∑。因为x 不是最优解，必存在解向量,使得),,,(21n y y y y "=∑∑>i i i i x p y p 。设是使得的最小下标，则y k k k x y ≠k < x k . 这是因为，当j k <时，1=k x ,上述不等式自然成立；当时，若x j k ≥k 1 11 1 k n k i i k k i i i i k k i i k i w y w y w y w x w x ??==+=++ >+= ∑1 n i i i w x M ==∑ y 不是解向量，矛盾。 因是比y x 更优的解，不失一般性，可以假定。于是 M y w n i i i =∑=1 （当k k k i i i n k i i i k k k i i i x w x w y w y w y w +=+ +∑∑∑?=+=?=1 1 1 1 1 ∑+=+ j k i i i x w 1 j k < 时） 。 再由，有。现在取新的向量k k x y <0)(1 >?≥∑+=k k k n k i i i y x w y w ),,,(21n z z z z "=满 足 ，1111,,,k k k k z y z y z x ??==="n n k k y z y z ≤≤≤≤++0,,011" , )()(1k k k n i k i i i y z w z y w ?=?∑≤≤+ 这样的向量是存在的，而且是背包问题的可行解，因为 z M y w y w y w z w z w y w z w n i i i n i k i i k i i i n i k i i k k k i i i n i i i ≤= +=++=∑∑∑∑∑∑≤≤≤≤?≤≤≤≤+?≤≤≤≤11 111 11 至此，我们找到一个新的解向量。以下证明它的总价值不小于z y 的总价值： 111()/()/i i i i k k k k k i i i i i i n i n k i n p z p y z y w p w y z w p ≤≤≤≤+≤≤=+?? ?∑∑∑ w 81 111()()/i i k k k i i i k k i n k i n i i i n p y z y w y z w p w p y ≤≤+≤≤≤≤??≥ +???????=∑∑∑中间的不等式是由于当时有而得。但是与k i >][/][][/][i w i p k w k p ≥z x 的第一个不同分量的位置比y 与x 的第一个不同的分量的位置至少向后推迟了一个。以代替z y 进行上面的讨论，我们又可以找到新的解向量'，如此等等，由于分量的个数n 有限，这样的过程必到某一步停止，最后找到解向量,它和z *y x 有相同的分量，又比x 有更大的总价值，矛盾。这个矛盾源于x 不是最优解的假设。证毕 贪心算法主要用于处理优化问题。每个优化问题都是由目标函数和约束条件组成。满足约束条件的解称为可行解，而那些使得目标函数取得最大（最小）值的可行解称为最优解。如背包问题是一个优化问题，式(4.1.3)中的函数是目标函数，而(4.1.4)式描述的要求是约束条件，这里优化是使目标函数取最大值。 贪心算法在每一步的决策中虽然没有完全顾忌到问题整体优化，但在局部择优中是朝着整体优化的方向发展的。为此，贪心算法首先要确定一个度量准则（称为贪心准则），每一步都是按这个准则选取优化方案。如背包问题的贪心准则是选取单位价值p/w 最大物品；而装载问题的贪心的准则是选取最轻的货箱；找零钱问题所用的贪心准则是选取面值最大的硬币。对于一个给定的问题，初看起来，往往有若干种贪心准则可选，但在实际上，其中的多数都不能使贪心算法达到问题的最优解。如背包问题的下面实例： n=3, M=20, p=(25, 24, 15), w=(18,15,10) 如果以价值最大为贪心准则，则贪心算法的执行过程是：首先考虑将物品1装包，此时获得效益值25，包的剩余容量是2。然后考虑将物品2装包，但物品2的重量15超出包的剩余容量，只能装入该种物品的2/15，此时获得的总效益值为 25+24×2/15=28.2。 这样得到的可行解（1，2/15，0）并不是最优解。 事实上，如果以单位价值最大为贪心准则，则贪心算法的执行过程是：先计算出各个物品的单位价值(25/18, 24/15, 15/10)=(1.389, 1.6, 1.5)。首先考虑单位价值大的物品装包，即将物品2装包，此时获得效益值24，背包的剩余容量是5。然后考虑装物品3，由于物品3的重量超出背包的剩余容量，只能装入该物品5/15=1/2, 至此背包已经装满，所得的总的效益值为24+15/2=31.5。比前面的装法的效益值大。实践证明，选择能产生最优解的贪心准则是设计贪心 82 算法的核心问题。以下给出贪心算法流程的伪代码。 程序4-1-2 贪心算法抽象化控制流程 proc Greedy(A, n) // A[1:n]代表那个输入 solution={}; //解向量初始化为空集 for i to n do x:=Select(A); if Feasible(solution, x) then solution:=Union(solution, x); end{if} end{for} return(solution); end{Greedy} 这里Select(A)是按照贪心准则选取A中的输入项； Feasible(solution, x)是判断已知的解的部分solution与新选取的x的结合Union(solution, x)是否是可行解。过程Greedy描述了用贪心策略设计算法的主要工作和基本控制流程。一旦给出一个特定的问题，就可将Select，Feasible和Union具体化并付诸实现。 §2. 作业排序问题 z活动安排问题 我们首先从活动安排这一简单问题入手。该问题要求高效安排安排安排一系列争用争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能够兼容地使用公共资源。 问题：已知n个活动 E={1, 2, … ,n}，要求使用同一资源，第k个活动要 求的开始和结束时间为s k , f k , 其中s k k , k=1, 2, … , n .活动k与活动j称为 相容的如果s k >f j 或者s j >f k 。活动安排问题就是要在所给的活动集合中选出最大 (活动个数最多)的相容活动子集。 解决这个问题的基本思路是在安排时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的时间，从而达到安排最多活动的目的。据此，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组s和f存储，并使得数组中 元素的顺序按结束时间非减排列：f 1≤ f 2 ≤…≤ f n 。 83 算法 4-2-1 活动安排贪心算法伪代码 proc GreedyAction(s, f，n) // s[1..n]、f[1..n]分别代表n项活动的 //起始时间和结束时间, 并且满足f[1]≤ f[2]≤…≤ f[n] j:=1; solution:={1}; //解向量初始化 for i from 2 to n do if s i ≥f j then solution:=solution ∪ {j}; // 将j加入解中 j:=i; end{if} end{for} return(solution); end{GreedyAction} 例4.2.1 待安排的11个活动的开始时间和结束时间按结束时间的非减次序排列如下： 表1 一个作业安排表 k 1 2 3 4 5 6 7 8 9 10 11 s[k] 1√ 3 0 5√ 3 5 6 8√8 2 12√ f[k] 4 5 6 78 9 10 1112 13 14 解集合为 {1,4,8,11}.容易证明算法GreedyAction所得到的解是最优解。 z带期限的单机作业安排问题 为使问题简化，我们假定完成每项作业所用的时间都是一样的，如都是1。带期限的单机作业安排问题陈述如下： 已知n项作业 E={1, 2, … ,n}，要求使用同台机器完成（该台机器在同一时刻至多进行一个作业），而且每项作业需要的时间都是1。第k项作业要求在时 刻f k 之前完成, 而且完成这项作业将获得效益p k ，k=1, 2, … , n 。作业集E的 子集称为相容的，如果其中的作业可以被安排由一台机器完成。带限期单机作业安排问题就是要在所给的作业集合中选出总效益值最大的相容子集。 这个问题可以考虑用贪心算法求解。容易想到贪心准则应该是： 尽量选取效益值大的作业安排 但由于起始时间是一个区间[0,f i -1]，可以将后面考虑的作业插到前面安排时剩余的空闲时间片里。 84 程序 4-2-2 带限期作业安排的贪心算法伪代码 proc GreedyJob (f, p, n) //f[1..n]和p[1..n]分别代表各项作业的 //限期和效益值，而且n项作业的排序满足：p 1 ≥ p 2 ≥ … ≥ p n local J; J:={1};//初始化解集 for i from 2 to n do if J ∪ {i} 中的作业是相容的 then //此步验证需要认真设计 J:= J ∪ {i}; // 将i 加入解中 end{if} end{for} end{GreedyJob} 定理4.2.1 算法GreedyJob 对于作业排序问题总是得到最优解。 证明：假设贪心算法所选择的作业的集合J 不是最优解，则一定有相容的作业子集I，其产生更大的效益值。假定I 是具有最大效益值的相容作业子集中使得I ∩J 最大者，往证。 J I =反证法：若不成立，则这两个作业集J I =I 和之间没有包含关系。这是因为算法GreedyJob的特性和假定I产生的效益值比J的效益值更大。假设a是J\I 中具有最大效益的作业，于是，J中比a具有更大效益的作业(如果有的话)都应该在I中。现在将作业a加入到I中，得I J *={a}∪I.由I的极大性知，I *一定是不相容的.从而，对于I的任何一个调度表S，在f a 时刻前的时间片都已经被I中的作业占用。假定S是I的这样一个调度表：在f a 时刻之前最大限度地安排了I\J中的作业。如果S中f a 时刻以前的作业仍然都是J中的，则I ∩J中结束时刻不晚于f a 的作业至少有f a 个。但a ?I ∩J,这与J的相容性矛盾。因此，S中必有某个作业b ∈I\J,其被安排在f a 时刻之前的时间片上。在所有这样的作业b中选择结束时刻最晚的。由于a的选法以及b ∈I\J，必然有p a ≥p b 。不然，按照算法，b将先于a考虑加入到J中。令J * =I * \{b}，则J * 必然具有最大效益，而且|J * ∩I|>|J ∩I|,这与I的选取矛盾。故J具有最大效益。 证毕 例4.2.2 设n=7, (p 1, p 2,… , p n )=(35,30,25,20,15,10,5), (d 1, d 2,… ,d n )=(4,2,4,3,4,8,3), 算法GreedyJob 的执行过程可描述如下： d 1； d 2, d 1；d 2, d 1，d 3；d 2, d 4, d 1，d 3； d 2, d 4, d 1， d 3, d 6； 4； 2，4； 2，4, 4；2， 3, 4, 4； 2， 3, 4, 4， 8； 85 这里涉及到如何判断 “J ∪ {i} 中的作业是相容的”。如果每选入一个作业i 的期限为t，J 中至少有t 个作业的期限不晚于t，则J ∪ {i}一定是不相容的。反之，若J 中期限不晚于t 的作业少于t 个，则作业i 比可插入到作业集J 中，即J ∪ {i}一定是相容的。因而，J ∪ {i}的相容性判断最坏情况下需要|J|次比较。上述算法在最坏情况下的时间复杂度为。实现这一程序的伪代码如下： 2()O n 程序 4-2-3 带期限作业安排问题贪心算法 proc GreedyJobS (D,J,n,k) //D(1),…,D(n)是期限值，作业已按p 1 ≥ p 2 ≥ … ≥ p n 排序。J(i)是 //最优解中的第i 个作业。终止时，D(J(i))≤ D(J(i+1))，1≤i ≤k integer D[0..n],J[0..n],i,k,n,r D(0):=0; J(0):=0; //初始化 k:=1; J(1):=1; //计入作业1，k 表示当前选择的作业个数 for i from 2 to n do //按p 的非增次序考虑作业，找i 的位置，并检查插入的可能性 r:=k; while D(J(r))>D(i) and D(J(r))<>r do r:=r-1; end{while}; //期限不晚于D(i)的作业个数小于D(i)时 if D(J(r))≤ D(i) and D(i)>r then for j from k to r+1 by –1 do //给作业i 腾出位置 J(j+1):=J(j); end{for}; J(r+1):=i; k:=k+1; end{if}; end{for}; end{GreedyJobS} 上述算法的基本思路是将J中的作业按照期限先后排列，d i1, d i2,… , d ik ，然后，将D(i)从后向前比较，如果判断出J ∪ {i}是相容的，即算法中的语句： if D(J(r))≤ D(i) and D(i)>r 则将作业i 插到第一个（从后向前数）限期不超过它的限期的作业之后，即算法中的语句： 86 J(r+1):=i; 为避免调度表调整，将算法GreedyJob稍做改进：在每次选择作业时，在调度表中尽量地向后分配时间片，这样好为后面的作业安排留下更多的空间: 1，[3,4]; 1,2,[3,4],[1,2]; 1,2,3,[3,4],[1,2],[2,3]; 1,2,3,4,[3,4],[1,2],[2,3],[0,1]; 1,2,3,4,6,[3,4], [1,2],[2,3],[0,1],[7,8]. 根据该思路构造的算法时间复杂度为O(n)（参看快速作业调度.doc）. z多机调度问题 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为t i 。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业分段处理。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。 这是一个NP完全问题，到目前为止还没有一个有效的解法。利用贪心策略，有时可以设计出较好的近似解。可以采用贪心准则：需要长时间处理的作业优先处理。 例4.2.3 设有7项独立的作业{1,2,3,4,5,6,7},要由三台机器M 1, M 2 , M 3 处 理。各个作业所需要的处理时间分别为{2,14,4,16,6,5,3}.将作业标号按它们所需时间的长短排列：[4, 2, 5, 6, 3, 7,1].首先将作业4安排给机器M 1 处理， 此时，机器M 1被占用的时间是16，而机器M 2 , M 3 被占用的时间都是零，所以，应 将作业2安排给机器M 2 来处理，作业5应安排给机器M 3 来处理，至此，机器M 1 , M 2 , M 3 被占用的时间分别是16、14、6。接下去应安排作业6，因为机器M 3 最早 空闲，所以作业6应安排给机器M 3。此时，机器M 1 , M 2 , M 3 分别在16、14、11 时刻开始空闲。所以下面将要安排的作业3安排给机器M 3。此时，机器M 1 , M 2 , M 3 分别在16、14、15时刻开始空闲。即将安排的作业7应安排给机器M 2 ，此时， 机器M 1, M 2 ,M 3 分别在时刻16、17、15开始空闲。即将安排的作业1应安排给机 器M 3 。如此全部作业均已安排完毕，所需要的时间是17。这里采用的调度方案是：将需要时间最长的未被安排作业首先安排给能够最早空闲下来的机器处理。 下面的图描述了上述例子的算法执行过程。 机器M 1 机器M 2 机器M 3 87 §3. 最优生成树问题 考虑无向图G=(V, E)，不妨假定该图代表城市间的交通情况，顶点代表城市，边代表连接两个城市的可能的交通线路。现在将每条边赋予一个权值，这些权可以代表建造该条线路的成本、交通线的长度或其它信息。这样得到一个赋权图。在实际问题中，人们往往希望在结构上选择一组交通线，它们连通所有的城市并且具有最小的建造成本这个问题相当于求取连通赋权图的具有最小权值的生成树。我们称之为最优生成树。贪心方法可以很好地解决此类问题。在此介绍两种算法：Prim算法和Kruskal算法。 Prim算法的基本思想： 1). 选择图G的一条权值最小的边e 1 ，形成一棵两点一边的子树； 2). 假设G的一棵子树T已经确定； 3). 选择G的不在T中的具有最小权值的边e，使得T∪{e}仍是G的一棵子树。 下面两个图给出Prim算法和Kruskal算法的最优生成树产生过程。 Prim 算法 (1,2) (2,6) (6,3) (6,4) (3,5) (1,2) (6,3) (6,4) (6,2) (5,3) Kruskal 算法 Kruskal算法的基本思想： 1). 选择图G的一条权值最小的边e 1 ； 2). 假设已经选好G的一组边L={e 1,e 2 ,…,e k }; 88 3). 选择G的不在L中的具有最小权值的边e k+1，使得L∪{e k+1 }诱导出的G的子 图不含G的圈。 程序4-3-1 Prim最小生成树算法伪代码 proc PrimTree(E,COST,n,T,mincost) //E是图G的边集，COST是G的带权 //邻接矩阵。计算一棵最小生成树T并把它作为一个集合存放到数组 //T[1..n-1,1..2]中，这棵树的权值赋给mincost 1 real COST[1..n,1..n],mincost; 2 i nteger NEAR[1..n],n,i,j,k,s,T[1..n-1,1..2]; 3 (k,s):= 权值最小的边； 4 mincost:＝COST[k,s]; 5 (T[1,1],T[1,2]):=(k,s); //初始子树 6 for i to n do //将NEAR赋初值（关于初始子树T） 7 if COST[i,s] 8 NEAR(i)=s; 9 else NEAR(i)=k; 10 end{if} 11 end{for} 12 NEAR(k):=0,NEAR(s):=0; 13 for i from 2 to n-1 do //寻找T的其余n-2条边 14 choose an index j such that NEAR(j)≠0 and COST[j,NEAR(j)] is of minimum value; 15 (T[i,1],T[i,2]):=(j,NEAR(j)); // 加入边（j，NEAR(j)） 16 mincost:=mincost+COST[j,NEAR(j)]; 17 NEAR(j):=0; 18 for s to n do //更新NEAR（关于当前子树T） 19 if NEAR(s)≠0 and COST[s,NEAR(s)]>COST[s,j] then 20 NEAR(s):=j; 21 end{if} 22 end{for} 23 end{for} 24 if mincost ≥∞then 25 print(‘no spanning tree’); 26 end{if} 27 end{PrimTree} 89 这里，树T的元素为(T[i,1],T[i,2]),其中T[i,1],T[i,2]代表第i条边的两个 端点。NEAR(j)表示顶点j的以最小权的边邻接T的一个顶点。 PrimTree算法的时间复杂度分析： 语句3需要O(|E|)的时间；语句6至语句11的循环体需要时间为O(n)； 语句18至22的循环体需要时间O(n); 语句14至17需要时间O(n); 语句13至23的循环体共需要时间O(n2)。 所以,PrimTree算法的时间复杂度为O(n2). 为叙述Kruskal算法，我们引进数据结构min-堆：它是一个完全二叉树，其中每个结点都有一个权值，而且该二叉树满足：每个结点的权值都不大于其儿子的权值。min-堆的根具有最小的权值。 程序4-3-2 Kruskal最优生成树算法伪代码 proc KruskalTree(E,COST,n,T,mincost)//说明同算法PrimTree 1 real mincost, COST[1..n,1..n]; 2 integer Parent[1..n],T[1..n-1],n; 3 以带权的边为元素构造一个min-堆; 4 Parent:=-1; //每个顶点都在不同的集合中; 5 i:= 0; mincost:= 0; 6while i 7 从堆中删去最小权边（u，v）并重新构造min-堆 8 j:= Find(u); k:= Find(v); 9 if j≠k then //保证不出现圈 10 i=:i+1; T[i,1]:=u; T[i,2]:=v; 11 mincost:=mincost+COST[u,v]; 90 12 Union(j,k); //把两个子树联合起来 13end{if} 14 end{while} 15 if i≠n-1 then 16 print(‘no spanning tree’); 17 end{if} 18 return; 19end{KruskalTree} 定理4.3.1 Kruskal算法对于每一个无向连通赋权图产生一棵最优树。 证明：设T是用Kruskal算法产生的G的一棵生成树，而T’是G的一棵最优生成树且使得|E(T′)∩E(T)|最大。用E(T)表示树T的边集，w(e)表示边e的权值，而边集E的权值之和用w(E)表示。以下证明E(T))=E(T′).反假设E(T)≠E(T′),因为|E(T)|=|E(T′)|,所以E(T)与E(T′)没有包含关系。设e是E(T)\E(T′)中权值最小的 边。将e添加到T′中即得到T′的一个圈：e，e 1 ,e 2 ,…,e k 。因为T是树，诸e i 中至 少有一个不属于E(T)。不妨设e i 不属于E(T),则必然有w(e)≤w(e i )。否则，由 w(e)>w(e i )以及E(T)中比e权值小的边都在T′中，e i 同这些边一起不含有圈，因而， 按Kruskal算法，e i 将被选到E(T)中，矛盾。在T′中去掉边e i ，换上边e，得到G的 一棵新的生成树T′′,这棵树有两个特点： a). T′′的权值不大于T′的权值，因而与T′有相等的权值； b).|E(T′′)∩E(T)| > |E(T′)∩E(T)|. a)说明T′′也是一棵最优树，而b)说明与T′取法相悖。因此E(T) = wE(T’)，T 是最优生成树。 证毕 §4 单点源最短路径问题 问题：已知一个赋权有向图G=(V,E，w),求由G中某个指定的顶点v 出发到其它各个顶点的最短路径。 路径长度 (1) v0v2 10 (2) v0v2v3 25 (3) v0v2v3v145 (4) v0v445 从v0到其它各顶点的最短距离 91 对于一般的单点源最短路径问题，我们采用逐条构造最短路径的办法， 用 迄今已生成的所有路径长度之和为最小 作为贪心准则，这要求，每一条已被生成的单独路径都必须具有最小长度。假定已经构造了k条最短路径，则下面要构造的路径应该是下一条最短长度的最短度路径。现记这k条最短路径的终点之集为S，为陈述方便，也将v 0放于S中。如果V\S不是空集，则从v 0到V\S中顶点的最短路径中应该有一条最短的，比如是v 0到v k+1的最短路径P： P=v 0u 1…u s-1u s v k+1 (4.4.1) 显然，P 1=v 0u 1…u s-1u s 应是v 0到u s 的最短路径，因而由S的定义和选定的贪心准则，u s 应属于S。同理，路径P上其它顶点u i 也都在S中。所以，由v 0出发的新的最短路径一定是某个已有的最短路径向前延伸一步。如果用Dist(v i )记从v 0到S中顶点v i 的最短路径的长度，而图G中的顶点w依其属于S与否分别记之为S(w)=1或S(w)=0，则从v 0出发，新的最短路径的长度应该是 = )(S D )},()({min 0 )(,1)(w u COST u Dist w S u S +== (4.4.2) 满足(4.4.2)式的顶点w被选择加入S，新的最短路径就是从v 0出发到w的最短路径,而此时的Dist(w)=D(S)，S被更新为}{'w S S ∪=,后者可以由更新w的（集合）特征值来实现：S(w)=1(原来S(w)=0).上述算法思想是Dijkstra(迪杰斯特)提出的。 程序4-4-1 Dijkstra 最短路径算法伪代码 proc DijkstraPaths (v,COST,n,Dist,Parent)//G 是具有n 个顶点 //{1,2,…,n}的有向图， v 是G 中取定的顶点，COST 是G 的邻接矩阵, //Dist 表示v 到各点的最短路径之长度，Parent 表示各顶点在最短路径//上的前继。 bool S[1..n]; float COST[1..n,1..n],Dist[1..n]; integer u,v,n,num,i,w; 1 for i to n do //将集合S 初始化为空 2 S[i]:=0; Parent[i]:=v; Dist[i]:=COST[v,i]; 3 end{for} 4 S[v]:=1; Dist[v]:=0; Parent[v]:=-1;//首先将节点v 记入S 5 for i to n-1 do //确定由节点v 出发的n-1条最短路 6 选取顶点w 使得)}({min )(0 )(u Dist w Dist u S == 7 S[w]:=1； 8 while S[u]=0 do //修改v 通过S 到达S 以外的结点u 的最小距离值 92 9if Dist[u]> Dist[w]+COST[w,u] then 10 Dist[u]:=Dist[w]+COST[w,u]; 11 Parent[u]:=w; 12end{if} 13end{while} 14 end{for} 15End{DijkstraPath} S Θ 赋权连通图G G的最优生成树G的一棵单点源最短路径生成树 93 所有由v到达各顶点的最短路径并起来构成图G的一棵生成树，称为单点源最短路径树。上页的图给出了一个连通赋权图G及它的两棵生成树：最优生成树和单点源最短路径树。 §5 Huffman编码 哈夫曼编码是用于数据文件压缩的一个十分有效的编码方法，其压缩率通常在20％～90％之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个0,1串，以表示各个字符的最优表示方式。下表给出的是具有100,000个字符文件中出现的6个不同的字符的出现频率统计。 表 4-5-1 字符出现频率表 不同的字符 a b c d e f 频率（千次） 45 13 12 16 9 5 定长码 000 001 010 011 100 101 变长码 0 101 100 111 1101 1100 如果采用定长码，则每个字符至少需用三位，该文件总共需要300,000位；如果采用上面所列变长码，则该文件需用 （45×1＋13×3＋12×3＋16×3＋9×4＋5×4）×1000＝224,000位， 总码长减少了25%。 一般的编码都是沿一个方向连续地写下0,1子串，比如从左到右、从上到下。解码时也是以同样的方向逐字地搜索。为了使解码唯一，必须使用一个规则。前缀码即是一种规则，它要求表示任何一个字符的0,1字串都不能是表示另一个字符的0,1字串的前部。比如，若用01表示字符a，则表示其它字符的字串不能是具有形式：01…。 可以用一棵二叉树来表示前缀编码。用树叶代表给定的字符，并将给定字符的前缀码看作是从树根到代表该字符的树叶的一条道路。代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 在一般情况下，若C是编码字符集，则表示其最优前缀码的二叉树中恰有 |C| 个叶结点，每个叶结点对应于一个字符。这样的二叉树的每个不是叶的结点恰有两个子结点，因而，该二叉树恰有 |C|-1个内部结点。给定编码字符集C及其频率分布f，即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀编码方案 对应于一棵二叉树T。字符c在树中的深度记为d T (c)。d T (c)也是字符c的前缀码长。 该编码方案的平均码长定义为 94 ∑∈=C c T c d c f T B )()()( (4.5.1) 使平均码长达到最小的前缀编码方案称为C 的一个最优编码。 图 4-5-1 哈夫曼提出了一种构造最优前缀编码的贪心算法，称为哈夫曼编码。该算法以自底向上的方式构造表示最优前缀编码的二叉树T。算法以 |C| 个叶结点开始，执行 |C|-1次“合并”运算后产生最终所要求的二叉树T。 图4-5-2 Huffman 95 图4-5-3 Huffman 编码树 Huffman 编码首先用字符集C 中的每一个字符c 的频率f(c)初始化一个优先队列Q，然后不断地从优先队列Q 中取出具有最小频率的两棵树x 和y，将它们合并成一棵新树z，z 的频率是x 与y 的频率之和。新树z 以x 为其左儿子，y 为其右儿子（当然，也可以y 为左儿子，x 为右儿子）。经过至多n-1次合并后（假定 |C| = n ）,优先队列中只剩下一棵树，即是所求的Huffman 树。 设计Huffman 算法可以用最小堆实现优先队列Q。初始化最小堆需要计算时间。由于DeleteMin 和Insert 只需要时间，()O n (log )O n 1n ?次的合并共需要 计算时间。因此，关于n 个字符的Huffman 编码的计算时间为。 (log )O n n (log )O n n 定理4.5.1 Huffman 编码产生最优前缀编码方案。 证明： 设T 是一棵表示最优前缀编码的二叉树，编码的字符集为C。我们先证明：对于频率最小的两个字符x,y，可以将它们调换到最深叶顶点的位置而使新树T ′的平均码长不增加。事实上，假设b,c 是两个最深的叶顶点，它们是兄弟，具有同样的深度。不妨设f(b)≤f(c),f(x)≤f(y)。在树T 中将节点b 与节点x 互换，得到一个新树T ′。此时 B(T)- B(T ′) = f(b)d T (b)+ f(x)d T (x)- f(b)d T (x)- f(x)d T (b) = (f(b)-f(x))( d T (b)- d T (x))≥ 0 如果在树T ′中将节点y 与节点c 互换，得到一棵新树T ′′，同理可证B(T ′)≥ B(T ′′)， 但T 是最有编码树，所以B(T ′′)＝B(T)，说明T ′′也是最优编码树。其次，如果令T ′′中节点x,y 的父节点代表一个新的字符z，出现频率为 f(z)=f(x)+f(y)， 96 则T ′′去掉节点x,y 后得到一个以{C\{x,y})∪{z}为字符集的最优前缀编码树。对于这棵树叶可以象对待树T 那样进行调整，使得新树将具有最小频率的两个字符放在最深的叶子节点位置。如此继续下去，最后得到一棵只有一个节点的树，它是只有一个字符，出现率为100%的最优编码树。以这棵树为根逐步将上述过程中摘掉的叶节点恢复出来，得到的就是Huffman 树。所以Huffman 树是最优树，即平均码长最短的树。 证毕 习题 四 1． 设有n 个顾客同时等待一项服务。顾客i 需要的服务时间为。应该如何安排个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由（证明）。 n i t i ≤≤1,n 2． 字符出现的频率分布恰好是前8个Fibonacci 数，它们的Huffman 编码是什么？将结果推广到n 个字符的频率分布恰好是前n 个Fibonacci 数的情形。Fibonacci 数的定义为：h a ~1,1,11210>+===??n if F F F F n n n F 3． 设是准备存放到长为L 的磁带上的n 个程序，程序需要的带长为。设，要求选取一个能放在带上的程序的最大子集合（即其 中含有最多个数的程序）Q 。构造的一种贪心策略是按的非降次序将程序计入集合。 n p p p ,,,21"i p i a L a n i i >∑=1Q i a 1) 证明这一策略总能找到最大子集Q ，使得∑∈≤Q p i i L a 。 2) 设Q 是使用上述贪心算法得到的子集合，磁带的利用率可以小到何种程度？ 3) 试说明1)中提到的设计策略不一定得到使∑∈Q p i i L a /取最大值的子集合。 4． 写出Huffman 编码的伪代码，并编程实现。 5． 已知n 种货币和有关兑换率的12,,,n c c c "n n ×表R ，其中[,]R i j 是一个单位的货币可以买到的货币i c j c 的单位数。 1）试设计一个算法，用以确定是否存在一货币序列使得： 12,,,k i i i c c c " 2） 设计一个算法打印出满足1）中条件的所有序列，并分析算法的计算 时间。 12231[,][,][,]1k R i i R i i R i i >" 97 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 贪心算法经典例题 发布日期：2009-1-8 浏览次数：1180 本资料需要注册并登录后才能下载！ ·用户名密码验证码找回密码·您还未注册？请注册 您的账户余额为元，余额已不足，请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④ 6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 实验三、0-1背包问题（贪心算法） 实验代码： #include printf("物品总数为：7\n"); printf("物品重量和价值分别为：\n"); printf("\n重量价值\n"); for (i=1;i<=n;i++) printf("%d %d \n",w[i],v[i]); int m=15; int array[8][100]={0}; Knapsack(v,w,x,m,7,array); printf("背包能装的最大价值为: %d\n",array[1][m]); printf("贪心算法的解为: "); for(i=1;i<=n;i++) { if(i==1) printf("%d",x[i]); else printf(" %d",x[i]); } printf("\n"); return 0; } 测试截图为： 贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 201312-27 贪心算法的应用 摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词：贪心法背包问题最优化 目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13) 贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。 应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。贪心选择性质与“动态规划”的主要差别。 2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。 代码如下： #include for(i=1;i<=n;i++) goods[i].X=0; cu=M; //背包剩余容量 for(i=1;i 4.5 哈夫曼编码 哈夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，哈夫曼根据字符在文件中出现的不同频率来建立一个用0，1串表示各字符的最优编码树（称为哈夫曼树），它的设计也是贪心选择的一个典型例子。 例假设有一个包含10000个只含a，b，c，d，e，f字符的数据文件，各字符在文件中出现的频率见下4.5.1表 表 4.5.1 若采用等长编码，则需3位二进制数位来表示6个字符，这种方法要用30000位来表示整个文件。若采用变长编码，则整个文件只需 (45×1+13×3+12×3+16×3+9×4+5×4) ×100=22400 位 也就是说压缩了 (30000-22400)÷30000×100%≥25% 。实际上，这就是这个文件的最优编码方案了 4.5.1 前缀码 我们对每一字符规定一个0，1串作为其代码，并要求任一字符代码都不是其他字符代码的前缀，这样的编码简称为前缀码。在4.5.1表中的两种编码都是前缀码。由于任一字符代码都不是其他字符代码的前缀，所以译码方法非常简单。为了在译码过程中方便地取出编码的前缀，我们可以用二叉树作为前缀码的数据结构。在表示前缀码的二叉树中，树叶代表给定的字符，并将每个字符的前缀码看作是从树根到代表该字符的树叶的一条道路。代码中每一位的0或1分别作为指示某结点到左儿子或右儿子的路标。如图4-1中的两棵二叉树是表4.5.1中两种编码方案所对应的数据结构。 图 4-1 前缀码的二叉树表示 容易看出，表示最优编码方案所对应的前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子。而定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，包含有n个字符，则表示其最优前缀码的二叉树中恰好有n个叶子。每个叶子对应于字符集中一个字符，且该二叉树恰好有n - 1个内部结点。 4.6 最小生成树 设G= （V ，E ）是一个无向连通图，即一个网络。给 E 的每一条边（v, w ）赋于一个权。如果G 的一个子图G ˊ是一棵包含G 的所有顶点的树，则称G ˊ为G 的生成树。生成树上各边权的总和称为该生成树的代价。在G 的所有生成树中，代价最小的生成树称为G 的最小生成树。 网络的最小生成树在实际中有着广泛的应用。在不同的背景下，边的权可以代表不同的含义，比如，两点间的距离，两点间的公路造价等等。例如，在设计通信网络时，用图的顶点表示城市，用边（v, w ）的权表示建立城市v 和城市w 的之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节中要介绍的构造最小生成树的Prim 算法和Kruskal 算法都可以看作是应用贪心算法设计策略的典型例子。 4.6.1 Prim 算法 设G= （V ，E ）是一个连通带权图，V={1 ，2 ，···，n} ，二维数组W 的元素W[i][j] 表示边（i ，j ）的权。构造G 的一棵最小生成树的Prim 算法的基本思想是：首先置S={1} ， 【贪心算法】思想 & 基本要素 & 贪心算法与局部最优 & 贪心算法与动态规划的区别 & 运用贪心算法求解问题 首先我们先代入问题来认识一下贪心算法涉及的问题 找钱问题 给顾客找钱，希望找零的钞票尽可能少，零钱种类和数量限定 找钱问题满足最优子结构 最快找零（贪心）：为得到最小的找零次数，每次最大程度低减少零额活动安排问题 设个活动都需要使用某个教室，已知它们的起始时间和结束时间，求合理的安排使得举行的活动数量最多 贪心：使得每次安排后，教室的空闲时间最多 解决过程如下： 贪心算法求得的相容活动集是最大的 第一步：证明最优解中包含结束时间最早的活动 设相容集 A 是一个最优解，其结束最早的活动为 a，则 ( A - { a }) U { 1 } 也是一个最优解 第二步：证明去掉结束时间最早的活动后，得到的子问题仍是最优的：反证法 理解贪心算法 贪心算法总是做出当前最好的选择 贪心选择的依据是当前的状态，而不是问题的目标 贪心选择是不计后果的 贪心算法通常以自顶向下的方法简化子问题 贪心算法求解的问题具备以下性质 贪心选择性质：问题的最优解可以通过贪心选择实现 最优子结构性质：问题的最优解包含子问题的最优解 贪心选择性质的证明 证明问题的最优解可以由贪心选择开始 即第一步可贪心 证明贪心选择后得到的子问题满足最优子结构 即步步可贪心 背包问题 问题描述：给定 n 个物品和一个背包。物品 i 的重量为 Wi ，价值为 Vi ，背包的容量为 c ，问如何选择物品或物品的一部分，使得背包中物品的价值最大？ 当 n = 3 ，c = 50 0-1背包问题：装入物品2、3，最大价值220 背包问题：装入物品1、2和2-3的物品3，最大价值240（贪心算法）贪心算法无法求解0-1背包问题，按贪心算法，0-1背包问题将装入物品1和2 贪心与局部最优 思考：为什么0-1背包可以用动态规划？而不能用贪心算法 贪心易陷入局部最优 基于贪心算法与最小路径的基因组组装优化问题 摘要 随着人类基因组计划的实施和飞速发展，基因组测序拼接作为生物信息学的核有着极其重要的应用价值。新的测序技术大量涌现，产生的reads 长度更短，数量更多，覆盖率更大，能直接读取的碱基对序列长度远小于基因组长度。本文通过如何在保证组装序列的连续性、完整性和准确性的同时设计耗时短、内存小的组装算法，建立数学模型来解决基因组组装问题。 针对问题一，首先，利用相应的软件对原基因组G 进行切割，利用全基因鸟枪法测序对切割后的短基因进行测序，得到较小的基因组j i G ,通过对比多条任意切割后相似的基因组j i G 从而找出个别碱基对存在的识别错误。而对于基因组中存在的重复片段可以通过两个read 之间的DNA 片段的长度满足一定的分布规律即pared end read 来解决。 接下来对比任意两个11 1m n read 和3 2 2 m n read 是否相等，通过MATLAB 软件建立n m 阶的关联矩阵，最后利用图论中的最短路径方法使更多的基因组能拼接在一起，尽可能使拼接出来的基因组在原基因组的覆盖率达到最大。 针对问题二，先把附件给出的数据提取出来导入MATLAB 中，再结合问题一给出的模型对基因组进行重组，从而得到新的基因。 最后，基于对基因组组装的研究，为使重组基因能更接近原基因序列，对问题一提出模型进行合理性的评价。 关键词：基因组组装 全基因鸟枪法测序 贪心算法 最短路径 一、问题的重述 1.1问题背景 快速和准确地获取生物体的遗传信息对于生命科学研究具有重要的意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比较全面地揭示基因组的复杂性和多样性，成为生命科学领域的重要研究内容。 1.2问题提出 确定基因组碱基对序列的过程称为测序（sequencing）。测序技术始于20世纪70年代，伴随着人类基因组计划的实施而突飞猛进。从第一代到现在普遍应用的第二代，以及近年来正在兴起的第三代，测序技术正向着高通量、低成本的方向发展。尽管如此，目前能直接读取的碱基对序列长度远小于基因组序列长度，因此需要利用一定的方法将测序得到的短片段序列组装成更长的序列。通常的做法是，将基因组复制若干份，无规律地分断成短片段后进行测序，然后寻找测得的不同短片段序列之间的重合部分，并利用这些信息进行组装。例如，若有两个短片段序列分别为 ATACCTT GCTAGCGT GCTAGCGT AGGTCTGA 则有可能基因组序列中包含有ATACCTT GCTAGCGT AGGTCTGA这一段。当然，由于技术的限制和实际情况的复杂性，最终组装得到的序列与真实基因组序列之间仍可能存在差异，甚至只能得到若干条无法进一步连接起来的序列。对组装效果的评价主要依据组装序列的连续性、完整性和准确性。连续性要求组装得到的（多条）序列长度尽可能长；完整性要求组装序列的总长度占基因组序列长度的比例尽可能大；准确性要求组装序列与真实序列尽可能符合。 利用现有的测序技术，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长（reads）。基因组复制份数约为50–100。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLC（Overlap/Layout/Consensus）方法、贪婪图方法、de Bruijn 图方法等。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大的改善空间。 具体解决问题如下： 问题一：试建立数学模型，设计算法并编制程序，将读长序列组装成基因组。你的算法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在重复片段等复杂情况。 问题二：现有一个全长约为120,000个碱基对的细菌人工染色体（BAC），采用Hiseq2000测序仪进行测序，测序策略以及数据格式的简要说明见附录一和附录二，测得的读长数据见附录三，测序深度（sequencing depth）约为70×，即基因组每个位置平均被测到约70次。试利用你的算法和程序进行组装，并使之具有良好的组装效果。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] ： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 摘要：作业和测试的自动组卷是在线形成性考核系统的核心内容。本文在深入研究贪心算法的基础上，提出了基于贪心算法的自动组卷算法，分析了题库和作业库的约束条件，实现了快速高效的组卷过程。最后给出具体实例加以论证。该算法已经成功应用于实际的在线形成性考核系统中。 关键词：贪心算法；在线形成性考核；约束条件；组卷 一、引言目前，常用的自动组卷算法有随机选取算法、回溯试探算法、蛮力法和遗传算法等，这些算法对在线考试系统确实具有一定的应用价值，但这些方法生成的作业卷和测试卷在试卷的科学性和合理性上考虑较少。在综合研究以上各种算法的优缺点后，保证达到较好时间效率和空间效率的基础上，采用贪心算法为核心和随机选取算法为辅助的组卷算法，应用于在线形成性考核系统在线作业和在线测试中，能够达到较好的组卷效果，并且达到教学辅助效果。决定组卷效率和作业卷质量的主要因素有两个：一是题库和作业库的结构；二是组卷算法的设计。二、贪心算法简介贪心算法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个全局的最优解。贪心算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法的基本要素。一是贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。二是最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。在题库组卷问题中，其最优子结构性质表现为：若a是对于e的题库组卷问题包含试题1的一个最优解，则相容作业卷集合a′= a-{1}是对于e′= {i∈e：si≥f1}的题库组卷问题的一个最优解。三、基于贪心算法的在线形成性考核系统组卷算法1、在线形成性考核系统结构在线形成性考核是指对学生学习过程的测评，是对学生课程学习的阶段性考核，是加强教学过程管理、检验学习效果的重要措施。在该系统中，管理员模块主要负责数据导入导出和系统维护，按照学生的课程注册信息绑定学生的班级、课程、辅导教师及恢复误删除成绩；教师模块完成课程形成性考核方案设计，作业题设计，查询考核内容，作业管理，作业批阅，查询批阅结果，删除已批阅但学生要求重做的作业成绩，学生信息管理，查询作业完成情况，到课率录入；学生模块主要功能是查看形考方案、主持教师、辅导教师、导学教师，在线作业，在线测试，作业成绩及反馈查询。在线形成性考核系统结构如图1所示。图1 在线形成性考核系统结构2、题库设计首先需要确定的是试题组织的方式。为了保证达标原则、全面性原则和主要性原则，最好将试题库与具体的知识内容进行关联，也即以课程知识点为核心组织试题库。然后就要考虑试题本身固有的特性参数，主要有题型、试题内容、答案、难度系数等。难度系数是试题难易程度的指标，也是试卷生成中的一个重要参数，它可以由教师录入试题时给定，并且在同一门课程中要坚持相同的标准，并且难度标准初始设定时要充分考虑到所要测试学生的程度范围。难度系数一般用等级来表示, 在五级难度系数中, 一级难度为最低, 五级难度为最高。题型分为客观题和主观题。客观题分单项选择题、多项选择选、判断题和填空题，主观题分计算题、简答题和论述题。3、作业库设计组卷方式可以按需求由主持老师进行客观题和主观题自由组卷。客观题在学生完成并提交成功后，系统自动阅卷并给出成绩。主观题在学生完成并提交后，由辅导老师阅 贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质： 1.整体的最优解可以通过局部的最优解来求出； 2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。 在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。 特别注意：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！ 以经典的活动安排为例： 1、若A是E的最优解，那么E-A 也是问题的最优解，在余下的问题里，继续拿最早结束的； 2、拿可以开始的最早结束。(所以要按结束时间排序一次，然后把可以开始的选择上，然后继续向后推) 贪心子结构是独立的（往往用标志判断而已），不同于动态规划（后面每一边的计算要用到前一步的值，另外开辟空间来保存） 贪心算法的基本步骤： 1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终解。 如最经典的活动安排问题，按结束时间从小到大排序，这样找出第一个节目后，剩下的节目已经是最safe的子结构了，再从子结构中最最早结束但又不和上一次观看的节目有冲突的节目 void arrange(int s[],int f[],bool A[],int n) { A[0] = true; int lastSelected = 0; for (int i = 1;i 武汉理工大学 算法设计与分析论文题目：贪心算法应用研究 姓名：吴兵 学院：信息工程 专业班级：电子133 学号： 1409721303131 任课教师：张小梅 目录 摘要 (1) 1.绪论 (2) 2贪心算法的基本知识概述 (3) 2.1 贪心算法定义 (3) 2.2 贪心算法的基本思路及实现过程 (3) 2.3贪心算法的核心 (3) 2.4贪心算法的基本要素 (4) 2.5 贪心算法的理论基础 (6) 2.6 贪心算法存在的问题 (7) 3贪心算法经典应用举例 (8) 3.1删数问题 (8) 3.2 汽车加油问题 (10) 3.3会场安排问题 (12) 4.总结 (16) 5.参考文献 (17) 摘要 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。 关键词：贪心算法最小生成树多处最优服务次序问题删数问题 贪心算法的应用实例 例2．排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0 贪心算法 1.喷水装置（一） 描述 现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0 对于每一组输入，输出最多能够安排的活动数量。 每组的输出占一行 样例输入 2 2 1 10 10 11 3 1 10 10 11 11 20 样例输出 1 2 提示注意：如果上一个活动在T时间结束，下一个活动最早应该在T+1时间开始。 解题思路：这是一个贪心法中选择不相交区间的问题。先对活动结束时间从小到大排序，排序的同时活动的起始时间也要跟着变化。而且，结束时间最小的活动一定会安排，不然这段时间就白白浪费了。后一个活动的起始时间如果比前一个活动的结束时间大，即两个活动没有相交时间，就把这个活动也安排上。就这样一直找到结束时间最大的，输出时间数目即可。排序时可用下面的方法，排序的同时起始时间也跟着变了。 如果输入 0 6 3 4 1 9 2 8 则排序后的结果就是 3 4 0 6 2 8 1 9 Sample Output 3 5 贪心算法的实际应用 姓名： 班级： 学号： 指导老师： 定义： 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪心选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。 实验五应用贪心算法求解背包问题 学院：计算机科学与技术专业：计算机科学与技术 学号：班级：姓名： 、 实验内容： 背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是n ，假设W w i和v i（1 i n）w i 1i，求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 二、算法思想： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 三、实验过程： #in elude { float p; // 物品效益 float w; // 物品重量 float X; // 物品该放的数量 int flag; // 物品编号 };// 物品信息结构体 void Insertionsort(goodinfo goods[],int n)// 插入排序，按pi/wi 价值收益进行排序，一般教材上按冒泡排序 { int j,i; for(j=2;j<=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].p>goods[i].p) { } goods[i+1]=goods[0]; } }// 按物品效益，重量比值做升序排列goods[i+1]=goods[i]; i--; void bag(goodinfo goods[],float M,int n) { float cu; int i,j; Computer Knowledge and Technology 电脑知识与技术软件设计开发本栏目责任编辑：谢媛媛第6卷第35期(2010年12月)基于贪心算法的0-1背包问题 陈曦 （九江学院，江西九江332005） 摘要：贪心算法是解决问题的一种算法，因其解决问题时具有简单性、直观性和高效性而备受青睐。当待解决的问题具有最优子结构和贪心选择性质时，就可以考虑用贪心算法求解。0-1背包问题是计算机问题中一个普遍的问题，文章中详述了用贪心算法如何解决0-1背包问题。并得出用贪心算法求解此问题能得到最优解。 关键词：0-1背包；贪心算法；动态规划中图分类号：TP312文献标识码：A 文章编号：1009-3044(2010)35-10061-02 Based on the Greedy Algorithm of 0-1Knapsack Problems CHEN Xi (Jiujiang University,Jiujiang 332005,China) Abstract:The greedy algorithm is the solution to the problem of an algorithm,because of its solving problems with simplicity,intuitive and the efficiency is favour.When un-solved problems that have the most YouZi structure and moment-the greedy-choice properties,can con -sider to use greedy algorithm.0-1knapsack problems in computer problems is a common problem in the text,was described by the greedy algorithm to solve 0-1knapsack problems.And obtained by greedy algorithm for solving this problem can obtain optimal solutions.Key words:0-1knapsack;greedy algorithm;dynamic programming 1算法设计与分析是一门集应用性、创造性、实践性为一体的综合性极强的课程[1-2] 一个高效的程序不仅需要“编程技巧”，更需要合理的数据组织和清晰高效的算法。当一个问题具有最优子结构时，根据其具体情况可以用动态规划算法或者贪心算法来求解，但是问题同时具有贪心选择性质时，选择贪心算法更优，贪心算法通常会给出一个简单、直观和高效的解法[3]。 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法并不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。 作为一种算法设计技术，贪心法是一种简单的方法。与动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。这种局部最优选择并不能保证总能获得全局最优解，但是通常能得到较好的近似最优解。例如，平时购物找钱时，为使找回的零钱的硬币数量最少，从最大面值的币种开始，按递减的顺考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小的面值的币种。这就是在采用贪心算法。这种方法在这里总是最优，因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1,5,和11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币，但是最优的解答应是3个5单位面值的硬币。 1.1贪心算法解题思路 贪心算法[4]是经常用到的一种解题方法，往往在解决最优问题时都可以用贪心算法求解。其解题思路为： 1）建立数学模型来描述问题。 2）把求解的问题分成若干子问题。 3）对每一对问题求解，得到子问题的局部最优解。 4）把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进do 求出可行解的一个元素； 由所有解元素组合成问题的一个可行解。 虽然贪心算法有时并不能得到最优解，但是经过证明贪心算法能提高问题的解决效率。 收稿日期：2010-10-15 作者简介：陈曦（1982-），女，江西九江人，讲师，硕士，主要研究方向为计算机应用。 E-mail:xsjl@https://www.doczj.com/doc/bd3453468.html, https://www.doczj.com/doc/bd3453468.html, Tel:+86-551-56909635690964ISSN 1009-3044Computer Knowledge and Technology 电脑知识 与技术Vol.6,No.35,December 2010,pp.10061-1006210061算法设计与分析实验报告贪心算法
贪心算法经典例题
贪心算法0-1背包问题(算法实验代码)
贪心算法详解分析
【精选】贪心算法的应用
背包问题的贪心算法
常见的贪心算法问题
贪 心 算 法
基于贪心算法与最短路径的基因组组装最优拼接问题---1411
贪心算法的应用
基于贪心算法的在线形成性考核系统组卷研究
贪心算法
算法分析与设计选修课-贪心算法应用研究
贪心算法的应用实例
贪心算法练习题
贪心算法的实际应用
c应用贪心算法求解背包问题
基于贪心算法的0_1背包问题
相关主题
文本预览