算法设计与分析40学时课件ch4new
56页1、第四章 动态规划技术,骆吉洲 计算机科学与工程系,4.1 动态规划原理 4.2 最长公共子序列 4.3 矩阵链惩罚 4.4 0/1背包问题 4.5 最优二叉搜索树,提要,参考资料,Introduction to Algorithms 第15章: 15.2, 15.3, 15.4, 15.5 计算机算法设计与分析 第3章: 3.1, 3.3, 3.5, 3.10, 3.11 网站资料 第四章,4.1 动态规划技术的基本要素,为什么引入动态规划? 什么是动态规划? 如何进行动态规划?,分治技术的问题 子问题是相互独立的 如果子问题不是相互独立的,分治方法将重复计算公共子问题,效率很低 例如,计算斐波那契数列的第n项 F(0)=F(1)=1 F(n)=F(n-1)+F(n-2),Why?,分治技术的问题 子问题是相互独立的 如果子问题不是相互独立的,分治方法将重复计算公共子问题,效率很低 分治算法 算法F(n) 输入:非负整数n 输出:斐波那契数列第n项 1. If n=0 或1 Then 输出1,算法结束 2. f1F(n-1); 3. f2F(n-2); 4. 输出f1+f2;,Why?
2、,时间复杂性 T(1)=T(0)=1 T(n)=T(n-1)+T(n-2) T(n)不是多项式有界的,提高效率的方法 从规模最小的子问题开始计算 用恰当数据结构存储子问题的解,供以后查询 确保每个子问题只求解一次 算法 算法F(n) 输入:非负整数n 输出:斐波那契数列第n项 1. A0 1; A1 1; 2. For i=2 To n 3. Ai Ai-1+Ai-2; 4. 输出An;,Why?,时间复杂性 T(n)=(n) 存在(log n)的分治算法,DB-LAB(2003),分治技术的问题 子问题是相互独立的 如果子问题不是相互独立的,分治方法将重复计算公共子问题,效率很低 优化问题 给定一组约束条件和一个代价函数,在解空间中搜索具有最小或最大代价的优化解 很多优化问题可分为多个子问题,子问题相互关联,子问题的解被重复使用,Why?,DB-LAB(2003),动态规划算法特点 把原始问题划分成一系列子问题 求解每个子问题仅一次,并将其结果保存在一个表中,以后用到时直接存取,不重复计算,节省计算时间 自底向上地计算 适用范围 一类优化问题:可分为多个相关子问题,子问题的解被重复使
3、用,What?,使用Dynamic Programming的条件 Optimal substructure(优化子结构) 当一个问题的优化解包含了子问题的优化解时,我们说这个问题具有优化子结构。 缩小子问题集合,只需那些优化问题中包含的子问题,减低实现复杂性 优化子结构使得我们能自下而上地完成求解过程 Subteties(重叠子问题) 在问题的求解过程中,很多子问题的解将被多次使用,How?,动态规划算法的设计步骤 分析优化解的结构 递归地定义最优解的代价 自底向上地计算优化解的代价保存之, 并获取构造最优解的信息 根据构造最优解的信息构造优化解,4.2 最长公共子序列,问题的定义 最长公共子序列 (LCS) 结构分析 建立求解LCS长度的递归方程 自底向上LCS长度的计算 构造优化解,子序列 X=(A, B, C, B, D, B) Z=(B, C, D, B)是X的子序例 W=(B, D, A)不是X的子序例 公共子序列 Z是序列X与Y的公共子序列如果Z是X的子序也是Y的子序列。,问题的定义,最长公共子序列(LCS)问题 输入:X = (x1,x2,.,xn),Y = (y1,y2
4、,.ym) 输出:Z = X与Y的最长公共子序列,蛮力法 枚举X的每个子序列Z 检查Z是否为Y的子序列 T(n)=O(m2n),最长公共子序列结构分析,第i前缀 设X=(x1, x2, ., xn)是一个序列,X的第i前缀Xi是一个序列,定义为Xi=(x1, ., xi ) 例. X=(A, B, D, C, A), X1=(A), X2=(A, B), X3=(A, B, D),优化子结构 定理1(优化子结构)设X=(x1, ., xm)、Y=(y1, ., yn) 是两个序列,Z=(z1, ., zk)是X与Y的LCS,我们有: 如果xm=yn, 则zk=xm=yn, Zk-1是Xm-1和Yn-1的LCS, 即,LCSXY = LCSXm-1Yn-1+ . 如果xmyn,且zkxm,则Z是Xm-1和Y的LCS,即 LCSXY= LCSXm-1Y 如果xmyn,且zkyn,则Z是X与Yn-1的LCS,即 LCSXY= LCSXYn-1,证明: . X=, Y=,则 LCSXY = LCSXm-1Yn-1+ . 设zkxm,则可加xm=yn到Z,得到一个长为k+1的X与Y 的公共序列,
《算法设计与分析40学时课件ch4new》由会员E****分享,可在线阅读,更多相关《算法设计与分析40学时课件ch4new》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-05-07 48页
2024-05-07 41页
2024-05-07 36页
2024-05-07 33页
2024-05-07 43页
2024-05-07 30页
2024-05-07 27页
2024-05-07 31页
2024-05-07 44页
2024-05-07 39页