页数:60页文件大小:317.7 KB来源: 计算机算法设计与分析ppt课件
本课件讲解贪心方法,先给出可行解、约束条件、目标函数等基本概念与GREEDY抽象化控制,再依次展开背包问题的三种量度标准比较与最优性证明、带有限期的作业排序及其快速实现,以及最优归并模式与二元归并树的构造,并给出各算法的复杂度分析。
1第五章贪心方法
2
35.1一般方法
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与解向量合并,并修改目标函数
65.2背包问题
7
8
9
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
13定理5.1证明
14Z= z1……zk-1zkzk+1……znX= x1……xk-1xkxk+1……xnY= y1……yk-1ykyk+1……yn==≠===>
155.3带有限期的作业排序假定:单机无资源约束每个作业在等量时间(单位时间)内完成
165.3带有限期的作业排序
175.3带有限期的作业排序目标函数约束条件作业j的处理时间tj≤dj,dj>0, pj>0,1≤j≤n
四个作业的效益为 (p1,p2,p3,p4)=(100,10,15,20),截止期限为 (d1,d2,d3,d4)=(2,1,2,1)。下表列出各可行解的处理顺序与总效益。
| 可行解J | 处理顺序 | 效益值Σpj |
|---|---|---|
| (1) | 1 | 100 |
| (2) | 2 | 10 |
| (3) | 3 | 15 |
| (4) | 4 | 20 |
| (1,3) | 1,3或3,1 | 115 |
| (1,2) | 2,1 | 110 |
| (1,4) | 4,1 | 120 |
| (2,3) | 2,3 | 25 |
| (3,4) | 4,3 | 35 |
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
21
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实例: 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带有限期的作业排序
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带有限期的作业排序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’015101520p441320d28
快速作业排序实例:下表逐次给出各作业分配到的时间片与可行解的变化。
| 考虑的作业 | 分配动作 | 已分配的时间片 | 可行解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•对集合的运算合、并、交、确定某元素是否属于一个集合例:U={1,2,3,…,10}S1={1,5,8,9} S2={2,7,10} S3={3,4,6,8}2.4.3集合的树表示和不相交集合的合并p42
31•集合的表示方法位向量表示:SET(1:n)确定某元素是否属于一个集合的运算:很快交并操作:逻辑加,逻辑乘缺点:n很小时才有效集合的元素表:无序:交、并( mn )、确定某元素是否属于一个集合(m+n)有序:交、并(m+n)、判断属于(log(n))树结构表示:2.4.3集合的树表示和不相交集合的合并n为全集中元素的个数
322.4.3集合的树表示和不相交集合的合并λ树用链接表表示,每个结点只需要设置PARENT信息段。
λPARENT(i):存放着元素i在树中其父结点的指针。
λ根结点的PARENT信息段的内容为零。
λ并操作的实现--将两棵树合并1985210719852107
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
342.4.3集合的树表示和不相交集合的合并
352.4.3集合的树表示和不相交集合的合并
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为根合并后集合中元素个数
372.4.3集合的树表示和不相交集合的合并
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的路径上经过的结点
392.4.3集合的树表示和不相交集合的合并
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带有限期的作业排序思想:将期限值表示成集合,使得确定α的时间减小
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带有限期的作业排序
425.3带有限期的作业排序
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)被占用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考虑作业树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(舍弃)
48例:将4个文件X1,X2,X3,X4进行归并,有不同的归并方式:X1X2X3X4Y1Y2Y3X1X2X3X4Y1Y2Y35.4最优归并模式n个文件归并,有多种归并方式,需要的时间也不同。
49归并的计算时间,即记录比较和移动的时间。
问题:如何确定一个把n个已排序文件归并在一起的最优方法,即需要时间最少的方法。
n=3,长度分别为30,20,10Y1Y35060记录移动的总次数:50+60=110X1X2X330 20 10Y1Y2X130X2X320 103060记录移动的总次数:30+60=90最优5.4最优归并模式
50量度标准:每一步都归并尺寸比较小的两个文件例:有五个文件长度分别是(F1,…,F5)=(20, 30,10, 5, 30)5F410F315Z120F130F230F560Z335Z295Z4这种模式称二路归并模式用二元归并树来表示叶结点称外部结点表示已知的文件内部结点,每个内部结点有两个儿子,表示它是由两个文件归并而得到的5.4最优归并模式
52
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最优归并模式
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最优归并模式
5623551013i=4,表L:7916i=5,表L:7916232355101323395.4最优归并模式
57
58
59
605.1一般方法——基本概念,关键问题5.2背包问题5.3带有限期的作业排序重点:掌握用贪心方法解决问题的具体过程,对算法正确性的证明,算法分析。
作业:2, 3, 8, 9本章小结
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}