第4章 贪心方法.

Presentation on theme: "第4章 贪心方法."— Presentation transcript:

1 第4章 贪心方法

2 设计一个好的算法就像一门艺术。但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，可以使用这些方法来设计算法。在许多情况下，为了获得较好的性能，必须对这些算法进行细致的调整。但在某些情况下，算法经过调整之后仍然无法达到要求，这时就必须寻求另外的方法来求解该问题。 从本章开始介绍一些与数据结构中不同的算法设计方法：贪心法，动态规划，分枝限界法。其它的方法还有：线性规划，整数规划，遗传算法，模拟退火算法等等。

3 4.1 最优化问题 1. 问题的一般特征 问题有n个输入，问题的解是由这n个输入的某个子集组成，这个子集必须满足某些事先给定的条件。
约束条件：子集必须满足的条件； 可行解：满足约束条件的子集；可行解可能不唯一； 目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出； 最优解：能够使目标函数取极值（极大或极小）的可行解。

4 例1 [渴婴问题] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n种不同的饮料。根据以前关于这n种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用1盎司第i种饮料，对它作出相对评价，将一个数值si作为满意度赋予第i种饮料。 通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴地需要，但是不幸地是：具有最大满意度值地饮料有时并没有足够地量来满足此婴儿解渴地需要。设ai是第i种饮料地总量，而此婴儿需要t盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢？

5 上述问题可形式描述如下： 输入：n,t,si,ai(其中1in,n为整数，t、si、ai为正实数)。 输出：实数xi(1in)，使 最大，且 。 如果 ，则输出适当的错误信息。 限制条件为 优化函数为 任何满足限制条件的一组实数xi都是可行解，而使 最大的可行解是最优解。

6 例2 [装箱问题] 有一艘大船准备用来装载货物。所有待装载货物都装在货箱中，且所有货箱的大小都一样，但货箱的重量都各不相同。设第i种货箱的重量为wi(1in )，而货船的最大载重量为c，我们的目标是在货船上装入最多的货物。 这个问题可以作为最优化问题进行描述：设存在一组标量xi ,其可能取值为0或1。如果xi 为0，则货箱i不被装上船；如xi 为1，则货箱i将被装上船。我们的目的是找到一组xi ，使它满足限制条件： 相应的优化函数是： 满足限制条件的每一组xi 都是可行解，能使 取得最大值的方案是最优解。

7 例3 [找零钱问题] 一个小孩买了价值少于1元的糖，并将1元钱交给了售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为50分、10分、5分、2分、1分的硬币。
可以通过解不定方程来解决这一问题。也可以分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时采用如下准则：每一次选择应使零钱数尽量增大。为保证解的可行性，所选择的硬币不应使零钱总数超过最终所需的数目。 假设需要找给小孩88分，首先选1枚50分的硬币，然后选3枚10分硬币，再选1枚5分硬币，1枚2分硬币，1枚1分的硬币。 问题：这样得到的硬币数目达到最少吗？ 类似问题：工资发放。

8 例5 [最短路径问题] 在有向图中求一个顶点到另一个顶点的最短路径。（如路由问题）
例4 [最小代价通讯网络] 城市之间所有可能的通信连接可被视作一个无向图，图的每条边都被赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点（城市）的连通子图都是一个可行解。设所有权值都为负，则所有可能的可行解都可表示成无向图的一组生成树，而最优解就是其中具有最小代价的生成树。 在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足如下限制条件：所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。 例5 [最短路径问题] 在有向图中求一个顶点到另一个顶点的最短路径。（如路由问题）

9 例6 [机器调度] 现有n件任务和无限多台机器，任务可以在机器上得到处理。每件任务的开始时间为si ，完成时间为fi ， si <fi 。[si ,fi ]为处理任务i的时间范围。两个任务i,j重叠是指两个任务的时间范围区间重叠，而并非是指i,j的起点或终点重合。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分配中，每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。 假设有n=7件任务，标号为a到g。它们的开始于完成时间如下： 任务 a b c d e f g 开始 完成 若将任务a分给机器M1,任务b分给机器M2,…,任务g分给机器M7这种分配是可行的分配，共使用了7台机器。但它不是最优分配。因为若将a、b、d分配给同一台机器，则机器数目降为5台。

10 最优化问题求解分类：根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。
贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些问题方便地求解。

11 ？ 2. 贪心方法的一般策略 问题的一般特征：问题的解是由n个输入的、满足某些事先给定的条件的子集组成。 注： 贪心解 ＝ 最优解
1）一般方法 根据题意，选取一种度量标准。然后按照这种度量标准对n个输入排序，并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的新的部分解。 2）贪心方法 这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法 ？ 注： 贪心解 ＝ 最优解 直接将目标函数作为量度标准也不一定能够得到问题的最优解 3）使用贪心策略求解的关键 选取能够得到问题最优解的量度标准。

12 3. 贪心方法的抽象化控制描述 returnprocedure GREEDY(A,n) //A(1:n)包含n个输入//
solution←Φ //将解向量solution初始化为空// for i←1 to n do x←SELECT(A) //按照度量标准，从A中选择一个输入，其值赋予x, 并将之从A中删除// if FEASIBLE(solution,x) then //判定x是否可以包含在解向量中， 即是否能共同构成可行解// solution←UNION(solution,x) //将x和当前的解向量合并成新的解向量，并修改目标函数// endif repeat end GREEDY

13 4.2 背包问题 1.问题的描述 已知n种物品具有重量(w1,w2,…,wn)和效益值(p1,p2,…,pn) ，及一个可容纳M重量的背包；设当物品i全部或一部分xi放入背包将得到pi xi的效益，这里，0≤ xi ≤1, pi >0。 问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？ 分析：① 装入背包的总重量不能超过M ② 如果所有物品的总重量不超过M，即 ≤M，则把所有的物品都装入背包中将获得最大可能的效益值。 ③ 如果物品的总重量超过了M，则将有物品不能（全部）装 入背包中。由于0≤xi≤1，所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为M的若干物品（整个或一部分） 目标：使装入背包的物品的总效益达到最大。

14 问题的形式描述 目标函数： 约束条件： 可 行 解： 满足上述约束条件的任一集合(x1,x2,…,xn) 都是问题的一个可行解——可行解可能有多个。 (x1,x2,…,xn)称为问题的一个解向量 最 优 解：能够使目标函数取最大值的可行解是问题的最优解。 ——最优解也可能有多个。

15 (x1,x2,x3) 例5.1 背包问题的实例 设，n=3，M=20，
例5.1 背包问题的实例 设，n=3，M=20， (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)。 可能的可行解如下： (x1,x2,x3) ① (1/2,1/3,1/4) //没有放满背包// ② (1, 2/15, 0 ) ③ (0, 2/3, 1) ④ (0, 1, 1/2)

16 2. 贪心策略求解 度量标准的选择：三种不同的选择 pi/2 = 2 ＜ pj＝ 3 1）以目标函数作为度量标准
即，每装入一件物品，就使背包背包获得最大可能的效益增量。 该度量标准下的 处理规则： ● 按效益值的非增次序将物品一件件地放入到背包； ● 如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在剩下的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。 如：若ΔM=2,背包外还剩两件物品i,j，且有(pi＝ 4，wi＝4) 和(pj＝ 3，wj＝2)，则下一步应选择j而非i放入背包： pi/2 = 2 ＜ pj＝ 3

17 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 28.2 (次优解,非问题的最优解)
实例分析（例4.1) ∵ p1＞p2＞ p3 ∴ 首先将物品1放入背包，此时x1＝1，背包获得p1＝25的效益增量，同时背包容量减少w1＝18个单位，剩余空间ΔM=2。 其次考虑物品2和3。就ΔM=2而言有，只能选择物品2或3的一部分装入背包。 物品2： 若 x2＝2/15， 则 p2 x2＝16/5＝3.2 物品3： 若 x3＝2/10， 则 p3 x3＝3 为使背包的效益有最大的增量，应选择物品2的2/15装包，即 x2＝2/15 最后，背包装满， ΔM=0，故物品3将不能装入背包，x3＝0 。 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ (次优解,非问题的最优解)

18 2）以容量作为度量标准 以目标函数作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入“更多”的物品。 改进：让背包容量尽可能慢地消耗，从而可以尽量装入“更多”的物品。 即，新的标准是：以容量作为度量标准 该度量标准下的处理规则： ● 按物品重量的非降次序将物品装入到背包； ● 如果正在考虑的物品放不进去，则只取其一部分装满背包；

19 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31 (次优解,非问题的最优解)
实例分析（例4.1) ∵ w3＜w2 ＜w1 ∴ 首先将物品3放入背包，此时x3＝1，背包容量减少w3＝10个单位，剩余空间ΔM=10。同时，背包获得p3＝15的效益增量。 其次考虑物品1和2。就ΔM=10而言有，也只能选择物品1或2的一部分装入背包。为使背包的按照“统一”的规则，下一步将放入物品2的10/15装包，即 x2＝10/15＝2/3 最后，背包装满ΔM=0，故物品1将不能装入背包，x1＝0 。 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31 (次优解,非问题的最优解) 存在的问题：效益值没有得到“最大”的增加

20 3）最优的度量标准 影响背包效益值的因素： 背包的容量M 放入背包中的物品的重量及其可能带来的效益值
可能的策略是：在背包效益值的增长速率和背包容量消耗速率之间取得平衡，即每次装入的物品应使它所占用的每一单位容量能获得当前最大的单位效益。 在这种策略下的量度是：已装入的物品的累计效益值与所用容量之比。 故，新的量度标准是：每次装入要使累计效益值与所用容量的比值有最多的增加和最小的减小。 此时，将按照物品的单位效益值：pi/wi 比值（密度）的非增次序考虑。

21 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31.5 (最优解)
实例分析（例4.1) ∵ p1/w1＜p3/w3 ＜p2/w2 ∴ 首先将物品2放入背包，此时x2＝1，背包容量减少w2＝15个单位，还剩余空间ΔM=5。同时，背包获得p2＝24的效益增量。 其次考虑物品1和3。此时，应选择物品3,且就ΔM=5而言有，也只能放入物品3的一部分到背包中 。即 x3＝5/10＝1/2 最后，背包装满ΔM=0，故物品1将不能装入背包，x1＝0 。 背包最终可以获得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ (最优解) 9

22 3. 背包问题的贪心求解算法 算法4.2 背包问题的贪心算法 procedure GREEDY－KNAPSACK(P,W,M,X,n) //p(1:n)和w(1:n)分别含有按P(i)/W(i)≥P(i＋1)/W(i＋1)排序的n件物品的效益值和重量。M是背包的容量大小，而x(1:n)是解向量// real P(1:n),W(1:n),X(1:n),M,cu; integer I,n X←0 //将解向量初始化为空// cu←M //cu是背包的剩余容量// for i←1 to n do if W(i) > cu then exit endif X(i) ←1 cu ←cu-W(i) repeat if i≤n then X(i) ←cu/W(i) endif end GREEDY-KNAPSACK

23 4. 最优解的证明 即证明：由第三种策略所得到的贪心解是问题的最优解。
最优解的含义：在满足约束条件的情况下，可使目标函数取极（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。 证明的基本思想：将此贪心解与（假设中的）任一最优解相比较。 ● 如果这两个解相同，则显然贪心解就是最优解。否则， ● 这两个解不同，就去找开始不同的第一个分量位置i，然后设法用贪心解的这个xi去替换最优解的那个xi ，并证明最优解在分量代换前后总的效益值没有任何变化。 可反复进行代换，直到新产生的最优解与贪心解完全一样。这一代换过程中，最优解的效益值没有任何损失，从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大/最小值。 从而得证：该贪心解也即问题的最优解。

24 定理4.1 如果p1/w1≥ p2/w2≥…≥ pn/wn,则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。
证明： 设X=(x1, x2, …, xn)是GRDDDY-KNAPSACK所生成的贪心解。 ① 如果所有的xi都等于1,则显然X就是问题的最优解。否则， ② 设j是使xi≠1的最小下标。由算法可知， xi=1 1≤i＜j, 0≤xj＜1 xi=0 j＜i≤n 若X不是问题的最优解，则必定存在一个可行解 Y=(y1, y2, …, yn),使得： 且应有：

25 设k是使得yk≠ xk的最小下标，则有yk＜ xk:
a) 若k<j，则xk=1。因为yk≠ xk,从而有yk ＜ xk b) 若k=j，由于 ，且对1≤i＜j，有yi=xi=1,而对j＜i≤n,有xi＝0；故此时若yk＞xk，则将有 ，与Y是可行解相矛盾。而yk≠ xk,所以yk ＜ xk c) 若k＞j，则 ，不能成立 在Y中作以下调整：将yk增加到xk，因为yk≤xk,为保持解的可行性，必须从(yk , yk+1,…,yn)中减去同样多的量。设调整后的解为Z=(z1, z2, …, zn)，其中zi＝xi，1≤i≤k，且有： 则对于Z有：

26 由以上分析得： (1)若 ，则Y将不是最优解； (2)若 则或者Z=X，则X就是最优解；
或者Z≠X，则重复以上替代过程，或者证明Y不是最优解，或者把Y转换成X，从而证明X是最优解。 练习PP87 3.[0/1背包问题]

27 4.3 带有限期的作业排序 1. 问题描述 假定在一台机器上处理n个作业，每个作业均可在单位时间内完成；同时每个作业i都有一个截至期限di>0,当且仅当作业i在其截至期限以前被完成时，则获得pi>0的效益。 问题：求这n个作业的一个子集J，其中的所有作业都可在其截至期限内完成。——J是问题的一个可行解。 可行解J中的所有作业的效益之和是pi ，具有最大效益值的可行解是该问题的最优解。 如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益值；否则，将有作业无法完成——决策应该执行哪些作业，以获得最大可能的效益值。

28 目标函数： 约束条件：所有的作业都应在其期限之前完成 ti<=di; 其中，ti是完成时间di是截止期限

29 例4.2 n=4，(p1，p2，p3，p4)＝(100,10,15,20)和(d1，d2，d3，d4)＝(2,1,2,1)。可行解如下表所示：
处理顺序 效益值 ① （1） 1 100 ② （2） 2 10 ③ （3） 3 15 ④ （4） 4 20 ⑤ （1,2） 2,1 110 ⑥ （1,3） 1,3或3,1 115 ⑦ （1,4） 4,1 120 ⑧ （2,3） 2,3 25 ⑨ （3,4） 4,3 35 问题的最优解是⑦。所允许的处理次序是：先处理作业4再处理作业1。

30 1. 带有限期的作业排序算法 1) 度量标准的选择 以目标函数 作为量度。
1) 度量标准的选择 以目标函数 作为量度。 量度标准：下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下让 得到最大增加的作业。 处理规则：按pi的非增次序来考虑这些作业。

31 ② 作业1具有当前的最大效益值，且{1}是可行解，所以作业1计入J；
例：例4.2求解 ① 首先令J=Φ, ② 作业1具有当前的最大效益值，且{1}是可行解，所以作业1计入J； ③ 在剩下的作业中，作业4具有最大效益值，且{1,4}也是可行解，故作业4计入J，即J={1,4}； ④ 考虑{1,3,4}和{1,2,4}均不能构成新的可行解，作业3和2将被舍弃。 故最后的J={1,4}，最终效益值＝120（问题的最优解）

32 procedure GREEDY-JOB(D,J,n)
2)作业排序算法的概略描述 算法4.3 procedure GREEDY-JOB(D,J,n) //作业按p1≥p2≥…≥pn的次序输入，它们的期限值D(i)≥1, 1≤i≤n,n≥1。J是在它们的截止期限完成的作业的集合// J←{1} for i←2 to n do if J∪{i}的所有作业能在它们的截止期限前完成 then J←J∪{i} endif repeat end GREEDY-JOB

33 2. 最优解证明 定理4.2 算法4.3对于作业排序问题总是得到问题的一个最优解 证明：
设J是由算法所得的贪心解作业集合，I是一个最优解的作业集合。 ① 若I=J，则J就是最优解；否则 ② ，即至少存在两个作业a和b，使得a∈J且 ,b∈I且 。 并设a是这样的一个具有最高效益值的作业，且由算法的处理规则可得：对于在I中而不在J中的作业所有b，有： pa≥pb

34 si’ o o o o o o o o o o i o o o o o o t’ t
设SJ和SI分别是J和I的可行的调度表。因为J和I都是可行解，故这样的调度表一定存在； 设i是既属于J又属于I的一个作业，并i设在调度表SJ中的调度时刻是[t，t+1]，而在SI中的调度时刻是[t’，t’+1]。 在SJ和SI中作如下调整： ● 若t＜t’，则将SJ中在[t’，t’+1]时刻调度的那个作业（如果有的话）与i相交换。如果J中在[t’，t’+1]时刻没有作业调度，则直接将i移到[t’，t’+1]调度。——新的调度表也是可行的。反之， ● 若t’＜t，则在SI中作类似的调换，即将SI中在[t，t+1]时刻调度的那个作业（如果有的话）与i相交换。如果I中在[t，t+1]时刻没有作业调度，则直接将i移到[t，t+1]调度。——同样，新的调度表也是可行的。 对J和I中共有的所有作业作上述的调整。设调整后得到的调度表为S’J和S’I，则在S’J和S’I中J和I中共有的所有作业将在相同的时间被调度。 sj o o o o o o o o o o i o o o o o o t’ t si’ o o o o o o o o o o i o o o o o o t’ t si o o o o o o i o o o o o o o o o o sj o o o o o o i o o o o o o o o o o t t’ sj’ o o o o o o o o o o i o o o o o o si o o o o o o o o o o i o o o o o o

35 si’ o o o o o o o b o o o o o o ta sj’ o o o o o o o a o o o o o o
设a在S’J中的调度时刻是[ta, ta+1]， b是S’I中该时刻调度的作业。根据以上的讨论有：pa≥pb。 在S’I中，去掉作业b，而去调度作业a，得到的是作业集合I’=I-{b} ∪{a}的 一个可行地调度表，且I’的效益值不小于I的效益值。而I’中比I少了一个与J不同的作业。 重复上述的转换，可使I在不减效益值的情况下转换成J。从而J至少有和I一样的效益值。所以J也是最优解。 证毕。 si’ o o o o o o o b o o o o o o ta sj’ o o o o o o o a o o o o o o si’ o o o o o o o a o o o o o o

36 3. 如何判断J的可行性 方法二：检查J中作业的一个特定序列就可判断J的可行性：
方法一：检验J中作业所有可能的排列，对于任一种次序排列的作业序列，判断这些作业是否能够在其期限前完成——若J中有k个作业，则将要检查k!个序列 方法二：检查J中作业的一个特定序列就可判断J的可行性： 对于所给出的一个排列σ＝i1i2…ik,由于作业ij完成的最早时间是j，因此只要判断出σ排列中的每个作业dij≥j，就可得知σ是一个允许的调度序列，从而J是一个可行解。 反之，如果σ排列中有一个dij＜j,则σ将是一个行不通的调度序列，因为至少作业ij不能在其期限之前完成。 这一检查过程可以只通过检验J中作业的一种特殊的排列：按照作业期限的非降次序排列的作业序列即可完成。

37 σ’ ooooooraoooorbooooo σ ooooooiaoooooooraooo
定理4.3 设J是k个作业的集合，σ＝i1i2…ik是J中作业的一种排列，它使得di1≤di2≤…≤dik。J是一个可行解，当且仅当J中的作业可以按照σ的次序而又不违反任何一个期限的情况来处理。 证明： ① 如果J中的作业可以按照σ的次序而又不违反任何一个期限的情况来处理，则J是一个可行解 ② 若J是一个可行解，则必存在序列σ’＝r1r2…rk，使得drj≥j, 1≤j≤k。 ★ 若σ＝σ’，则σ即是可行解。否则， ★ σ≠σ’，令a是使得ra≠ia的最小下标，并设rb=ia。则有： b＞a 且 dra≥drb (为什么?) 在σ’中调换ra与rb，所得的新序列σ’’＝ s1s2…sk的处理次序不违反任何一个期限。 重复上述过程，则可将σ’转换成σ且不违反任何一个期限。故σ是一个可行的调度序列 故定理得证。 σ’ ooooooraoooorbooooo σ ooooooiaoooooooraooo

38 5. 带有限期的作业排序算法的实现 对当前正在考虑的作业j，按限期大小采用一种“插入排序”的方式，尝试将其“插入”到一个按限期从小到大顺序构造的作业调度序列中，以此判断是否能够合并到当前部分解J中。如果可以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。 具体如下： 假设n个作业已经按照效益值从大到小的次序，即p1≥p2≥…≥pn的顺序排列好，每个作业可以在单位时间内完成，并具有相应的时间期限；且至少有一个单位时间可以执行作业 首先，将作业1存入部分解J中，此时J是可行的； 然后，依次考虑作业2到n。假设已经处理了i-1个作业，其中有k个作业计入了部分解J中：J(1),J(2),…,J(k)，且有 D(J(1))≤D(J(2))≤…≤D(J(k))

39 ① ② ③ ④ 对当前正在考虑的作业i,将D(i)依次和D(J(k)), D(J(k-1)),…，D(J(1))相比较，直到找到位置q：使得
★ D(i)＜ D(J(l))，q＜l≤k，且 ★ D(J(q))≤ D(i) 此时，若D(J(L))＞L, q＜L≤k,即说明q位置之后的所有作业均可推迟一个单位时间执行，而又不违反各自的执行期限。 若 D(i)>=q，将q位置之后的所有作业后移一位，作业i插入到位置q＋1处，从而得到一个包含k+1个作业的新的可行解。 若找不到这样的q，作业i将被舍弃。 对i之后的其它作业重复上述过程直到n个作业处理完毕。最后J中所包含的作业集合是此时算法的贪心解，也是问题的最优解。 ① ② ③ ④

40 D(0)←J(0)←0 //初始化，设置岗哨// k←1;J(1)←1 //计入作业1//
算法5.4 带有限期和效益的单位时间的作业排序贪心算法 procedure JS(D,J,n,k) //D(1),…,D(n)是期限值。n≥1。作业已按p1≥p2≥…≥pn的顺序排序。J(i)是最优解中的第i个作业，1≤i≤k。终止时， D(J(i))≤D(J(i＋1))， 1≤i＜k// integer D(0:n),J(0:n),i,k,n,r D(0)←J(0)←0 //初始化，设置岗哨// k←1;J(1)←1 //计入作业1// for i←2 to n do //按p的非增次序考虑作业。找i的位置并检查插入的可行性// r←k while D(J(r))＞D(i) and D(J(r)) ≠r do r←r-1 repeat If D(J(r))≤D(i) and D(i)＞r then //把i插入到J中// for i←k to r+1 by -1 do J(i+1) ←J(i) //将插入点的作业后移一位// J(r+1) ←I;k←k+1;K当前解中的作业数 endif end JS

41 计算时间分析 设s是最终计入J中的作业数，则算法JS所需要的总时间是O(sn)。s≤n，故
for i←2 to n do  将循环n-1次－－－－－－－－－－－－－－－－－－① r←k while D(J(r))＞D(i) and D(J(r)) ≠r do  至多循环k次， k是当前计入J中的作业数 －－－② r←r-1 repeat If D(J(r))≤D(i) and D(i)＞r then for i←k to r+1 by -1 do  循环k-r次，r是插入点的位置 －－－－－③ J(i+1) ←J(i) J(r+1) ←I;k←k+1 endif 设s是最终计入J中的作业数，则算法JS所需要的总时间是O(sn)。s≤n，故 最坏情况：TJS = О(n2)，特例情况：pi=di=n-i+1,1≤i≤n 最好情况：TJS = О(n)，特例情况：pi=di=i,1≤i≤n

42 6. 一种“更快”的作业排序问题 使用不相交集合的 UNION和FIND算法（见1.4.3节），可以将JS的计算时间降低到数量级接近О(n)。 前一种方法，纳入序列J的作业存在向后移动问题，改进思想：将计入J的作业i尽量延迟处理，当然是在di之前。

43 例5.3 n=5 p1-p5=20 15 10 5 1 d1-d5=2 2 1 3 3 J 已分配时间片 正考虑作业 动作
时间片：[α-1,α]的单位时间称为时间片α 对作业i分配处理时间时，分配尽量大的空时间片α 。如果找不到一个空时间片，则抛弃i 例5.3 n=5 p1-p5= d1-d5= J 已分配时间片 正考虑作业 动作 Ф 无 分配[1,2] {1} [1,2] 分配[0,1] {1,2} [0,1][1,2] 舍弃 {1,2} [0,1][1,2] 分配[2,3] {1,2,4} [0,1][1,2][2,3] 舍弃

44 问题：如何确定最大的空时间片是多少？ 随着作业的不断加入，最大空时间片是变化的。如何动态改变作业的最大空时间片？

45 基本思想 1.用i表示时间片[i-1,i],只需考虑这样的时间片 [i-1,i] , 1≦i ≦b, b=min{n,max{dj}}
2.将b个期限值分成一些集合:i:期限值,ni时间片 对于任意一个期限值i,ni是使得nj ≦i的最大整数且是空时间片。 ni是i的最大空时间片，nj是j的最大空时间片 当且仅当ni=nj时i和j在同一集合中 即，具有相同最大空时间片的期限值在同一集合中

46 3.用F(i)表示期限值i的当前最大空时间片 F(i)=ni
引入虚拟时间片0[-1,0]避免极端情况产生 b+1个期限值初始时为F(i)=i 0≦i≦b 4. 用树来表示集合 P(i)>0时 表示期限i的父亲结点 P(i)<0时 表示期限i是根，且该集合中有|P(i)|个结点

47 5.当前正考虑作业具有期限值d，则需要寻找期限值d所在集合，即寻找所在树的根j
若 F(j) =nj≠0即有空时间片，则这个作业分配时间片nj 并且 将这个集合与包含F(j)-1的集合合并 （因为该集合中所有期限值的作业最大可分配时间片减少1） 若 F(j)=0 则无空时间片，放弃此作业，处理下一个作业，直到处理完n个作业。

48 初始值：F(i)=i 0 <=i<=b
p(i)=-1;只包含一个期限值的树

49 算法4.5 作业排序的更快算法 proc fjs（D,n,b,J,k） //假定作业按pi非增序排列，b=min{n,max{dj}} for i=1 to b do F(i)=i,P(i)=-1; repeat k=0;//J中的作业序号 for i=1 to n do j=Find(min(n,D(i)));//找期限值所属集合的根j if F(j) ≠0 then k=k+1 ;J(k)=i//作业i计入解 l=Find(F(j)-1);Union(l,j); F(j)=F(l) endif repeat end fjs

50 考虑 F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) J 作业 无 0 1 2 3 4 5 6 7 Ф
例4.4 n=7, p1-p7=35,30,25,20,15,10,5 d1-d7=4,2,4,3,4,8,3.利用fjs算法求最优解 解： 考虑 F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) J 作业 无 Ф {1} {12} {123} {1234} F(1)=0 舍弃 {1234} {12346} F(1)=0 舍弃 最优解{1,2,3,4,6} -1 -2 3 3 4 -2 1 1 2 1 2 1 2 1 3 3 4

51

52 5.4 最优归并模式 1. 问题的描述 1）两个文件的归并问题 两个已知文件的一次归并所需的计算时间＝O(两个文件的元素总数)
5.4 最优归并模式 1. 问题的描述 1）两个文件的归并问题 两个已知文件的一次归并所需的计算时间＝O(两个文件的元素总数) 例：n个记录的文件 (n+m) 个记录的文件 ＋ m个记录的文件 О(n+m) 2）多个文件的归并 已知n个文件，将之归并成一个单一的文件 例：假定文件X1，X2， X3， X4，采用两两归并的方式，可能的归并模式有： ① X1+X2=Y1+X3= Y2+X4= Y3 ② X1+X2 = Y1 →Y3 X3+X4=Y2

53 在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示的文件归并成其本身所代表的文件
二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归并的模式，最终得到一个完整的记录文件。 二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，称之为二元归并树。 如 60 50 30 20 10 X1 Z1 X X3 X2 归并树的构造 外结点：n个原始文件 内结点：一次归并后得到的文件 在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示的文件归并成其本身所代表的文件

54 不同的归并顺序带来的计算时间是不同的。 例4.5 已知X1,X2,X3是分别为30、20、10个记录长度的已分类文件。将这3个文件归并成长度为60的文件。可能的归并过程和相应的记录移动次数如下： X X3 X2 X1 移动50次 移动60次 移动30次 总移动次数：110次 总移动次数：90次 问题：采用怎样的归并顺序才能使归并过程中元素的移动次数最小（或执行的速度最快）

55 2. 贪心求解 1) 度量标准的选择 ★ 任意两个文件的归并所需的元素移动次数与这两个文件的长度之和成正比；
★ 度量标准：每次选择需要移动次数最少的两个集合进行归并； ★ 处理规则：每次选择长度最小的两个文件进行归并。 95 35 5 20 30 60 15 10 F4 F3 Z1 Z2 Z4 Z3 F1 F5 F2 (F1,F2,F3,F4,F5) = (20,30,10,5,30)

56 2) 目标函数 目标：元素移动的次数最少 实例：为得到归并树根结点表示的归并文件，外部结点中每个文件记录需要移动的次数＝该外部结点到根的距离，即根到该外部结点路径的长度。如， F4 ： F4 Z1 Z2 Z4 则F4中所有记录在整个归并过程中移动的总量＝|F4|*3 带权外部路径长度：记di是由根到代表文件Fi的外部结点的距离，qi是Fi的长度，则这棵树的代表的归并过程的元素移动总量是： 最优的二路归并模式：与一棵具有最小外部带权路径长度的二元树相对应。

57 算法4.6 生成二元归并树的算法 procedure TREE(L,n) //L是n个单结点的二元树表//
for i←1 to n-1 do call GETNODE(T) //构造一颗新树T// LCHILD(T) ←LEAST(L) //从表L中选当前根WEIGHT最小的树， 并从中删除// RCHILD(T) ←LEAST(L) WEIGHT(T) ←WEIGHT(LCHILD(T))+WEIGHT(RCHILD(T)) call INSERT(L,T) //将归并的树T加入到表L中// repeat return (LEAST(L)) //此时，L中的树即为归并的结果// end TREE

58 采用算法TREE，各阶段的工作状态如图所示：
例5.6 已知六个初始文件，长度分别为：2,3,5,7,9,13。 采用算法TREE，各阶段的工作状态如图所示： L 迭代 2 3 5 7 9 13 2 3 5 7 9 13 1 2 3 5 7 9 13 10

59 2 3 5 7 9 13 10 16 2 3 5 7 9 13 10 16 23 39 2 3 5 7 9 13 4 10 16 23

60 时间分析 1) 循环体：n-1次 2) L以有序序列表示 LEAST(L): О(1) INSERT(L,T): О(n)
3) L以min-堆表示 LEAST(L): О(logn) INSERT(L,T): О(logn) 总时间： О(nlogn)

61 3. 最优解的证明 证明：归纳法证明 ① 当n=1时，返回一棵没有内部结点的树。定理得证。
定理3.4 若L最初包含n≥1个单结点的树，这些树有WEIGHT值为(q1,q2,…,qn)，则算法TREE对于具有这些长度的n个文件生成一棵最优的二元归并树。 证明：归纳法证明 ① 当n=1时，返回一棵没有内部结点的树。定理得证。 ② 假定算法对所有的(q1,q2,…,qm)，1≤m＜n,生成一棵最优二元归并树。 ③ 对于n,假定q1≤q2≤…≤qn,则q1和q2将是在for循环的第一次迭代中首先选出的具有最小WEIGHT值的两棵树（的WEIGHT值）；如图所示，T是由这样的两棵树构成的子树： q1 q2 q1+q2 T

62 ■ 设T’是一棵对于(q1,q2,…,qn)的最优二元归并树。
■ 设P是T’中距离根最远的一个内部结点。 若P的两棵子树不是q1和q2，则用q1和q2代换P当前的子树而不会增加T’的带权外部路径长度。 故，p应是最优归并树中的子树。 则在T’中用一个权值为q1＋q2的外部结点代换T，得到的是一棵关于(q1＋q2,…,qn)最优归并树T”。 而由归纳假设，在用权值为q1＋q2的外部结点代换了T之后，过程TREE将针对(q1＋q2,…,qn)得到一棵最优归并树。将T带入该树，根据以上讨论，将得到关于(q1,q2,…,qn)的最优归并树。 故，TREE生成一棵关于(q1,q2,…,qn)的最优归并树。

63 5. k路归并模式 每次同时归并k个文件。 k元归并树：可能需要增加“虚”结点，以补充不足的外部结点——度为0的结点。 ★ 如果一棵树的所有内部结点的度都为k，则外部结点数n满足 n mod (k-1) = 1 ★ 对于满足 n mod (k－1) =1的整数n，存在一棵具有n个外部结点的k元树T，且T中所有结点的度为k。 需要增加 最多k-2 个虚结点。 k路最优归并模式得贪心规则：每一步选取k棵具有最小长度的子树归并。

64 4.5 最小生成树 1. 问题的描述 生成树：设G=(V,E)是一个无向连通图。如果G的生成子图T=(V,E‘)是一棵树，则称T是G的一棵生成树(spanning tree)． G的边赋予一个权值，表示成本、长度等。 最小生成树:具有最小成本的生成树 生成树性质：1.无环2.包含所有节点3.各点连通 4.|V|=n，具有n-1条边

65 假定一个带权无向连通图，希望选择一组连线，连接所有的结点，并且具有最小的成本，即找最小生成树。
约束条件：cost(i,j)=wij (i,j) G无环 目标函数：min∑cost(i,j) (i,j)  T

66 度量标准：选择能使迄今为止所计入的边的成本和有最小增加的那条边。 ● Prim算法 ● Kruskal算法
2. 贪心策略 度量标准：选择能使迄今为止所计入的边的成本和有最小增加的那条边。 ● Prim算法 ● Kruskal算法 构成树，最小的边 最小的边，计入后无环

67 1 4 6 2 5 3 10 30 20 45 25 55 40 50 15 35

68 3. Prim算法 策略：使得迄今所选择的边的集合A构成一棵树；对将要计入到A中的下一条边(u,v)，应是E中一条当前不在A中且使得A∪{(u,v)}也是一棵树的最小成本边。

69 边 (1,2) (2,6) (3,6) (6,4) 成本 10 25 15 20 1 4 6 2 5 3 10 30 20 45 25 55 40 50 15 35 1 2 1 6 2 1 6 2 3 1 6 2 3 4 1 4 6 2 5 3 10 20 25 15 35 (3,5) V(TP) = {1,2,3,4,5,6} E(TP) = { (1,2),(2,6),(3,5),(4,6),(3,6) }

70 算法思想 1.将所有边中的最小成本边（K,L）计入数组T中，T是一个二维数组T(1..N-1，2)存储n-1条边的两个端点。初始：T(1,1)=K T(1,2)=L 2.要计入的边(i,j)的特点: i是计入到树的结点，j是不在树中的结点 cost(i,j)满足上面要求的最小成本边 3.near(j)=0表示结点j已在树中 near(j)<>0=i 表示结点j不在树中，结点i是与之相连的最小成本边的结点。 4.near(j)的值随着结点不断计入树不断可能更新 计入树的结点j，near(j)置0， 不在树中的结点j，near(j)=k，新计入树的结点l，比较cost(j,k)和cost(j,l)，其中较小的一边的另一个结点送near(j) 5.边的成本采用成本邻接矩阵存放

71 procedure PRIM(E,COST,n,T,mincost)
//E是G的边集.COST(n,n)是n结点图G的成本邻接矩阵，矩阵元素COST(i,j)是一个正实数，如果不存在边(i,j)，则为＋∞。计算一棵最小生成树并把它作为一个集合存放到数组T(1:n-1,2)中(T(i,1),T(i,2))是最小成本生成树的一条边.最小成本生成树的总成本最后赋给mincost// real COST(n,n), mincost；integer NEAR(n), T(1:n-1,2) (k,l)←具有最小成本的边 mincost←COST(k,l) (T(1,1),T(1,2)) ←(k,l) for i←1 to n do //将NEAR置初值// if COST(i,l) ＜ COST(i,k) then NEAR(i)←l else NEAR(i) ←k endif repeat

72 NEAR(k)←NEAR(l)←0 for i←2 to n-1 do //找T的其余n-2条边// 设j是NEAR(j)≠0 且COST(j,NEAR(j))最小的下标 (T(i,1),T(i,2))←(j,NEAR(j)) mincost←mincost+COST(j,NEAR(j)) NEAR(j)←0 for k←1 to n do //修改NEAR// if NEAR(k)≠0 and COST(k,NEAR(k))＞COST(k,j) then NEAR(k)←j endif repeat if mincost＞∞ then print(‘no spanning tree’) endif end PRIM 找构成最小边的结点j 这个边存入二维数组T 修改near数组的值 计算复杂性：(n2)

73 算法的改进 从指定结点开始建立生成树，算法的3-9改为： mincost=0 for i=1to n do near(i)=1 repeat
for k=1 to n do least=& if near(k)<>0 and cost(k,near(k))<least then least=cost(k,near(k)); j=k endif T(i,1) T(i,2)=(j,near(j)) near(j)=0 其他不变

74 4. Kruskal算法 边 (1,2) (3,6) (4,6) (2,6) 成本 10 15 20 25
（连通）图的边按成本的非降次序排列，下一条计入生成树T中的边是还没有计入的边中具有最小成本且和T中现有的边不会构成环路的边。 1 2 3 4 5 6 边 (1,2) (3,6) (4,6) (2,6) 成本 10 15 20 25 1 4 6 2 5 3 10 30 20 45 25 55 40 50 15 35 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 5 4 6 5 1 2 3 4 6

75 10 1 2 成本 35 边 (3,5) 35 3 5 25 15 4 20 6 V(TK) = {1,2,3,4,5,6} E(TK) = { (1,2),(2,6),(3,5),(4,6),(3,6) }

76 算法5.9 Kruskal算法 procedure KRUSKAL(E,COST,N,T,mincost) i←mincost←0
//G有n个结点，E是G的边集。COST(u,v)是边(u,v)的成本。T是最小成本生成树的边集，mincost是它的成本// real mincost, COST(1:n,1:n); integer PARENT(1:n), T(1:n-1,2),n 以边成本为元素构造一个min堆 PARENT←-1//每个结点都在不同的集合中// i←mincost←0 while i＜n-1 and 堆非空 do 从堆中删去最小成本边(u,v)并重新构造堆 j←FIND(u); k←FIND(v) if(j≠k) then i←i+1 T(i,1) ←u; T(i,2) ←v mincost←mincost + COST(u,v) call UNION(j,k) endif repeat if i≠n-1 then print(‘no spanning tree’) endif return end KRUSKAL

77 注： ● 边集以min-堆的形式保存，一条当前最小成本边可以在О(loge)的时间内找到； ● 当且仅当图G是不连通的，i≠n-1；此时算法具有最坏的执行时间； ● 算法的计算时间是О(eloge)

78 5. Sollin算法 Sollin算法每步选择若干条边。在每步开始时，选择的边及图中的n个顶点形成一个生成树的森林。 在每一步中为森林中得每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。将所选择的边加入要创建的生成树中。 注意一个森林中的两棵树可以选择同一条边，因此必须多次复制同一条边，在这种情况下，必须丢弃其中的一条边。 开始时，所选择的边的集合为空。 若某一步结束时仅剩下一棵树或没有剩余的边可供选择时算法终止。

79 初始入选边数为0时的情形如图(b),森林中的每棵数均是单个顶点。
对于前面的例子，初始状态如图(a)。 1 4 6 2 5 3 10 30 20 45 25 55 40 50 15 35 1 4 6 2 5 3 初始入选边数为0时的情形如图(b),森林中的每棵数均是单个顶点。 图（a） 图（b） 1 4 6 2 5 3 图（c） 顶点1，2，3，…，6所选择的边分别是(1,2),(2,1),(3,6),(4,6),(5,3),(6,3), 其中相同的边有(3,6)与(6,3), (1,2)与(2,1)。这些边加入到森林得到图（C）。 为森林中的树选边 （2,6）,构成树。

80 1 4 6 2 5 3 7 28 16 10 14 25 22 24 18 12 1 4 6 2 5 3 7 Sollin算法另一个示例。 1 4 6 2 5 3 7 10 14 22 12 22 1 4 6 2 5 3 7 16 10 14 25 12

81 5.6 单源最短路径 1. 问题描述 最短路径问题： ● 每对结点之间的路径问题 ● 特定线路下的最短路径问题 ● 单源最短路径问题等
5.6 单源最短路径 1. 问题描述 最短路径问题： ● 每对结点之间的路径问题 ● 特定线路下的最短路径问题 ● 单源最短路径问题等 单源最短路径问题 已知一个n结点有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其它各结点的最短路径。 假定边的权值为正。

82 例5.10 如图所示。设v0是起始点，求v0到其它各结点的最短路径。
45 10 15 20 3 35 30 路径 长度 (1) v0v (2) v0v2v (3) v0v2v3v (4) v0v 注：路径按照长度的非降次序给出

83 2. 贪心策略求解 1) 度量标准 量度的选择：迄今已生成的所有路径长度之和——为使之达到最小，其中任意一条路径都应具有最小长度： 假定已经构造了i条最短路径，则下一条要构造的路径应是下一条最短的路径。 处理规则：按照路径长度的非降次序依次生成从结点v0到其它各结点的最短路径。 例： v0→v2 v0→v2→v3 v0→v2→v3→v1 v0→v4

84 S 2) 贪心算法 则有， ♠ 设S是已经对其生成了最短路径的结点集合（包括v0)。
♠ 对于当前不在S中的结点w，记DIST(w)是从v0开始，只经过S中的结点而在w结束的那条最短路径的长度。 则有， S W

85 ② 所生成的下一条路径的终点u必定是所有不在S内的结点中且具有最小距离DIST(u)的结点。
① 如果下一条最短路径是到结点u，则这条路径是从结点v0出发在u处终止，且只经过那些在S中的结点,即由v0至u的这条最短路径上的所有中间结点都是S中的结点: 设w是这条路径上的任意中间结点，则从v0到u的路径也包含了一条从v0到w的路径，且其长度小于从v0到u的路径长度。 v0,s1,s2,…,w,…,sm-1,u  均在S中 根据生成规则：最短路径是按照路径长度的非降次序生成的，因此从v0到w的最短路径应该已经生成。从而w也应该在S中。 故,不存在不在S中的中间结点。 ② 所生成的下一条路径的终点u必定是所有不在S内的结点中且具有最小距离DIST(u)的结点。

86 ★ 根据DIST(w)的定义，它所表示的v0至w的最短路径上的所有中间结点都在S中；
③如果选出了这样结点u并生成了从v0到u的最短路径之后，结点u将成为S中的一个成员。此时，那些从v0出发，只经过S中的结点并且在S外的结点w处结束的最短路径可能会减少——DIST(w)的值变小： 如果这样的路径的长度发生了改变，则这些路径必定是一条从v0开始，经过u然后到w的更短的路所致。 S W u v0 ★ 根据DIST(w)的定义，它所表示的v0至w的最短路径上的所有中间结点都在S中； ★ 只考虑<u,w>∈E和<u,w>E 的情况 ★ u是从v0至w的最短路径上所经过的结点。 则有：DIST(w) = DIST(u) + c(u,w)

87 更新dist的值 算法5.10 生成最短路径的贪心算法 procedure SHORTEST-PATHS(v,COST,DIST,n)
//G是一个n结点有向图，它由其成本邻接矩阵COST(n,n)表示。DIST(j)被置结点v到结点j的最短路径长度，这里1≤j≤n。DIST(v)被置成零// boolean S(1:n);real COST(1:n,1:n),DIST(1:n) for i←1 to n do //将集合S初始化为空// S(i) ←0;DIST(i) ←COST(v,i) repeat S(v) ←1;DIST(v) ←0 //结点v计入S// for num←2 to n-1 do //确定由结点v出发的n-1条路// 选取结点u,它使得DIST(u)= S(u) ←1 //结点u计入S// for 所有S(w)＝0的结点w do //修改DIST(w)// DIST(w) = min(DIST(w), DIST(u) + COST(u,w)) end SHORTEST-PATHS 选择dist中最小的u， s(u)=1 更新dist的值

88 3) 计算时间 ⑴ 算法3.10的计算时间是：О(n2) ⑴ for i←1 to n do S(i) ←0;DIST(i) ←COST(v,i) repeat ⑵ for num←2 to n-1 do 选取结点u,它使得DIST(u)= S(u) ←1 for 所有S(w)＝0的结点w do DIST(w) = min(DIST(w), DIST(u) + COST(u,w)) ⑵最短路径算法的时间复杂度 由于任何一条边都有可能是最短路径中的边，所以求任何最短路径的算法都必须至少检查图中的每条边一次，所以这样的算法的最小时间是О(e)。 邻接矩阵表示的图： О(n2)

89 例5.11 求下图中从v1出发到其余各结点的最短路径
20 50 25 70 10 55 40 30 图的成本邻接矩阵： ∞ +∞ +∞ +∞ ∞ +∞ ∞ +∞ +∞ ∞ +∞ +∞ +∞ ∞ +∞ +∞ +∞ +∞ ∞ ∞ +∞ +∞ ∞ +∞ ∞ +∞ +∞ ∞ +∞ +∞

90 算法的执行在有n-1个结点加入到S中后终止
算法的执行轨迹描述 迭代 选取的结点 S DIST (1) (2) (3) (4) (5) (6) (7) 初值 1 2 3 4 5 － 6 1,2 1,2,4 1,2,4,3 1,2,4,3,5 1,2,4,3,5,6 ∞ +∞ +∞ ∞ ∞ ∞ ∞ 算法的执行在有n-1个结点加入到S中后终止

91 3. 最短路径生成树 对于无向连通图G，由结点v到其余各结点的最短路径的边构成G的一棵生成树，称为最短路径生成树。
2 1 3 5 6 7 4 8 55 25 40 35 15 10 50 20 45 30 2 1 3 5 6 7 4 8 55 25 15 10 45 30 2 1 3 5 6 7 4 8 25 40 15 10 20 30 原始图 由结点1出发的最短路径生成树 最小成本生成树

92