计算机算法分析—习题课六.pptVIP

计算机算法分析—习题课 2011年6月 第六章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) 3－7行 计算出D( j ) 之后，即可计算最短路径。9－11行 P131 算法6.3 对矩阵进行初始化，每个元素赋值为边的长度（如果没边则赋值成MAX）1－5行 迭代计算最短路径长度6－12行 仿照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 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(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)（0≤i, j≤4）。 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)，0≤i j≤4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。 ② Procedure BuildTree(m, n, R, Root) integer R(n,n), k TreeNode Root, LR, RR k←R(m,n) if k≠0 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(