首页计算机计算机基础计算机算法设计与分析 12 第六章作业.pptx

12 第六章作业.pptx

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

本课件为第六章动态规划的习题课,涵盖最短路径递推式在负长度环下的失效分析、输出每对结点最短路径的算法与复杂度、最优二分检索树的构造与近似构造算法、0/1背包序偶集合与最优决策序列的确定、整数背包与两仓库分配问题的递推式,以及流水线调度最优性与最优性原理的反例。

第六章习题课封面,标示本次习题覆盖动态规划一章的1至17题
要点回顾页,说明动态规划适用于多阶段过程、需满足最优性原理并建立递推关系式
习题P151-1题目页,要求判断递推关系式在所给图上是否成立并说明负长度环的影响
查看本课件的文字版(共 51 页,供检索与复制)

第1页:第六章习题课封面

1计算机算法分析—习题课第六章1,2,3,4,5,6,7,8,12,13,15,17

第2页:动态规划要点回顾

2动态规划1.多阶段过程2.满足最优性原理3.建立递推关系式

第3页:习题P151-1题目

3P151-1

  • ①递推关系式(6.8)对右图成立吗?为什么?
  • ②递推关系式(6.8)为什么对于含有负长度环的图不能成立?12345674536-42931

第4页:P151-1的解答

4

  • Ak(i,j) = min{Ak-1(i,j), Ak-1(i,k)+Ak-1(k,j)} , k≥1①成立,不包含负长度环. P130②可以使结点间的长度任意小。P151-1

第5页:习题P151-2题目

5P151-2

  • 修改过程ALL_PATHS,使其输出每对结点(i,j)间的最短路径,这个新算法的时间和空间复杂度是多少?
  • 回忆算法:P131算法6.3P127算法6.1

第6页:算法6.3回顾

6P131算法6.3

  • 对矩阵进行初始化,每个元素赋值为边的成本(1-5行)
  • 迭代计算最短路径长度(6-12行)
  • Ak(i,j) = min{Ak-1(i,j), Ak-1(i,k)+Ak-1(k,j)} , k≥1

第7页:算法6.1回顾

7P127算法6.1

  • D(i,j)/D(j) :从节点j到汇点t的最优路径中下一个节点,即最优路径中j的后继节点。
  • 算法6.1在计算COST(j)的同时也记录了D(j)3-7行
  • 计算出D( j )之后,即可计算最短路径。9-11行
  • 仿照6.1 ,用Path(i,j)表示从i到j的最短路径时i的后继结点。

第8页:ShortestPath过程

8ProcedureShortestPath(COST,n,A,Max) integeri,j,k realCOST(n,n),A(n,n),Path(n,n),Maxfori←1tondo//初始化最优路径矩阵forj←1tondoA(i,j)←COST(i,j)ifi≠jandA(i,j)≠Max thenPath(i,j)←j elsePath(i,j)←0 endif repeat repeat

第9页:迭代中的路径更新

9fork←1tondo//迭代计算fori←1tondoforj←1tondoifA(i,j)>A(i,k)+A(k,j) thenA(i,j)←A(i,k)+A(k,j)Path(i,j)←Path(i,k) endif repeat repeat repeat

第10页:路径输出部分

10fori←1tondo//输出最优路径forj←1tondoprint(“thepathofitojis”i)k←path(i,j)whilek≠0doprint(k)k←path(k,j)repeatrepeatrepeatendShortestPath

第11页:复杂度分析

11复杂度分析

  • 时间复杂度第一个循环:O(n2)第二个循环:O(n3)第三个循环:O(n3)
  • 空间复杂度Cost(n,n) A(n,n) Path(n,n)O(n2)

第12页:习题P151-3题目

12P151-3

  • 对于标识符集(a1,a2,a3,a4)=(end, goto, print,stop),已知成功检索概率为P(1)=1/20,P(2)=1/5, P(3)=1/10, P(4)=1/20,不成功检索概率为Q(0)=1/5, Q(1)=1/10, Q(2)=1/5,Q(3)=1/20, Q(4)=1/20,用算法OBST对其计算W(i ,j),R(i, j)和C(i, j) (0≤i, j≤4)。

第13页:最优二分检索树的递推关系式

  • 13递推关系式
  • W(i,j) = Q(i) i=jW(i, j-1)+P(j)+Q(j) i<j
  • C(i,j) = 0 i=jW(i, j)+min{C(i, k-1)+C(k, j)} i<jk在R(i,j-1)和R(i+1,j)中,使C(i,k-1)+C(k,j)取最小值。
  • R(i,j) = k

第14页:各概率取值

14P136算法6.5

  • P(i)P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20
  • Q(i)Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20,Q(4)=1/20化简为整数形式
  • P(i)P(1)=1, P(2)=4, P(3)=2, P(4)=1
  • Q(i)Q(0)=4, Q(1)=2, Q(2)=4, Q(3)=1, Q(4)=1

第15页:成本计算过程

  • 15CRW393222702221018+1+1=2015+2+1=187+4+4=154+2+1=742720100222013+1+1=1510+2+1=132+4+4=10212703307+1+1=94+1+2=7430401+1+1=31001ijj-i=0; j-i=1;j-i=2;j-i=3;j-i=4
  • P(1)=1, P(2)=4, P(3)=2, P(4)=1
  • Q(0)=4, Q(1)=2, Q(2)=4, Q(3)=1, Q(4)=1

第16页:习题P151-4题目

16P151-4

  • ①证明算法OBST的计算时间是O(n2)。
  • ②在已知根R(i, j),0≤i < j≤4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。

第17页:OBST的时间复杂性

17

  • ①将C中元素的加法看做基本运算,则算法OBST的时间复杂性为
  • O(n2)

第18页:构造最优树的实现思想

18②实现思想

  • k←R(m, n)
  • 如果k≠0–创建结点root–令data(Root)←k–令m=m,n=k-1,递归构造左子树–令m=k,n=n,递归构造右子树

第19页:BuildTree过程之一

19②ProcedureBuildTree(A,m, n, R, Root) integer R(n,n), kTreeNode Root, LR, RRifm=n then data(Root)←null, else ifm+1=n then data(Root)←A(n), left(Root)←null,right(Root)←null, endif elsek←R(m,n)data(Root)←A(k),BuildTree(A,m, k-1, R, LR),BuildTree(A,k, n, R, RR),left(Root)←LR, right(Root)←RR endif end BuildTree时间复杂性分析:T(n)=c+T(k)+T(n-k-1),此递推式保证算法的时间复杂性为O(n),也可从递归的角度出发,递归的次数正是结点的个数,而每次递归时间复杂性为常数,所以算法的时间复杂度也为O(n)。

第20页:BuildTree过程之二

20②ProcedureBuildTree(m, n, R, Root) integer R(n,n), kTreeNode Root, LR, RR if (m≤n) then k←R(m,n) if k≠0 then data(Root)←k else Root←nullendif endif end BuildTree

第21页:习题P151-5题目

21P151-5

  • 由于我们通常只知道成功检索和不成功检索概率的近似值,因此,在较短的时间内找出几乎是最优的二分检索树,这也可能是一件很有意义的工作。
  • 所谓几乎是最优的二分检索树,就是对于给定的P和Q,该树的成本(由(6.9)式计算)几乎最小。已经证明,由以下方法获得这种检索树的算法可以有O(nlogn)的时间复杂度
  • 选取这样的k为根,它使|W(0, k-1)-W(k, n) |尽可能地小。重复以上步骤去找这根的左、右子树。

第22页:P151-5的两问

22P151-5

  • ①对于习题6.3的数据,用上述方法找出一棵这样的二分检索树。它的成本是什么?
  • ②用SPAKS写一个实现上述方法的算法,你的算法的计算时间为O(nlogn)吗?

第23页:根的选择与权值差

23

  • n-m=4时(j-i=4)–k=1: |W(0,0)-W(1,4)|=11–k=2: |W(0,1)-W(2,4)|=2–k=3: |W(0,2)-W(3,4)|=12–k=4: |W(0,3)-W(4,4)|=17
  • 所以该树的根是T(0,4)=2
  • 依次计算得到T(0,1)=1,T(2,4)=3,T(3,4)=4选取这样的k为根,使|W(0, k-1)-W(k, n)|尽可能小①矩阵W如右所示,相应的k从1到4得式如下

第24页:概率的整数形式与成本

标识符检索概率的整数形式:把习题6.3的概率化为整数后,四个标识符的成功检索概率与不成功检索概率取值如下表。

标识符集合中各标识符的成功与不成功检索概率
标识符成功检索概率 P(i)不成功检索概率 Q(i)
end1Q(0)=4
goto4Q(1)=2
print2Q(2)=4
stop1Q(3)=1、Q(4)=1

按使左右子树权值之差最小的规则选根,所构造的近似最优二分检索树总体成本为39。

第25页:构造近似最优树的实现思想

  • 25实现思想
  • 如果n-m=0,r[m][n]=0
  • 如果n-m=1,r[m][n]=n
  • 如果n-m>1,求使|w(m, k-1)-w(k, n)|值最小的k值,不妨设是r,其中k=m+1,…,n,r[m][n]=r。–令m=m,n=r-1,重复上述过程。–令m=r,n=n,重复上述过程。

第26页:CreateTree过程

26②Procedure CreateTree(m, n, root, w) integer r, k, root(n, n), w(n, n) real ww, min←+∞ if m=n thenroot(m, n)←0 else if m=n-1 thenroot(m,n)←n else for k←m+1 to n doww←|w(m, k-1)-w(k, n)| if ww< min then min←ww, r←k endif repeatroot(m, n)←rCall CreateTree(m, r-1, root, w)Call CreateTree(r, n, root, w) endif endifEnd BuildTree通过求解递归关系式可得,时间复杂性平均情况是O(nlogn),

第27页:习题P151-6题目

27P151-6

  • 设(w1,w2,w3,w4)=(10, 15, 6, 9),(p1,p2,p3,p4)=(2, 5, 8, 1)。
  • 生成每个fi阶跃点的序偶集合Si,0≤i≤4。

第28页:各物品的质量与效益

28(p1,p2,p3,p4)=(2,5,8,1)(w1,w2,w3,w4)=(10,15,6,9)

第29页:习题P151-7题目

29P151-7

  • 假设在过程DKNAP已算出了Si,0≤i<n,写一个确定0/1背包问题的最优决策序列x1,x2,…,xn的算法PARTS。由于已知道F(i)和F(i+1),因此我们可以使用二分检索方法去确定序偶(P, W)是否属于Si。所以你的算法的时间复杂度不应大于O(n max{log| Si|})≤O(n2)。

第30页:PARTS的实现思想

  • 30实现思想
  • 1:令(P,W)为最优解所对应的序偶,i=n-1
  • 2:如果i>0,重复下列操作:–在F(i)和F(i+1)之间使用二分检索法查找(P,W)。–若存在,Xi+1=0;–否则,(P,W) = (P-Pi+1,W-Wi+1),Xi+1=1。–i=i-1

第31页:PARTS过程

31Procedure PARTS(n, F, M, P, W, p, w)integer n, k, i, j, F(0:n), x(n)real P(m), W(m), pp, ww, p(n), w(n)

第32页:最优序偶的定位

32k←F(n)-1ww ← W(k)pp ← P(k)j←k//k为Sn-1的最末位置 while W(j)+w(n)>M and j>=F(n-1) doj←j-1 repeat//找Sn的最末位置jif(pp<P(j)+p(n) and j>=F(n-1)) then x(n) ← 1, pp ← P(j), ww ← W(j) else x(n) ← 0 endif

第33页:逐阶段回溯决策

33 for i← n-2 to 0 by-1 doBINSRCH(W,ww,F(i),F(i+1)-1,j) if (j=0) then x(i+1) ←1, pp←pp-p(i+1), ww←ww-w(i+1) else x(i+1) ←0 endif repeatendPARTS

第34页:习题P151-8题目

34P151-8

  • 给出一个使得DKNAP(算法6.7 P141)出现最坏情况的例子,它使得| Si|=2i, 0≤i<n。还要求对n的任意取值都适用。

第35页:P151-8的构造

35P151-8取(P1,P2,…,Pi,…)=(W1,W2,…,Wi,…)=(20,21,…,2i-1,…)P和W取值相同,使支配原则成立,也就是说不会因为支配原则而删除元素;

只要说明不会出现相同元素被删除一个的情形,即可知是最坏的情况。

可用归纳法证明此结论。

第36页:习题P151-12题目

36P151-12

  • 将式(6.1)的0/1约束用xi≥0且为整数来代替,就是整数背包问题。
  • 用ZKNAP(l,j, X)来表示这个问题极大化约束条件xi≥0的整数,l≤i≤j若对于有n个物品,容量为M的背包,则整数背包问题就可表示为ZKNAP(1,n,M)

第37页:P151-12的递推关系式之一

  • 37P151-12(1)对这个问题,推导出相应于式(6.14)动态规划递推关系式。
  • 设fi(X)是KNAP(1,i,X)最优解的值,则fn(M) = max { fn−1(M) , fn−1(M−wn)+pn}
  • 对于任意的fi(X), i>0 :fi(X) = max { fi−1(X) , fi−1(X−wi)+pi}(6.14)

第38页:P151-12的递推关系式之二

  • 38P151-12(1)对这个问题,推导出相应于式(6.14)的动态规划递推关系式。
  • 设fi(X)是ZKNAP(1,i,X)最优解的值,则对于任意的fi(X), i>0 :

第39页:习题P152-13题目

39P152-13

  • 假定两个仓库W1和W2都存有同一种货物,其库存量分别为r1和r2.现要将其全部发往n个目的地D1,D2,…,Dn.设发往Dj的货物为dj,因此r1+r2= ∑dj.如果由仓库Wi发送量为xij的货物到目的地Dj的花费为Cij(xij),那么仓库问题就是求各个仓库应给每个目的地发多少货才使总的花费最小。即要求这些非负整数xij,1≤i≤2,1≤j≤n,它使得x1j+x2j=dj, 1≤j≤n ,并且使∑i,jcij(xij)取最小值。假设当W1有x的库存且按最优方式全部发往目的地D1,D2,…, Di时所需的花费为gi(x)(W2的库存为∑1≤j≤idj-x)。于是,此库存问题的最优总花费是gn(r1)。

第40页:求gi(x)的递推关系式

40①求gi(x)的递推关系式

第41页:求解递推式的算法

41②写一个算法求解这个递推关系式并要能得到xij的决策值得最优序列,1≤i≤2,1≤j≤n. procedure Allocate(c, x, d, g, i , y, X) integer c(n), x(n), d(n), g(n), i, X, j if i=1 and X≤d(1) then x(1)←X, c(1)←C(1,x(1)), g(1)← c(1), return endif if i=1 and X>d(1) then g(1)←0, return endif

第42页:Allocate过程

42G← ∞//G存储总花费的最小值,y保存最优解; for j←0 to d(i) dox(i)←j, c(i)←C(1,x(i))Allocate(c, x, d, g, i-1, y, X-j)//递归求所有可能解 if g(i-1) =0//不可行 then g(i)←0, return endif if G>g(i-1)+c(i)//更新G和y then G←g(i-1)+c(i), y(i)←x(i) endif repeat end Allocate

第43页:BothAllocate过程

43Procedure BothAllocate(X, d, x, c) integer c(2)(n), x(2)(n), d(n), g(n), i, X, jGG←∞ call Allocate(c(1), x(1), d, g, n , y, X) if g(n)≠0 then G←g(n) for i←1 to n dox(1, i)← y(i)x(2, i)← d(i)–y(i)c(2, i) ←C(2, x(2, i))G←G+c(2, i)Repeat endif end BothAllocate

第44页:习题P152-15题目之一

  • 44P152-15设I是在两台设备上作流水线调度的任一实例。
  • ①证明对于同一个I,每种POFT调度的长度和每种OFT调度的长度相同。因此6.8节的算法也生成一种POFT调度。

第45页:是否存在抢先的判别

45(一)若任意p=1,…,n-1,都有bp≤ap+1,则此种情况不存在抢先问题;

(二)若存在bp>ap+1,设p是第一个使得bp>ap+1的下标,此时允许抢先,分以下情形:⑴设m是第一个满足bp+bp+1+…+bm<ap+1+…+am+1的下标,则无论是抢先与否,bm执行完毕的时间均为,而bm+1则从am+1结束处时间开始执行,此时再一次针对m+1≤p≤n-1考虑(一)(二)两种情况。

⑵若不存在⑴所描述的m,则有对任意p+1≤m≤n-1,均有,即任意p+1≤j≤m+1,aj执行完时,都可以抢先执行bj,无论抢先与否,总执行时间均为

第46页:习题P152-15题目之二

46P152-15

  • ②证明对于I存在着一种作业在两台设备上按相同次序处理的OFT调度。
  • 往证:在两台设备上处理的任务分别采用不同的处理次序,在调度完成时间上不比采用相同的处理次序强。

第47页:两种处理次序的比较

  • 47P152-15设有两种处理方式:I1采用相同的处理次序,I2采用不同的处理次序I1: ai1ai2… aikI2: ai1ai2… aikbi1bi2… bikbj1bj2… bjk
  • 设I1≠I2,令a是第一个使得ja≠ia的下标,即:对p=1,2,…,a-1,都有ip=jp.情况(一)bia-1执行完时,aia尚未执行完,aja未开始执行。在I1上bia必须开始的时间t1肯定小于等于I2上bja必须开始的时间t2,故I2的执行时间大于等于I1的执行时间;情况(二)若bia-1执行完时,aia已经执行完,但aja未执行完,同样t(I2)≥t(I1);情况(三)若bia-1执行完时,aia、aja均已执行完,则I1中的bia与I2中的bja开始执行时间相同,再考虑下一个ja≠ia的下标。

第48页:习题P152-15题目之三

48P152-15③证明对于I存在着由作业的某种排列(见②)所定义的OFT调度,而这种排列中所有ai=0的作业均在这排列的前部。

进而证明此排列前部那些ai=0的作业出现的次序是无关紧要的。

第49页:作业前移的交换论证

49P152-15

  • ③设一个OFT调度其在设备a和b上分别为:ai1,…,aik,和bi1,…,bik。并假设a是第一个aia=0,但aia-1≠0,即对于所有1≤p≤a-1,aip≠0,将aia和bia移至最前部,得到I’。
  • 显然I’的调度长度是小于等于I的调度长度的。如此反复,可以将所有这样的aia=0的作业移至最前端,而不增加该调度的长度,因此结论成立。
  • 进一步,无论这些ai=0的作业如何排列,其对应在b上的执行时间均为

第50页:习题P152-17题目

50P152-17

  • 最优性原理并不总是对可以将其解看成是一系列决策结果的所有问题成立。找两个最优性原理不成立的例子,并说明对这两个问题最优性原理为什么不成立。

第51页:最优性原理不成立的例子

51P152-17

  • 无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
  • 多段图问题,以乘法为路径长度,当含有负权时。
顶部目录