算法分析第六章答案优秀PPT.ppt

《算法分析第六章答案优秀PPT.ppt》由会员分享，可在线阅读，更多相关《算法分析第六章答案优秀PPT.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1计算机算法分析计算机算法分析习题课习题课第六章1,2,3,4,5,6,7,8,12,13,15,172 2动态规划动态规划1.多阶段过程2.满足最优性原理3.建立递推关系式3 3P151-1n n递推关系式递推关系式(6.8)对右图成立吗？为什对右图成立吗？为什么？么？n n递推关系式递推关系式(6.8)为什么对于含有负长为什么对于含有负长度环的图不能成立？度环的图不能成立？12345674536-429314 4n nAk(i,j)=minAk-1(i,j),Ak-1(i,k)+Ak-1(k,j),k 1成立，不包含负长度环成立，不包含负长度环.P130可以使结点间的长度任意小。可以使

2、结点间的长度任意小。P151-15 5P151-2 n n修改过程修改过程ALL_PATHS，使其输出每对，使其输出每对结点（结点（i,j）间的最短路径，这个新算法）间的最短路径，这个新算法的时间和空间复杂度是多少？的时间和空间复杂度是多少？n n回忆算法：回忆算法：P131 算法算法6.3P127 算法算法6.1 6 6P131 算法算法6.3n n对矩阵进行初始化，每个元素赋值为边的成本对矩阵进行初始化，每个元素赋值为边的成本(15行行)n n迭代计算最短路径长度迭代计算最短路径长度(612行行)n nAk(i,j)=minAk-1(i,j),Ak-1(i,k)+Ak-1(k,j),k 1

3、7 7P127 算法算法6.1n nD(i,j)/D(j):D(i,j)/D(j):从节点从节点从节点从节点j j到汇点到汇点到汇点到汇点t t的最优路径中下一个的最优路径中下一个的最优路径中下一个的最优路径中下一个节点，即最优路径中节点，即最优路径中节点，即最优路径中节点，即最优路径中j j的后继节点。的后继节点。的后继节点。的后继节点。n n算法算法算法算法6.16.1在计算在计算在计算在计算COST(j)COST(j)的同时也记录了的同时也记录了的同时也记录了的同时也记录了D(j)D(j)3 37 7行行行行n n计算出计算出计算出计算出D(j)D(j)之后，即可计算最短路径。之后，即可

4、计算最短路径。之后，即可计算最短路径。之后，即可计算最短路径。9 91111行行行行n n仿照仿照仿照仿照6.1,6.1,用用用用Path(i,j)Path(i,j)表示从表示从表示从表示从i i到到到到j j的最短路径时的最短路径时的最短路径时的最短路径时i i的的的的后继结点。后继结点。后继结点。后继结点。8 8Procedure ShortestPath(COST,n,A,Max)Procedure ShortestPath(COST,n,A,Max)integer i,j,k integer i,j,k real COST(n,n),A(n,n),Path(n,n),Maxreal C

5、OST(n,n),A(n,n),Path(n,n),Maxfor i1 to n do/for i1 to n do/初始化最初始化最初始化最初始化最优优优优路径矩路径矩路径矩路径矩阵阵阵阵for j1 to n do for j1 to n do A(i,j)COST(i,j)A(i,j)COST(i,j)if ij and A(i,j)Max thenif ij and A(i,j)Max thenPath(i,j)jPath(i,j)jelseelsePath(i,j)0Path(i,j)0endifendif repeatrepeatrepeatrepeat9 9for k1 to n

6、 do/迭代迭代计计算算for i1 to n do for j1 to n do if A(i,j)A(i,k)+A(k,j)thenA(i,j)A(i,k)+A(k,j)Path(i,j)Path(i,k)endifrepeatrepeatrepeat1010for i1 to n do/for i1 to n do/输输输输出最出最出最出最优优优优路径路径路径路径for j1 to n dofor j1 to n doprint(print(“the path of i to j is the path of i to j is”i)i)kpath(i,j)kpath(i,j)while

7、 k0 dowhile k0 doprint(k)print(k)kpath(k,j)kpath(k,j)repeatrepeatrepeatrepeatrepeatrepeatend ShortestPath1111复杂度分析复杂度分析n n时间复杂度时间复杂度第一个循环：第一个循环：O(n2)第二个循环：第二个循环：O(n3)第三个循环：第三个循环：O(n3)n n空间复杂度空间复杂度Cost(n,n)A(n,n)Path(n,n)O(n2)1212P151-3n n对对于于标识标识符集符集(a1,a2,a3,a4)=(end,goto,print,stop)，已知成功，已知成功检检索概率

8、索概率为为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)(0i,j4)。1313递推关系式：递推关系式：n nW(i,j)=Q(i)i=jW(i,j-1)+P(j)+Q(j)ij n nC(i,j)=0 i=j W(i,j)+minC(i,k-1)+C(k,j)ij k在在R(i,j-1)和和R(i+1,j)中，使中，使C(i,k-1)+C(k,j)取最小

9、值。取最小值。n nR(i,j)=k1414P136 算法算法6.5n nP(i)P(1)=1/20,P(2)=1/5,P(3)=1/10,P(4)=1/20n nQ(i)Q(0)=1/5,Q(1)=1/10,Q(2)=1/5,Q(3)=1/20,Q(4)=1/20化化简为简为整数形式整数形式n nP(i)P(1)=1,P(2)=4,P(3)=2,P(4)=1n nQ(i)Q(0)=4,Q(1)=2,Q(2)=4,Q(3)=1,Q(4)=11515WRC44+2+1=77+4+4=1515+2+1=1818+1+1=20012220722 32 3922+4+4=1010+2+1=1313+1

10、+1=150222010 20 2744+1+2=77+1+1=9033071211+1+1=30403100ijj-i=0;j-i=1;j-i=2;j-i=3;j-i=4n nP(1)=1,P(2)=4,P(3)=2,P(4)=1P(1)=1,P(2)=4,P(3)=2,P(4)=1n nQ(0)=4,Q(1)=2,Q(2)=4,Q(3)=1,Q(4)=1Q(0)=4,Q(1)=2,Q(2)=4,Q(3)=1,Q(4)=11616P151-4n n证明算法证明算法OBST的计算时间是的计算时间是O(n2)。n n在已知根在已知根R(i,j)，0 i 1，求使，求使|w(m,k-1)-w(k,

11、n)|值值最小的最小的k值，不妨设是值，不妨设是r，其中，其中k=m+1,n，rmn=r。令令令令m=mm=m，n=r-1n=r-1，重复上述过程。，重复上述过程。，重复上述过程。，重复上述过程。令令令令m=rm=r，n=nn=n，重复上述过程。，重复上述过程。，重复上述过程。，重复上述过程。2626Procedure CreateTree(m,n,root,w)Procedure CreateTree(m,n,root,w)integer r,k,root(n,n),w(n,n)integer r,k,root(n,n),w(n,n)real ww,min+real ww,min+if m=

12、n then if m=n then root(m,n)0root(m,n)0else if m=n-1 then else if m=n-1 then root(m,n)nroot(m,n)n else else for km+1 to n do for km+1 to n do ww|w(m,k-1)-w(k,n)|ww|w(m,k-1)-w(k,n)|if ww min then minww,rk endif if ww0，重复下列操作：，重复下列操作：在在在在F(i)F(i)和和和和F(i+1)F(i+1)之间使用二分检索法查找之间使用二分检索法查找之间使用二分检索法查找之间使用二分检

13、索法查找(P,W)(P,W)。若存在，若存在，若存在，若存在，X Xi+1i+1=0;=0;否则，否则，否则，否则，(P,W)=(P-P(P,W)=(P-Pi+1i+1,W-W,W-Wi+1i+1)，X Xi+1i+1=1=1。i ii-1i-13131Procedure PARTS(n,F,M,P,W,p,w)Procedure PARTS(n,F,M,P,W,p,w)/*p(n)/*p(n)和和和和w(n)w(n)是存放原数据的，是存放原数据的，是存放原数据的，是存放原数据的，P(m)P(m)和和和和W(m)W(m)是存放是存放是存放是存放S S的，的，的，的，F(n)F(n)是存放指针的

14、，是存放指针的，是存放指针的，是存放指针的，x(n)x(n)是存放元素取舍结果的是存放元素取舍结果的是存放元素取舍结果的是存放元素取舍结果的*/integer n,k,i,j,F(0:n),x(n)integer n,k,i,j,F(0:n),x(n)real P(m),W(m),pp,ww,p(n),w(n)real P(m),W(m),pp,ww,p(n),w(n)3232/*/*确定：确定：确定：确定：x(n)x(n)、最优解所对应的序偶、最优解所对应的序偶、最优解所对应的序偶、最优解所对应的序偶(pp,ww)(pp,ww)，其所在位置其所在位置其所在位置其所在位置j j，j j在在在在

15、F(n-1)F(n-1)和和和和F(n)F(n)之间之间之间之间*/kF(n)-1 kF(n)-1 ww W(k)ww W(k)pp P(k)pp P(k)jk jk /k/k为为为为S Sn-1n-1的最末位置的最末位置的最末位置的最末位置 while W(j)+w(n)M and j=F(n-1)do while W(j)+w(n)M and j=F(n-1)do jj-1jj-1 repeat repeat /找找找找S Sn n的最末位置的最末位置的最末位置的最末位置j jif(pp=F(n-1)if(pp=F(n-1)then x(n)1,pp P(j),ww W(j)then x(

16、n)1,pp P(j),ww W(j)else x(n)0 else x(n)0 endif endif 3333 /*/*使用二分检索法在使用二分检索法在使用二分检索法在使用二分检索法在WW上上上上F(i)F(i)和和和和F(i+1)F(i+1)范围范围范围范围 之间查找之间查找之间查找之间查找wwww，确定确定确定确定x(i+1)*/x(i+1)*/for i n-2 to 0 by-1 do n-2 to 0 by-1 do BINSRCH(W,ww,F(i),F(i+1)-1,j)BINSRCH(W,ww,F(i),F(i+1)-1,j)if(j=0)if(j=0)then x(i+1

17、)1,pppp-p(i+1),wwww-w(i+1)then x(i+1)1,pppp-p(i+1),wwww-w(i+1)else x(i+1)0 else x(i+1)0 endif endif repeat repeatendPARTSendPARTS3434P151-8n给出一个使得给出一个使得DKNAP(算法算法6.7 P141)出现出现最坏情况的例子，它使得最坏情况的例子，它使得|Si|=2i,0i0:fi(X)=max fi 1(X),fi 1(X wi)+pi （6.14）3838P151-12(1)(1)对这个问题，推导出相应于式对这个问题，推导出相应于式对这个问题，推导出相

18、应于式对这个问题，推导出相应于式(6.14)(6.14)的动态规的动态规的动态规的动态规划递推关系式。划递推关系式。划递推关系式。划递推关系式。n设设fi(X)是是ZKNAP(1,i,X)最优解的值最优解的值,则则对于任意的对于任意的fi(X),i0:3939P152-13n假定两个仓库假定两个仓库W1和和W2都存有同一种货物，其库存量分别都存有同一种货物，其库存量分别为为r1和和r2.现要将其全部发往现要将其全部发往n个目的地个目的地D1，D2，Dn.设设发往发往Dj的货物为的货物为dj，因此，因此r1+r2=dj.如果由仓库如果由仓库Wi发送量发送量为为xij的货物到目的地的货物到目的地D

19、j的花费为的花费为Cij(xij)，那么仓库问题就，那么仓库问题就是求各个仓库应给每个目的地发多少货才使总的花费最小。是求各个仓库应给每个目的地发多少货才使总的花费最小。即要求这些非负整数即要求这些非负整数xij，1i2，1jn，它使得，它使得x1j+x2j=dj,1jn,并且使并且使i,jcij(xij)取最小值。假设当取最小值。假设当W1有有x的库存的库存且按最优方式全部发往目的地且按最优方式全部发往目的地D1，D2，,Di 时所需的花时所需的花费为费为gi(x)(W2的库存为的库存为1jidj-x)。于是，此库存问题的最。于是，此库存问题的最优总花费是优总花费是gn(r1)。4040求求

20、gi(x)的递推关系式的递推关系式4141 写一个算法求解这个递推关系式并要能得到写一个算法求解这个递推关系式并要能得到xij的决策值得最优序列，的决策值得最优序列，1i2,1jn.n nprocedure Allocate(c,x,d,g,i,y,X)procedure Allocate(c,x,d,g,i,y,X)/*c /*c是代价数组，是代价数组，是代价数组，是代价数组，x x是货物量，是货物量，是货物量，是货物量，d d是限量，是限量，是限量，是限量，g g是花费是花费是花费是花费(若若若若g g为零，则无解为零，则无解为零，则无解为零，则无解)，i i是处理到第几个目的地，是处理到

21、第几个目的地，是处理到第几个目的地，是处理到第几个目的地，X X是库存量，是库存量，是库存量，是库存量，C C是函数是函数是函数是函数*/integer c(n),x(n),d(n),g(n),i,X,j integer c(n),x(n),d(n),g(n),i,X,j if i=1 and Xd(1)if i=1 and Xd(1)then x(1)X,c(1)C(1,x(1),g(1)c(1),then x(1)X,c(1)C(1,x(1),g(1)c(1),return return endif endif if i=1 and Xd(1)if i=1 and Xd(1)then g(

22、1)0,return then g(1)0,return endif endif4242 G G /G/G存储总花费的最小值，存储总花费的最小值，存储总花费的最小值，存储总花费的最小值，y y保存最优解；保存最优解；保存最优解；保存最优解；for j0 to d(i)do for j0 to d(i)do x(i)j,c(i)C(1,x(i)x(i)j,c(i)C(1,x(i)Allocate(c,x,d,g,i-1,y,X-j)Allocate(c,x,d,g,i-1,y,X-j)/递归求所有可能解递归求所有可能解递归求所有可能解递归求所有可能解 if g(i-1)=0 if g(i-1)=

23、0 /不可行不可行不可行不可行 then g(i)0,returnthen g(i)0,return endif endif if Gg(i-1)+c(i)if Gg(i-1)+c(i)/更新更新更新更新GG和和和和y y then Gg(i-1)+c(i),y(i)x(i)then Gg(i-1)+c(i),y(i)x(i)endif endif repeat repeatend Allocateend Allocate4343Procedure BothAllocate(X,d,x,c)Procedure BothAllocate(X,d,x,c)integer c(2)(n),x(2)(

24、n),d(n),g(n),i,X,j integer c(2)(n),x(2)(n),d(n),g(n),i,X,j GG GG call Allocate(c(1),x(1),d,g,n,y,X)call Allocate(c(1),x(1),d,g,n,y,X)if g(n)0 if g(n)0 then Gg(n)then Gg(n)for i1 to n do for i1 to n do x(1,i)y(i)x(1,i)y(i)x(2,i)d(i)y(i)x(2,i)d(i)y(i)c(2,i)C(2,x(2,i)c(2,i)C(2,x(2,i)GG+c(2,i)GG+c(2,i)R

25、epeat Repeat endif endifend BothAllocateend BothAllocate4444P152-15 设设I是在两台设备上作流水线调度的任是在两台设备上作流水线调度的任一实例。一实例。n n证明对于同一个证明对于同一个I，每种，每种POFT调度的调度的长度和每种长度和每种OFT调度的长度相同。因此调度的长度相同。因此6.8节的算法也生成一种节的算法也生成一种POFT调度。调度。4545（一）若任意（一）若任意（一）若任意（一）若任意p=1,n-1p=1,n-1，都有，都有，都有，都有b bp paap+1p+1，则此种情况，则此种情况，则此种情况，则此种情况不

26、不不不存在抢先问题存在抢先问题存在抢先问题存在抢先问题；（二）若存在（二）若存在（二）若存在（二）若存在b bp paap+1p+1，设，设，设，设p p是第一个使得是第一个使得是第一个使得是第一个使得b bp paap+1p+1的下标，的下标，的下标，的下标，此时允许抢先，分以下情形：此时允许抢先，分以下情形：此时允许抢先，分以下情形：此时允许抢先，分以下情形：设设设设mm是第一个满足是第一个满足是第一个满足是第一个满足b bp p+b+bp+1p+1+b+bmmaap+1p+1+a+am+1m+1的的的的下标，则无论是抢先与否，下标，则无论是抢先与否，下标，则无论是抢先与否，下标，则无论是

27、抢先与否，b bmm执行完毕的时间均为执行完毕的时间均为执行完毕的时间均为执行完毕的时间均为 ,而而而而b bm+1m+1则从则从则从则从a am+1m+1结束处时间开始执行，此时再一次结束处时间开始执行，此时再一次结束处时间开始执行，此时再一次结束处时间开始执行，此时再一次针对针对针对针对m+1pn-1m+1pn-1考虑考虑考虑考虑(一一一一)()(二二二二)两种情况。两种情况。两种情况。两种情况。若不存在若不存在若不存在若不存在所描述的所描述的所描述的所描述的mm，则有对任意，则有对任意，则有对任意，则有对任意p+1mn-1p+1mn-1，均有，均有，均有，均有 ，即任意，即任意，即任意，

28、即任意p+1jm+1p+1jm+1，a aj j执行完时，执行完时，执行完时，执行完时，都可以抢先执行都可以抢先执行都可以抢先执行都可以抢先执行b bj j，无论抢先与否，总执行时间均，无论抢先与否，总执行时间均，无论抢先与否，总执行时间均，无论抢先与否，总执行时间均为为为为4646P152-15n n 证明对于证明对于I存在着一种作业在两台设存在着一种作业在两台设备上按相同次序处理的备上按相同次序处理的OFT调度。调度。n n往证：在两台设备上处理的任务分别采往证：在两台设备上处理的任务分别采用不同的处理次序，在调度完成时间上用不同的处理次序，在调度完成时间上不比采用相同的处理次序强。不比采

29、用相同的处理次序强。4747P152-15设有两种处理方式：设有两种处理方式：设有两种处理方式：设有两种处理方式：I I1 1采用相同的处理次序，采用相同的处理次序，采用相同的处理次序，采用相同的处理次序，I I2 2采用不同的处采用不同的处采用不同的处采用不同的处理次序理次序理次序理次序 I I1 1:ai:ai1 1 ai ai2 2 ai aik k I I2 2:ai:ai1 1 ai ai2 2 ai aik k bi bi1 1 bi bi2 2 bi bik k bj bj1 1 bj bj2 2 bj bjk kn n设设设设I I1 1II2 2，令，令，令，令a a是第一个

30、使得是第一个使得是第一个使得是第一个使得j ja aiia a的下标，即：对的下标，即：对的下标，即：对的下标，即：对p=1,2,a-1p=1,2,a-1，都有，都有，都有，都有i ip p=j=jp p.情况（一）情况（一）情况（一）情况（一）bibia-1a-1执行完时，执行完时，执行完时，执行完时，aiaia a尚未执行完，尚未执行完，尚未执行完，尚未执行完，ajaja a未开始执行。未开始执行。未开始执行。未开始执行。在在在在I I1 1上上上上bibia a必须开始的时间必须开始的时间必须开始的时间必须开始的时间t1t1肯定小于等于肯定小于等于肯定小于等于肯定小于等于I I2 2上上

31、上上bjbja a必须开始的必须开始的必须开始的必须开始的时间时间时间时间t2t2，故，故，故，故I I2 2的执行时间大于等于的执行时间大于等于的执行时间大于等于的执行时间大于等于I I1 1的执行时间；的执行时间；的执行时间；的执行时间；情况（二）若情况（二）若情况（二）若情况（二）若bibia-1a-1执行完时，执行完时，执行完时，执行完时，aiaia a已经执行完，但已经执行完，但已经执行完，但已经执行完，但ajaja a未执行完，未执行完，未执行完，未执行完，同样同样同样同样t(It(I2 2)t(I)t(I1 1)；情况（三）若情况（三）若情况（三）若情况（三）若bibia-1a-

32、1执行完时，执行完时，执行完时，执行完时，aiaia a 、ajaja a均已执行完，则均已执行完，则均已执行完，则均已执行完，则I I1 1中的中的中的中的bibia a与与与与I I2 2中的中的中的中的bjbja a开始执行时间相同，再考虑下一个开始执行时间相同，再考虑下一个开始执行时间相同，再考虑下一个开始执行时间相同，再考虑下一个j ja aiia a的下标。的下标。的下标。的下标。4848P152-15 证明对于证明对于I存在着由作业的某种排列存在着由作业的某种排列(见见)所定义的所定义的OFT调度，而这种排列调度，而这种排列中所有中所有ai=0的作业均在这排列的前部。的作业均在这

33、排列的前部。进而证明此排列前部那些进而证明此排列前部那些ai=0的作业出的作业出现的次序是无关紧要的。现的次序是无关紧要的。4949P152-15n n设一个设一个设一个设一个OFTOFT调度其在设备调度其在设备调度其在设备调度其在设备a a和和和和b b上分别为：上分别为：上分别为：上分别为：ai1,aikai1,aik，和，和，和，和bi1,bik bi1,bik。并假设。并假设。并假设。并假设a a是第一个是第一个是第一个是第一个aiaia a=0=0，但，但，但，但aiaia-1a-100，即对于所有，即对于所有，即对于所有，即对于所有1pa-11pa-1，aiaip p00，将，将，

34、将，将aiaia a和和和和bibia a移至最前部，得到移至最前部，得到移至最前部，得到移至最前部，得到I I。n n显然显然显然显然I I的调度长度是小于等于的调度长度是小于等于的调度长度是小于等于的调度长度是小于等于I I的调度长度的。如的调度长度的。如的调度长度的。如的调度长度的。如此反复，可以将所有这样的此反复，可以将所有这样的此反复，可以将所有这样的此反复，可以将所有这样的aiaia a=0=0的作业移至最前的作业移至最前的作业移至最前的作业移至最前端，而不增加该调度的长度，因此结论成立。端，而不增加该调度的长度，因此结论成立。端，而不增加该调度的长度，因此结论成立。端，而不增加该

35、调度的长度，因此结论成立。n n进一步，无论这些进一步，无论这些进一步，无论这些进一步，无论这些a ai i=0=0的作业如何排列，其对应在的作业如何排列，其对应在的作业如何排列，其对应在的作业如何排列，其对应在b b上的执行时间均为上的执行时间均为上的执行时间均为上的执行时间均为5050P152-17n n最优性原理并不总是对可以将其解看成最优性原理并不总是对可以将其解看成是一系列决策结果的所有问题成立。找是一系列决策结果的所有问题成立。找两个最优性原理不成立的例子，并说明两个最优性原理不成立的例子，并说明对这两个问题最优性原理为什么不成立。对这两个问题最优性原理为什么不成立。5151P152-17n n无论过程的初始状态和初始决策是什么，无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。生的状态构成一个最优决策序列。n n多段图问题，以乘法为路径长度，当含多段图问题，以乘法为路径长度，当含有负权时。有负权时。