算法分析第六章答案.ppt

  1. 1、本文档共51页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法分析第六章答案

计算机算法分析—习题课 第六章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)。 ②

文档评论(0)

dajuhyy + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档