算法分析第六章答案

1计算机算法分析—习题课第六章1,2,3,4,5,6,7,8,12,13,15,172动态规划1.多阶段过程2.满足最优性原理3.建立递推关系式3P151-1①递推关系式(6.8)对右图成立吗？为什么？②递推关系式(6.8)为什么对于含有负长度环的图不能成立？12345674536-429314Ak(i,j)=min{Ak-1(i,j),Ak-1(i,k)+Ak-1(k,j)},k1①成立，不包含负长度环.P130②可以使结点间的长度任意小。P151-15P151-2修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？回忆算法：P131算法6.3P127算法6.16P131算法6.3对矩阵进行初始化，每个元素赋值为边的成本(1－5行)迭代计算最短路径长度(6－12行)Ak(i,j)=min{Ak-1(i,j),Ak-1(i,k)+Ak-1(k,j)},k17P127算法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的后继结点。8ProcedureShortestPath(COST,n,A,Max)integeri,j,krealCOST(n,n),A(n,n),Path(n,n),Maxfori←1tondo//初始化最优路径矩阵forj←1tondoA(i,j)←COST(i,j)ifi≠jandA(i,j)≠MaxthenPath(i,j)←jelsePath(i,j)←0endifrepeatrepeat9fork←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)endifrepeatrepeatrepeat10fori←1tondo//输出最优路径forj←1tondoprint(“thepathofitojis”i)k←path(i,j)whilek≠0doprint(k)k←path(k,j)repeatrepeatrepeatendShortestPath11复杂度分析时间复杂度第一个循环：O(n2)第二个循环：O(n3)第三个循环：O(n3)空间复杂度Cost(n,n)A(n,n)Path(n,n)O(n2)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递推关系式：W(i,j)=Q(i)i=jW(i,j-1)+P(j)+Q(j)ijC(i,j)=0i=jW(i,j)+min{C(i,k-1)+C(k,j)}ijk在R(i,j-1)和R(i+1,j)中，使C(i,k-1)+C(k,j)取最小值。R(i,j)=k14P136算法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)=115WRC44+2+1=77+4+4=1515+2+1=1818+1+1=20012220722323922+4+4=1010+2+1=1313+1+1=150222010202744+1+2=77+1+1=9033071211+1+1=30403100ijj-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)=116P151-4①证明算法OBST的计算时间是O(n2)。②在已知根R(i,j)，0ij4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。17①将C中元素的加法看做基本运算，则算法OBST的时间复杂性为：O(n2)20((1,)(,1)1)nnmmiRijRij20((1,)(,1)1)nnmmiRiimRiim2((1,)(0,1)1)nmRnmnRmnm18②实现思想k←R(m,n)如果k≠0–创建结点root–令data(Root)←k–令m=m，n=k-1，递归构造左子树–令m=k，n=n，递归构造右子树19②ProcedureBuildTree(A,m,n,R,Root)integerR(n,n),kTreeNodeRoot,LR,RRifm=nthendata(Root)←null,elseifm+1=nthendata(Root)←A(n),left(Root)←null,right(Root)←null,endifelsek←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)←RRendifendBuildTree时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。20②ProcedureBuildTree(m,n,R,Root)integerR(n,n),kTreeNodeRoot,LR,RRif(mn)thenk←R(m,n)ifk≠0thendata(Root)←k//内结点BuildTree(m,k-1,R,LR)BuildTree(k,n,R,RR)left(Root)←LRright(Root)←RRelseRoot←null//外结点endifendifendBuildTree21P151-5由于我们通常只知道成功检索和不成功检索概率的近似值，因此，在较短的时间内找出几乎是最优的二分检索树，这也可能是一件很有意义的工作。所谓几乎是最优的二分检索树，就是对于给定的P和Q，该树的成本(由(6.9)式计算)几乎最小。已经证明，由以下方法获得这种检索树的算法可以有O(nlogn)的时间复杂度：选取这样的k为根，它使|W(0,k-1)-W(k,n)|尽可能地小。重复以上步骤去找这根的左、右子树。22P151-5①对于习题6.3的数据，用上述方法找出一棵这样的二分检索树。它的成本是什么？②用SPAKS写一个实现上述方法的算法，你的算法的计算时间为O(nlogn)吗？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)=4471518202101315479131选取这样的k为根，使|W(0,k-1)-W(k,n)|尽可能小①矩阵W如右所示，相应的k从1到4得式如下：24又知标识符集合(a1,a2,a3,a4)=(end,goto,print,stop),检索概率化简为整数形式–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总体成本是2*(4+2+1)+4+2*(2+4)+3*(1+1+1)=39a2a1a3a425实现思想：如果n-m=0，r[m][n]=0如果n-m=1，r[m][n]=n如果n-m1，求使|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②ProcedureCreateTree(m,n,root,w)integerr,k,root(n,n),w(n,n)realww,min←+∞ifm=nthenroot(m,n)←0elseifm=n-1thenroot(m,n)←nelsefork←m+1tondoww←|w(m,k-1)-w(k,n)|ifwwminthenmin←ww,r←kendifrepeatroot(m,n)←rCallCreateTree(m,r-1,root,w)CallCreateTree(r,n,root,w)endifendifEndBuildTree通过求解递归关系式可得，时间复杂性平均情况是O(nlogn)，27P151-6设(w1,w2,w3,w4)=(10,15,6,9),(p1,p2,p3,p4)=(2,5,8,1)。生成每个fi阶跃点的序偶集合Si，0i4。280S={(0,0)}11S={(2,10)}1S={(0,0),(2,10)}21S={(5,15),(7,25)}2S={(0,0),(2,10),(5,15),(7,25)}31S={(8,6),(10,16),(13,21),(15,31)}3S={(0,0),(8,6),(10,16),(13,21),(15,31)}41S={(1,9),(9,15),(11,25),(14,30),(16,40)}4S={(0,0),(8,6),(9,15),(10,16),(13,21),(14,30),(15,31),(16,40)}(p1,p2,p3,p4)=(2,5,8,1)(w1,w2,w3,w4)=(10,15,6,9)29P151-7假设在过程DKNAP已算出了Si，0in,写一个确定0/1背包问题的最优决策序列x1,x2,…,xn的算法PARTS。由于已知道F(i)和F(i+1)，因此我们可以使用二分检索方法去确定序偶(P,W)是否属于Si。所以你的算法的时间复杂度不应大于O(nmax{log|Si|})O(n2)。30实现思想：1：令(P,W)为最优解所对应的序偶,i=n-12：如果i0，重复下列操作：–在F(i)和F(i+1)之间使用二分检索法查找(P,W)。–若存在，Xi+1=0;–否则，(P,W)=(P-Pi+1,W-Wi+1)，Xi+1=1。–i＝i-131ProcedurePARTS(n,F,M,P,W,p,w)/*p(n)和w(n)是存放原数据的，P(m)和W(m)是存放S的，F(n)是存放指针的，x(n)是存放元素取舍结果的*/integern,k,i,j,F(0:n),x(n)realP(m),W(m),pp,ww,p(n),w(n)32/*确定：x(n)、最优解所对应的序偶(pp,ww)，其所在位置j，j在F(n-1)和F(n)之间*/k←F(n)-1ww←W(k)pp←P(k)j←k//k为Sn-1的最末位置whileW(j)+w(n)Mandj=F(n-1)doj←j-1repeat//找Sn的最末位置jif(ppP(j)+p(n)andj=F(n-1))thenx(n)←1,pp←P(j),ww←W(j)elsex(n)←0endif33/*使用二分检索法在W上F(i)和F(i+1)范围之间查找ww，确定x(i+1)*/for