- 1、本文档共60页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
1 1 F 2 2 F 4 + 1 = 5 2 + 2 = 4 4 E2 6 + 1 = 7 9 + 2 = 11 7 E1 7 + 1 = 8 5 + 2 = 7 7 E2 1 + 4 = 5 5 + 7 = 12 / / / 5 D1 8+ 4 = 12 4 + 7 = 11 6 + 7 = 13 11 D2 4+ 4 = 8 4+ 7 = 11 2+ 7 = 9 8 D1 9+ 5 = 14 5+ 11 = 16 / / / 14 C1 4+ 5 = 9 3+ 11 = 14 5+ 8 = 13 9 C1 / / / 1+ 11 = 12 7+ 8 = 15 12 C2 3+ 14 = 17 5+ 9 = 14 4+ 12 = 16 14 B2 下 顶 A B1 B2 B3 C1 C2 C3 D1 D2 D3 E1 E2 F 3 5 4 9 5 4 3 5 1 7 1 5 8 4 6 4 4 2 2 2 6 9 7 5 1 4 即: A ? B2 ? C1 ? D1 ? E2 ? F 本章小结 动态规划法的设计思想: 把求解的问题分成许多阶段或多个子问题,然后按顺序求解各子问题,最后一个子问题就是初始问题的解。 动态规划算法的基本要素: 最优性原理、子问题重叠性 设计动态规划算法的基本步骤: 分析最优解的性质,并刻划其结构特征; 递归地定义最优值; 以自底向上的方式计算出最优值; 根据计算最优值时得到的信息,自顶向下构造最优解。 课后作业 1. 用动态规划法求解下图中从顶点0到顶点15的最短路径,写出求解过程。 练习:给定集合{k1,k2,k3,k4,k5},满足k1<k2<k3<k4<k5,查找成功的概率分别为:p1=0.15,p2=0.1,p3=0.05,p4=0.1,p5=0.2,失败的概率为:q0=0.05,q1=0.1,q2=q3=q4=0.05,q5=0.1。构造一颗具有最小平均查找长度的二叉有哪些信誉好的足球投注网站树。 A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 ⑷ 构造最优解 依据MatrixChain算法中数组s[i][j]记录的信息,可以确定计算矩阵链A[i:j]的最佳方式应该在矩阵Ak和Ak+1之间断开,即最优加括号的方式应为(A[i:k])(A[k+1:j])。因此,递归地构造最优解: void Traceback (int i, int j, int **s) { if (i==j) return; Traceback(i, s[i][j], s); Traceback(s[i][j]+1, j, s); cout“Multiply A”i“,”s[i][j]; cout“and A”(s[i][j]+1)“,”jendl; } 6.2 动态规划算法的基本要素 最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。 最优子结构是问题能用动态规划算法求解的前提。 用反证法说明问题的最优子结构性质。 重叠子问题 递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。 课后作业 1. 对以下5个矩阵相乘应用算法MatrixChain及算法Traceback。 A1:4*5,A2:5*3,A3:3*6, A4:6*4,A5:4*5 ⑴找出这5个矩阵相乘所需的最少数乘的次数m[1, 5]及部分中间结果m[i, j]: ⑵给出s[i, j]及最优括号表达式。 0 m[1,2]= m[1,3]= m[1,4]= m[1,5]= 0 m[2,3]= m[2,4]= m[2,5]= 0 m[3,4]= m[3,5]= 0 m[4,5]= 0 i j 6.3.1 最长公共子序列 子序列:若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik},使得对于所有j=1,2,…,k有:zj=xij。 例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。 公共子序列:给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。 6.3 动态规划法应用举例 问题
您可能关注的文档
最近下载
- 滁州市2017-2018年度一师一优课、一课一名师活动市级.PDF VIP
- 国家药监局关于发布免于临床评价医疗器械目录的通告(2023年第33号).pdf
- 杭州市西湖区各级文物保护单位一览表(2023版).docx VIP
- 杭州市萧山区各级文物保护单位一览表(2023版).docx VIP
- 《《亚克西巴郎》ppt课件》小学音乐苏少版二年级上册_3.ppt
- 幼儿园课件:小班数学形状《小熊饼干店》.ppt
- 杭州市上城区各级文物保护单位一览表(2023版).docx VIP
- 现代控制工程(第五版)卢伯英习题答案解析.pdf
- 2022年考研英语一必威体育精装版完整版真题.pdf
- 专业气象服务标准化工作.doc
文档评论(0)