计算机算法分析习题课,2008年5月 第六章1 2 3 4 5 6 8 13 17,动态规划,多阶段过程 满足最优性原理 建立递推关系式,P151-1,递推关系式（6.8）对右图成立吗？为什么？ 递推关系式（6.8）为什么对于含有负长度环的图不能成立？ 解： 成立，不包含负长度环 可以使节点间的长度任意小。,P151-2,修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？ 回忆算法：P127 算法 6.1 P131 算法 6.3,P127 算法6.1,D(i,j)/D(j) :从节点j到汇点t的最优路径中下一个节点，即最优路径中j的后继节点。 算法6.1在计算COST(j)的同时也计算了D(j) 37行 计算出D( j ) 之后，即可计算最短路径。911行,P131 算法6.3,对矩阵进行初始化，每个元素赋值为边的长度（如果没边则赋值成MAX）15行 迭代计算最短路径长度612行 仿照6.1，在每次计算最短路径的时候计算出D(j) 再通过D(j) 就可以表示出最短路径,Procedure ShortestPath(COST, n, A, Max) integer i , j, k real COST(n, n), A(n, n), Path(n, n), Max for i1 to n do /初始化最优路径矩阵 for j1 to n do A(i ,j)COST(i ,j) if ij and A(i, j)Max then Path(i, j )j else Path(i, j)0 endif repeat repeat,Path(i,j)是从i到j的最短路径上，结点i的后续结点编号。,for k1 to n do /迭代计算 for i1 to n do for j1 to n do if A(i,j)A(i,k)+A(k,j) then A(i,j)A(i,k)+A(k,j) Path(i,j)Path(i,k) endif repeat repeat repeat,for i1 to n do/输出最优路径 for j1 to n do print(“the path of i to j is ” i ) kpath(i, j) while k0 do print(k) kpath(k, j) repeat repeat repeat end ShortestPath,分析,时间复杂度第一个循环： O(n2)第一个循环： O(n3)第一个循环： O(n2) 空间复杂度Cost(n,n) A(n,n) Path(n,n)O(n2),P151-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)（0i, j4）。,P136 算法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,P151-4,证明算法OBST的计算时间是O(n2)。 在已知根R(i, j)，0i j4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。, Procedure BuildTree(m, n, R, Root) integer R(n,n), k TreeNode Root, LR, RR kR(m,n) if k0 then data(Root)k, BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR) left(Root)LR, right(Root)RR else data(Root)m, left(Root)null, right(Root)null, endif end BuildTree 时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。,P151-5 由于我们通常只知道成功检索和不成功检索概率的近似值，因此，若能在较短的时间内找出几乎是最优的二分检索树，也是一件很有意义的工作。所谓几乎是最优的二分检索树，就是对于给定的P和Q，该树的成本（由（6.9）式计算）几乎最小。已经证明，由以下方法获得这种检索树的算法可以有O(nlogn)的时间复杂度，选取这样的k为根，它使|W(0, k-1)- W(k, n) |尽可能地小。重复以上步骤去找这根的左、右子树。 对于题6.3的数据，用上述方法找出一棵这样的二分检索树。它的成本是什么？ 用SPAKS写一个实现上述方法的算法，你的算法的计算时间为O(nlogn)吗？,解：矩阵W如下所示，相应的k从1到4得式如下： |W(0,0)-W(1,4)|=11,|W(0,1)-W(2,4)|=2,|W(0,2)-W(3,4)|=12,|W(0,3)-W(4,4)|=17 所以该树的根是T(0,4)=2，依次计算得到T(0,1)=1，T(2,4)=3，T(3,4)=4 总体成本是4+2*（2+1）+2*（4+2+4）+3*（1+1+1）=39,Procedure CreateTree(m, n, root, w) integer r, k, root(n, n), w(n, n) real ww, min if m=n then root(m, n)0 else if m=n-1 then root(m,n)n else for km+1 to n do ww|w(m, k-1)-w(k, n)| if ww min then minww, rk endif repeat root(m, n)r Call CreateTree(m, r-1) Call CreateTree(r, n) endif End BuildTree 时间复杂性最好和平均的情况应该是O(nlogn)，但最坏的情况是O(n2),P151-6,设(w1,w2,w3,w4)=(10,15,6,9), (p1,p2,p3,p4)=(2,5,8,1)。生成每个fi阶跃点的序偶集合Si，0i4。,P151-8,给出一个使得DKNAP(算法6.7)出现最坏情况的例子，它使得| Si |=2i, 0in。还要求对n的任意取值都适用。,P151-8,取(P1,P2,Pi,) =(W1,W2,Wi,) =(20,21,2i-1,) P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。,假定两个仓库W1和W2都存有同一种货物，其库存量分别为r1和r2。想要将其全部发往n个目的地D1,D2,Dn. 设发往Dj的货物为dj，因此r1+r2=dj.如果由仓库Wi发送量为xij的货物到目的地Dj的花费为Cij，那么仓库问题就是求各个仓库应给每个目的地发多少货才使总的花费最小。即要求出这些非负整数xij，1i2,1jn，它使得x1j+x2j=dj, 1jn，并且使ijcij(xij)取最小值。假设当W1有x的库存且按最优方式全部发往目的地D1,D2,Di时所需的花费为gi(x)(W2的库存为dj-x)。于是此仓库问题的最优总花费是gn(r1).,P152-13,P128-13,求gi(x)的递推关系式 写一个算法求解这个递推关系式并要能得到xij的决策值得最优序列，1i2,1jn.,P152-17,最优性原理并不总是对可以将其解看成是一系列决策结果的所有问题成立。找两个最优性原理不成立的例子，并说明对这两个问题最优性原理为什么不成立。,多段图问题：路径和改为路径乘积并允许出现负数,