算法分析第六章答案.ppt

计算机算法分析—习题课 第六章1,2,3,4,5,6,7,8,12,13,15,17 动态规划 多阶段过程 满足最优性原理 建立递推关系式 P151-1 ①递推关系式(6.8)对右图成立吗？为什么？ ②递推关系式(6.8)为什么对于含有负长度环的图不能成立？ P151-1 Ak(i,j) = min{Ak-1(i,j), Ak-1(i,k)+Ak-1(k,j)} , k?1 P151-2 修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？ 回忆算法：P131 算法6.3 P127 算法6.1  P131 算法6.3 对矩阵进行初始化，每个元素赋值为边的成本(1－5行) 迭代计算最短路径长度 (6－12行) Ak(i,j) = min{Ak-1(i,j), Ak-1(i,k)+Ak-1(k,j)} , k?1 P127 算法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的后继结点。 Procedure ShortestPath(COST, n, A, Max) integer i , j, k real COST(n, n), A(n, n), Path(n, n), Max for i←1 to n do //初始化最优路径矩阵 for j←1 to n do A(i ,j)←COST(i ,j) if i≠j and A(i, j)≠Max then Path(i, j )←j else Path(i, j)←0 endif repeat repeat for k←1 to n do //迭代计算 for i←1 to n do for j←1 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 i←1 to n do//输出最优路径 for j←1 to n do print(“the path of i to j is ” i ) k←path(i, j) while k≠0 do print(k) k←path(k, j) repeat repeat repeat end ShortestPath 复杂度分析 时间复杂度第一个循环： O(n2)第二个循环： O(n3)第三个循环： O(n3) 空间复杂度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) (0≤i, j≤4)。 递推关系式： W(i,j) = Q(i) i=j W(i, j-1)+P(j)+Q(j) ij C(i,j) = 0 i=j W(i, j)+min{C(i, k-1)+C(k, j)} ij k在R(i,j-1)和R(i+1,j)中，使C(i,k-1)+C(k,j)取最小值。 R(i,j) = k 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)。 ②