首页计算机计算机基础计算机算法设计与分析 04 第5章 贪心方法.pptx

04 第5章 贪心方法.pptx

页数:60页文件大小:317.7 KB来源: 计算机算法设计与分析ppt课件

本课件讲解贪心方法,先给出可行解、约束条件、目标函数等基本概念与GREEDY抽象化控制,再依次展开背包问题的三种量度标准比较与最优性证明、带有限期的作业排序及其快速实现,以及最优归并模式与二元归并树的构造,并给出各算法的复杂度分析。

第五章贪心方法章节封面,标示本章主题为贪心策略及其典型应用
第五章目录页,列出一般方法、背包问题、带有限期的作业排序与最优归并模式四节
贪心方法基本概念页,给出可行解、最优解、约束条件与目标函数等定义
查看本课件的文字版(共 60 页,供检索与复制)

第1页:第五章 贪心方法章节封面

1第五章贪心方法

第2页:第五章主要内容

2

  • 5.1一般方法
  • 5.2背包问题
  • 5.3带有限期的作业排序
  • 5.4最优归并模式

第3页:贪心方法的基本概念

35.1一般方法

  • 基本概念:可行解、最优解、约束条件、目标函数A(n)A(n-1)…A(2)A(1)B1(m1)…B1(2)B1(1)Bk(mk)…Bk(2)Bk(1)…最优解问题有n个输入,它的解就是这n个输入的某个子集,这个子集必须满足某些事先给定的条件即约束条件,满足约束条件的子集称为该问题的可行解.一般来说可行解不是唯一的,为衡量可行解的优劣,以函数的形式给出一定的标准,这些函数称为目标函数,使目标函数取极值(极大或极小)的可行解就称为最优解.B1是该问题的一个可行解B1满足一定的约束条件B2(m2)…B2(2)B2(1)一类问题有n个输入:Bi是A的一个子集该问题有k个可行解该可行解可使目标函数取极值

第4页:贪心方法的基本思想

  • 4贪心方法是根据具体的问题,选取一种量度标准,按此标准对n个输入进行排序,然后按该顺序一次输入一个量.如果这个输入量和当前的部分最优解加在一起不能产生一个可行解,则不把此输入量加入到这个部分解中,这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。A(n)…A(2)A(1)量度标准1A1(n)…A1(1)Ak(n)…Ak(1)量度标准2量度标准k……A2(n)…A2(1)可行解1可行解2可行解k次优解次优解最优解
  • 用贪心法求解问题的关键是选择能产生最优解的最优量度标准5.1一般方法

第5页:贪心方法的抽象化控制

5贪心方法的抽象化控制Procedure GREEDY(A,n)solution←∅ for i←1 to n dox←SELECT(A) if FEASIBLE(solution,x) thensolution←UNION(solution,x) endif repeat return (solution)End GREEDY按某种最优量度标准从A中选择一个输入赋给x,并从A中除去x判断x是否可以包含在解向量中将x与解向量合并,并修改目标函数

第6页:背包问题描述

65.2背包问题

  • 问题描述已知有n种物品和一个可容纳M重量的背包,每种物品i(1≤i≤n)的重量为wi,假定将物品i的某一部分xi放入背包就会得到pixi的效益(0≤xi≤1,pi>0),采用怎样的装包方法会使装入背包物品的总效益为最大?
  • 问题的形式化描述:极大化∑pixi约束条件∑wixi≤M0≤xi≤1, pi>0 ,wi>0, 1≤i≤n1≤i≤n1≤i≤n

第7页:背包问题实例

7

  • 背包问题实例∑pixi∑wixi(x1, x2, x3)28.220(1, 2/15, 0)①2820(1, 0, 1/5)②3120(0, 2/3, 1)③31.520(0, 1, 1/2)④其中的4个可行解是:有3个物品,即n=3,背包能容纳的最大重量为20,即M=20物品的价值和重量: (p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10)5.2背包问题

第8页:以效益值为量度标准

8

  • 背包问题的量度标准选择用贪心策略求解背包问题时首先要选出量度标准
  • 选效益值(即目标函数)为量度标准该标准使得背包每装入一件物品就获得最大可能的效益值增量将物品按效益值非增次序排序: (p1,p2,p3)=(25,24,15)按该次序将物品一件件放到背包中,(w1,w2,w3)=(18,15,10)先装物品1(效益最大),即x1=1, w1=18;2,3都不能全放入,衡量后2的一部分效益增量最大。x2=2/15;最后得到总效益值为∑pixi= 25+24*2/15=28.2这是一个次优解,原因是背包容量消耗过快5.2背包问题

第9页:以重量为量度标准

9

  • 选重量为量度标准将物品按重量的非降次序排序: (w3,w2,w1)=(10,15,18)(p3,p2,p1)=(15,24,25)按该次序将物品放到背包中,让重量尽可能慢地被消耗先装物品3,即x3=1, w3=10, p3x3=15;再装入物品2,因约束条件为Σwixi≤M=20,所以物品2只能装入重量为10的一部分,即x2=10/15=2/3;最后得到总效益值为Σpixi=15+24×2/3=31这仍是一个次优解,原因是重量在慢慢消耗的过程中,效益值却没有迅速的增加。该标准使得背包每装入一件物品就获得最小可能的重量增量5.2背包问题

第10页:以单位效益为量度标准

  • 10将物品按pi/wi的非增次序排序:(p2/w2,p3/w3,p1/w1)=(24/15, 15/10, 25/18)即每一次装入的物品使它占用的每一单位重量获得当前最大的单位效益先装入物品2,即x2=1, w2=15, p2x2=24;再装入物品3,因约束条件为Σwixi≤M=20,所以物品3只能装入重量为5的一部分,即x3=5/10=1/2;最后得到总效益值为Σpixi=24+15×1/2=31.5
  • 选效益值和重量之比做为量度标准这是一个最优解,因为每一单位重量的增加将获得最大的单位效益值5.2背包问题

第11页:背包问题的贪心算法

11 背包问题的贪心算法 procedure GREEDY-KNAPSACK(P,W,M,X,n)float P(1:n), W(1:n), X(1:n), M, cu;int i, n;X←0;cu←M; for i←1 to n do if (W(i)>cu) then exit;X(i)←1;cu←cu−W(i); repeat if (i≤n) thenX(i)←cu/W(i); endif end GREEDY-KNAPSACK将解向量X初始化为0cu为背包的剩余重量放入物品i的一部分先将物品按pi/wi的非增次序排序(降序)若物品i的重量大于背包的剩余重量,则退出循环若物品i的重量小于等于背包的剩余容量,则物品i可放入背包内5.2背包问题

第12页:定理5.1与最优解证明

12

  • 最优解的证明
  • 定理5.1:如果p1/w1≥p2/w2≥…≥pn/wn,则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。证明的基本思想:把这个贪心解与任一最优解Y相比较,如果这两个解不同,就去找开始不同的第一个xi,然后设法用贪心解的这个xi去代换最优解的那个yi,并证明最优解在分量代换前后的总效益值无任何变化反复进行这种代换,直到新产生的最优解与贪心解完全一样,从而证明了贪心解就是最优解。5.2背包问题

第13页:定理5.1证明要点

13定理5.1证明

  • 分析贪心解的形式
  • 假设最优解
  • 比较贪心解和最优解
  • 重新构造最优解

第14页:贪心解与最优解的比较

14Z= z1……zk-1zkzk+1……znX= x1……xk-1xkxk+1……xnY= y1……yk-1ykyk+1……yn==≠===>

第15页:作业排序问题的假定

155.3带有限期的作业排序假定:单机无资源约束每个作业在等量时间(单位时间)内完成

第16页:带有限期的作业排序问题

165.3带有限期的作业排序

  • 问题描述假定只能在一台机器上处理n个作业,每个作业均可在单位时间内完成;又假定每个作业i都有一个截止期限di>0(di是整数),当且仅当作业i在它的期限截止之前被完成时获得pi>0的效益。该问题的一个可行解是这n个作业的一个子集合J,J中的每个作业都能在各自的截止期限之前完成,可行解的效益值是J中这些作业的效益之和∑pj具有最大效益值的可行解就是最优解。

第17页:作业排序的目标函数

175.3带有限期的作业排序目标函数约束条件作业j的处理时间tj≤dj,dj>0, pj>0,1≤j≤n

第18页:作业排序问题实例

四个作业的效益为 (p1,p2,p3,p4)=(100,10,15,20),截止期限为 (d1,d2,d3,d4)=(2,1,2,1)。下表列出各可行解的处理顺序与总效益。

带有限期作业排序的可行解与效益值
可行解J处理顺序效益值Σpj
(1)1100
(2)210
(3)315
(4)420
(1,3)1,3或3,1115
(1,2)2,1110
(1,4)4,1120
(2,3)2,325
(3,4)4,335

第19页:作业排序的贪心策略

19 设计算法 procedure GREEDY_JOB(D, J, n)J={1}; for i=2 to n do if (J∪{i}的所有作业都能在它们的截止期限前完成) then J=J∪{i} repeatendGREEDY_JOB为得到最优解,贪心策略应制定一个量度标准,使得所选择的下一个作业在这种量度下达到最优。选择目标函数∑pj作为量度标准,则下一个要计入的作业将是使∑pj得到最大增加的作业,只要将各作业按效益pj降序来排列就行了,即:p1≥p2≥…≥pn算法中最关键的一步5.3带有限期的作业排序

第20页:定理5.2与证明要点

20

  • 定理5.2对于作业排序问题算法5.3所描述的贪心方法总是得到一个最优解。证明要点:设J为贪心解, I为最优解(1)I、J的关系?(2)J中的作业a,a∈I,有pa≥pb,其中b∈I且b∈J.(3)重新构造I
  • I、J中相同的作业:在同一时段调度
  • I、J中不同的作业:在I中将与a同一时段调度的作业用a代换,代换后为I’ = (I−{b})∪{a}
  • 如何确定可行解?检查k!种可能作业排列5.3带有限期的作业排序

第21页:定理5.3可行解的判定

21

  • 定理5.3:设J是k个作业的集合,δ=i1,i2,…,ik是J中作业的一种排列,它使得di1≤di2≤…≤dik。J是一个可行解,当且仅当J中的作业可以按照δ的次序排列而又不超出任何一个期限的限定来处理。实例:(p1,p2,p3,p4)=(100,10,15,20), (d1,d2,d3,d4)=(2,1,2,1)按照1,4,3,2的顺序依次考虑作业J={1}δ=1;J是一个可行解J={1, 4}δ=4,1;J是一个可行解J={1,4,3}δ=4,1,3;但是作业3违反的它的期限,所以J不是一个可行解5.3带有限期的作业排序

第22页:作业排序的处理过程

  • 22根据定理5.3,带有限期的作业排序问题处理过程如下:
  • 首先将作业按p1≥p2≥…≥pn排序,将作业1存入解数组J中,然后处理作业2到作业n;
  • 假设已处理了i−1个作业,其中有k个作业已存入J(1),J(2)…J(k)中,且D(J(1))≤D(J(2))≤…≤D(J(k)),现在处理作业i,判断J∪{i}是否可行,就是看是否能找到一个适当的插入位置,使作业i插入后有D(J(r))≥r; 1≤r≤k+1.过程如下:将D(J(k)), D(J(k−1)),…依次与D(i)比较,若D(J(l))>D(i)且D(J(l))≠1,l≤k,则作业J(l)可以向后延迟一个单位时间来处理,作业i可以在J(l)之前处理。直到找到位置q,有D(i)≥D(J(q)),或者D(J(q))=q,这说明作业i不能在J(q)之前处理,此时只要D(i)>q,就可把作业i插入到q+1位置,即可行解.5.3带有限期的作业排序

第23页:带有限期作业排序的贪心算法

23 带有限期的作业排序的贪心算法从D(J(k))到D(J(1))依次与D(i)比较来寻找插入位置r的过程满足条件表示找到插入位置r实现作业r+1到作业k依次往后移动一个位置将作业i插入到r+1位置5.3带有限期的作业排序 procedure JS(D, J, n, k) integer D(0:n), J(0:n), i, k, n, r;D(0)←J(0)←0; k←1; J(1)←1; for i←2 to n dor←k; while (D(J(r))>D(i)andD(J(r))≠r) dor←r–1 repeat if (D(J(r))≤D(i)andD(i)>r ) then for l←k to r+1 by–1 doJ(l+1)←J(l); repeatJ(r+1)←i ; k←k+1; endif repeat end JS

第24页:JS算法实例

24实例: n=5, (p1,p2,p3,p4,p5)=(10, 1,15,20, 5)(d1,d2,d3,d4,d5)=( 1, 4, 3, 2, 4)排序: (p1,,p2,,p3,,p4,,p5,)=(20,15,10, 5, 1)(d1,,d2,,d3,,d4,,d5,)=( 2, 3, 1, 4, 4)5.3带有限期的作业排序

第25页:JS执行过程一

25D(0)=J(0)=0; k=1; J(1)=1;for循环(i=2时)r = k =1; while (D(J(r)))≯D(i)andD(J(r)))≠r)条件不满足,不执行循环 if (D(J(r)))≤D(i) and D(i)>r ) then{ fori=1tor+1=2by–1do不执行循环J(2)=i=2; k=k+1=2;}J(5)J(4)J(3)J(2)J(1)J(0)1’05’4’3’2’1’015101520p441320d2’5.3带有限期的作业排序

第26页:JS执行过程二

26k=2;for循环(i=3时)r = k = 2; while (D(J(r)))>D(i) and D(J(r)))≠r)执行两次循环后r=0 if (D(J(r)))≤D(i) and D(i)>r ) then{ fori=2tor+1=1by–1do执行2次J(3)=J(2); J(2)=J(1);J(1)=i=3; k=k+1=3;}J(5)J(4)J(3)J(2)J(1)J(0)2’1’02’1’3’k=3;for循环(i=4时)r = k =3; while (D(J(r)))≯D(i) and D(J(r)) ≠r)条件不满足,不执行循环 if (D(J(r)))≤D(i) and D(i)>r ) then{ fori=3tor+1=4by–1do不执行循环J(4)=i=4; k=k+1=4;}4’k=4;for循环( i=5时)r = k = 4; while (D(J(r))≯D(i)andD(J(r)))= =r)条件不满足,不执行循环 if (D(J(r)))≤D(i) and D(i)≯r )条件不满足作业5不能插入5.3带有限期的作业排序5’4’3’2’1’015101520p441320d

第27页:JS算法的时间复杂度

  • 27对于JS有两个赖以测量其时间复杂度的参数:作业数n和包含在解J中的作业数s内层的while循环至多循环k次插入作业i要执行时间为O(k−r)外层for循环共执行(n−1)次如果s是k的终值,即s是最后所得解的作业数,则JS算法所需要的总时间为O(sn)由于s≤n,所以JS算法的最坏时间复杂度为O(n2)
  • 带限期的作业排序贪心算法的时间复杂度5.3带有限期的作业排序

第28页:更快的作业排序算法思路

28

  • 一种更快的作业排序算法
  • 改进思想:对作业i分配时间时,尽可能推迟对作业i的处理。(在其截止期前最靠后的空时间片)
  • 算法思想:如果J是作业的可行子集,可使用下述规则来确定J中每个作业的处理时间:若还没给作业i分配处理时间,则分给它时间片[α-1,α],其中α应尽量取大,且该时间片是空的。若正在被考虑的作业i不存在像上面定义的α,则这个作业就不能计入J中。5.3带有限期的作业排序

第29页:快速作业排序实例

快速作业排序实例:下表逐次给出各作业分配到的时间片与可行解的变化。

快速作业排序的分配动作
考虑的作业分配动作已分配的时间片可行解J
1分配[1,2][1,2]{1}
2分配[0,1][0,1] [1,2]{1,2}
3舍弃[0,1] [1,2]{1,2}
4分配[2,3][0,1] [1,2] [2,3]{1,2,4}
5舍弃[0,1] [1,2] [2,3]{1,2,4}

第30页:集合的运算与表示

30•对集合的运算合、并、交、确定某元素是否属于一个集合例:U={1,2,3,…,10}S1={1,5,8,9} S2={2,7,10} S3={3,4,6,8}2.4.3集合的树表示和不相交集合的合并p42

第31页:集合的三种表示方法

31•集合的表示方法位向量表示:SET(1:n)确定某元素是否属于一个集合的运算:很快交并操作:逻辑加,逻辑乘缺点:n很小时才有效集合的元素表:无序:交、并( mn )、确定某元素是否属于一个集合(m+n)有序:交、并(m+n)、判断属于(log(n))树结构表示:2.4.3集合的树表示和不相交集合的合并n为全集中元素的个数

第32页:集合的树表示与合并

322.4.3集合的树表示和不相交集合的合并λ树用链接表表示,每个结点只需要设置PARENT信息段。

λPARENT(i):存放着元素i在树中其父结点的指针。

λ根结点的PARENT信息段的内容为零。

λ并操作的实现--将两棵树合并1985210719852107

第33页:并操作与查找操作

332.4.3集合的树表示和不相交集合的合并Procedure U(i,j) integer i,jPARENT(i)←jendUProcedure F(i) integer i,jj←iWhile PARENT(j)>0 doj←PARENT(j) repeat return(j) end F将以i和j为根的两棵树合并为一棵树合并后树根为j19852107

第34页:退化树的产生

342.4.3集合的树表示和不相交集合的合并

  • 假设有n个元素,开始时各自属于一个单独的集合,即Si={i},
  • U(1,2),F(1),U(2,3),F(1),U(3,4),F(1),…,U(n−1,n)1nn−1

第35页:加权规则

352.4.3集合的树表示和不相交集合的合并

  • 加权规则:如果树i的结点数少于树j的结点数,则j为i的父亲,反之,i为j的父亲。
  • 树根i:PARENT(i)不再为0,而是树i中结点个数的负数形式。

第36页:UNION过程

362.4.3集合的树表示和不相交集合的合并Procedure UNION(i,j) integer i,j,xx←PARENT(i)+ PARENT(j) if PARENT(i)>PARENT(j) then PARENT(i)←jPARENT(j)←x else PARENT(j)←iPARENT(i)←x endif end UNION若树j的结点个数多,以j为根若树i的结点个数多或两棵树结点个数相同,以i为根合并后集合中元素个数

第37页:引理2.3与压缩规则

372.4.3集合的树表示和不相交集合的合并

  • 引理2.3设T是一棵由算法UNION所产生的有n个结点的树。在T中没有结点的级数会大于⌊logn⌋+1.
  • 执行一次查找需要的时间至多是O(logn)
  • 在查找时使用压缩规则:如果j是由i到其根的路径上的一个结点,则置PARENT(j)←root(i)

第38页:带压缩规则的FIND过程

382.4.3集合的树表示和不相交集合的合并 procedure FIND(i) integer i,j,kj←i while PARENT(j)>0 doj←PARENT(j) repeatk←i while k≠j dot←PARENT(k)PARENT(k)←jk←t repeat return(j) end FIND从结点i到树根j的路径上所有结点的PARENT(k)都变为j找到结点i所在树的树根jj:树根结点k:由i到j的路径上经过的结点

第39页:树表示法的操作序列

392.4.3集合的树表示和不相交集合的合并

  • 假设有n个元素,开始时各自属于一个单独的集合,即Si={i},
  • U(1,2),F(1),U(2,3),F(1),U(3,4),F(1),…,U(n−1,n)
  • U(1,2), U(3,4), U(5,6), U(7,8),U(1,3), U(5,7), U(1,5),
  • FIND(8), FIND(8), …… FIND(8),8次

第40页:时间片范围的确定

401.n个作业,每个作业花费一个单位时间,因此只需考虑时间片[i−1,i],1≤i≤b,b=min{n,max{di}}例如:10个作业,作业的截止期中最大值是5,只需考虑时间段[0,5]5个作业,作业的截止期中最大值是10,同样只需考虑时间段[0,5]2.对于任一期限i,设ni是满足ni≤i且[ni−1,ni]为空的最大整数3.引进一个虚构的期限值0和时间片[−1,0]若期限值i≠j,但ni=nj,设i<j,表明时间[i+1,j]是满的,所以期限值为i+1,i+2,…,j的作业都有可能分到[i−1,i]时间片4.对于每个期限值i,用F(i)表示当前最接近的空时间片,F(i)=ni。

开始时,时间片都为空,F(i)=i.5.期限值按可以分配到的时间片被分成不同集合,初始有b+1个集合。

5.3带有限期的作业排序思想:将期限值表示成集合,使得确定α的时间减小

第41页:集合表示与空时间片查找

416.使用集合的树表示法,把每个集合表示成一棵树,根结点就认为是这个集合。

P(i)把期限值i链接到它的集合树。

开始时P(i) =−1,0≤i≤b.7.判断作业i的可用空时间片,即找min{n,di}的根j,若F(j)≠0,说明有时间片可以分配,则F(j)是最接近的时间片。

8.标识F(j)被占用:以j为根的集合树与包含期限F(j)−1的集合树合并。

5.3带有限期的作业排序

第42页:F(i)与P(i)的含义

425.3带有限期的作业排序

  • F(i):期限i能分配到的时间片
  • P(i):期限i所在的集合的根
  • 对于当前考虑的作业i①作业i的期限D(i)所在的集合FIND(D(i))→j②j是否已被分配F(j)是否为0③若F(j)不为0,则给作业i分配时间片F(j)并做标记集合的变化:j所在的集合和前面的集合l合并线性表的变化:对F(j)重新赋值为F(l)的值

第43页:FJS过程

43Procedure FJS(D,n,b,k.J)/*作业已按p1≥p2≥…≥pn被排序,b= min{n,max{D(i)}}. integer b,D(0:n),J(0:n),F(0:b),P(0:b) for i=0 TO b DOF(i)←i . P(i)←−1 . repeatk←0 . for i=1 TO n DOj←FIND(min(n,D(i))) .ifF(j)≠0 then k←k+1. J(k)←i .l←FIND(F(j)−1).UNION(l,j) .F(j)←F(l) . endif repeat end FJS5.3带有限期的作业排序作业i的期限值所在的集合的根可以给作业i分配时间片标识F(j)被占用

第44页:FJS执行过程一

  • 44考虑作业树J无0 1 2 3 4 5 6 7-10-11-12-13-14-15-16-170 1 2 335 6 7-10-11-12-2334-15-16-17{1}0 11335 6 7-10-2112-2334-15-16-17{1,2}F(0)(1) (2) (3) (4) (5) (6) (7)
  • 例:设n=7,(p1, …,p7)=(35,30,25,20,15,10,5)和(d1,…,d7)=(4,2,4,3,4,8,3)。12

第45页:FJS执行过程二

45考虑作业树J0 11135 6 7-10-4112-15-16-171334{1,2,3}001 1 35 6 710-5112-15-16-171334{1,2,3,4}F(0)(1) (2) (3) (4) (5) (6) (7)(p1, …,p7)=(35,30,25,20,15,10,5)(d1,…,d7)= (4,2,4,3,4,8,3)34

第46页:FJS执行过程三

46考虑作业树J10-5112-15-16-17131400 1 1 35 6 7{1,2,3,4}0 0 1 1 3 5 6610-5112-15-26671334{1,2,3,4,6}0 0 1 1 3 5 6 6同上F(0)(1) (2) (3) (4) (5) (6) (7)(p1, …,p7)=(35,30,25,20,15,10,5)(d1,…,d7)= (4,2,4,3,4,8,3)最优解J={1,2,3,4,6},处理次序4,2,3,1,6,效益值120(舍弃)567(舍弃)

第47页:最优归并模式问题描述

  • 475.4最优归并模式将两个分别包含n个和m个记录的已排序文件归并成一个包含(n+m)个记录的排序文件,时间为O(n+m)6419753001345679文件1: n=3文件2: m=5
  • 若待归并的文件数大于2,如何处理呢?

第48页:不同的归并方式

48例:将4个文件X1,X2,X3,X4进行归并,有不同的归并方式:X1X2X3X4Y1Y2Y3X1X2X3X4Y1Y2Y35.4最优归并模式n个文件归并,有多种归并方式,需要的时间也不同。

第49页:归并顺序与记录移动次数

49归并的计算时间,即记录比较和移动的时间。

问题:如何确定一个把n个已排序文件归并在一起的最优方法,即需要时间最少的方法。

n=3,长度分别为30,20,10Y1Y35060记录移动的总次数:50+60=110X1X2X330 20 10Y1Y2X130X2X320 103060记录移动的总次数:30+60=90最优5.4最优归并模式

第50页:最优归并的量度标准

50量度标准:每一步都归并尺寸比较小的两个文件例:有五个文件长度分别是(F1,…,F5)=(20, 30,10, 5, 30)5F410F315Z120F130F230F560Z335Z295Z4这种模式称二路归并模式用二元归并树来表示叶结点称外部结点表示已知的文件内部结点,每个内部结点有两个儿子,表示它是由两个文件归并而得到的5.4最优归并模式

第51页:带权外部路径长度

  • 515F410F315Z120F130F230F560Z335Z295Z4
  • 带权外部路径长度如果di表示从根到代表文件Fi的外部结点的距离,qi表示文件Fi的长度(即记录数),则这棵二元归并树的记录移动总量是:∑diqi( i=1,2,…n)
  • 一个最优二路归并模式与一棵具有最小外部路径的二元树相对应计算实例中的记录移动总量∑diqi=5*3+10*3+20*2+30*2+30*2=2055.4最优归并模式

第52页:生成二元归并树的算法

52

  • 生成二元归并树算法
  • 算法把n个树的表L作为输入,树中的每一个结点有三个信息段( LCHILD,RCHILD,WEIGHT )
  • 起初L中的每一棵树正好是一个结点,即外部结点,结点的LCHILD和RCHILD信息段都为0,而WEIGHT信息段的值就是已知文件的长度。
  • 算法运行时,对于L中的任何一棵具有根结点T的树,WEIGHT(T)表示要归并的文件的长度。WEIGHT(T) =树T中外部结点的长度和5.4最优归并模式

第53页:TREE过程

53 procedure TREE(L, n) for i←1 to n−1 do call GETNODE(T);LCHILD(T)←LEAST(L);RCHILD(T)←LEAST(L);WEIGHT(T)←WEIGHT(LCHILD(T))+WEIGHT(RCHILD(T)) call INSERT(L,T); repeat return (LEAST(L)); end TREE构造一个新结点作为当前树的根结点找出L中一棵WEIGHT最小的树,把它作为新结点的左子树,然后在L中将这棵树删除把根为T的树插入到表L中新结点的WEIGHT信息段的值等于左、右子树的WEIGHT之和最后留在表L中的树就是归并树,将它作为结果返回5.4最优归并模式

第54页:TREE执行过程一

  • 54例:有6个文件,长度分别为: 2 , 3 , 5 , 7 , 9 , 13,算法TREE如何工作?23
  • 初始,表L中有6棵树,每棵树只有一个结点,分别代表6个文件i=1,先产生一个新结点(内结点),从L的6棵树中找出WEIGHT值最小的树,作为新结点的左子树,再从剩余5棵树中找出WEIGHT最小的树,作为新结点的右子树,新结点的WEIGHT的值等于左、右子树WEIGHT值之和,表L中还有5棵树2351379表L:i=1,表L:5137955.4最优归并模式

第55页:TREE执行过程二

55i=2,先产生一个新结点,从L的棵树中找出WEIGHT值为5的树,作为新结点的左子树,再在剩余4棵树找出WEIGHT值为5的树,作为新结点的右子树,新结点的WEIGHT的值等于左、右子树WEIGHT值之和,表L中还有4棵树235i=2,表L:51379i=3,表L:i=3,先产生一个新结点,从L的棵树中找出WEIGHT值为7的树,作为新结点的左子树,再在剩余4棵树找出WEIGHT值为9的树,作为新结点的右子树,新结点的WEIGHT的值等于左、右子树WEIGHT值之和,表L中还有3棵树102355101379165.4最优归并模式

第56页:TREE执行过程三

5623551013i=4,表L:7916i=5,表L:7916232355101323395.4最优归并模式

第57页:二元归并树算法的计算时间

57

  • 二元归并树算法的计算时间
  • 主循环执行n−1次
  • 如果L中WEIGHT的值按升序排列,则LEAST(L)只需要O(1)的时间
  • INSERT(L,T)在O(n)时间内被执行
  • 因此二元归并树算法的计算是总量为:O(n2)
  • 若L表示成一个min-堆的情况,INSERT(L,T)和LEAST(L)可在log(n)时间内完成,算法的时间为O(nlogn)
  • 定理3.4:若L最初包含n≥1个单各结点的树,这些树有WEIGHT值为(q1,q2,…,qn),则算法TREE对于具有这些长度的n个文件生成一棵最优的二元归并树。5.4最优归并模式

第58页:TREE算法最优性的证明

58

  • 证明:数学归纳法1.n=1时,返回一棵没有内部结点的树。2.假定算法对于所有的(q1,q2,…,qm),1≤m<n生成一棵最优二元归并树。3.对于(q1,q2,…,qn),q1和q2是第一次for循环中进行归并的两棵树,它们形成子树T。T’是一棵对于(q1,q2,…,qn)的最优树,P是T’中距离根最远的一个内结点,转换后得到树T’’,是(q1+q2,…,qn)的最优归并树。由归纳假设,算法TREE对于(q1+q2,…,qn)生成一棵最优二元归并树……5.4最优归并模式

第59页:k路归并模式

59

  • k路归并--k元归并树k元归并树中内部结点的度数必须为k,因此必须引进一定量的“虚”外结点,即被赋予“0”值的qi.这些虚构的外结点不会影响k元树的带权外部路径长度。5.4最优归并模式

第60页:本章小结与作业

605.1一般方法——基本概念,关键问题5.2背包问题5.3带有限期的作业排序重点:掌握用贪心方法解决问题的具体过程,对算法正确性的证明,算法分析。

作业:2, 3, 8, 9本章小结

顶部目录