北京大学-动态规划-讲解PDF.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.87M 资料格式：pdf 举报版权申诉

csjapan-10280589-4744302543286228877.pdf-第1页.png

第1页 / 共57页

csjapan-10280589-4744302543286228877.pdf-第2页.png

第2页 / 共57页

csjapan-10280589-4744302543286228877.pdf-第3页.png

第3页 / 共57页

csjapan-10280589-4744302543286228877.pdf-第4页.png

第4页 / 共57页

csjapan-10280589-4744302543286228877.pdf-第5页.png

第5页 / 共57页

csjapan-10280589-4744302543286228877.pdf-第6页.png

第6页 / 共57页

csjapan-10280589-4744302543286228877.pdf-第7页.png

第7页 / 共57页

csjapan-10280589-4744302543286228877.pdf-第8页.png

第8页 / 共57页

文本预览

程序设计实习(II): 算法设计程序设计实习(II): 算法设计第二十讲动态规划

上一节课回顾  影响搜索效率的因素 搜索对象 (枚举什么） 搜索顺序 (先枚举什么后枚举什么) 搜索顺序 (先枚举什么，后枚举什么)  BFS：广度优先  DFS：深度优先先  A*：估价函数最小优先 剪枝 (及早判断出不符合要求的情况) 3 3

问题提出:为什么要用动态规划  BFS和DFS：树形递归存在冗余计算  例1：POJ 2753 Fibonacci数列 i数列求 Fibonacci数列的第n项求 Fibonacci数列的第n项 int f(int n){ ib if(n==0 || n==1) return n; return f(n-1)+f(n-2); f( 1) f( 2) }} 4

树形递归存在冗余计算为了除去冗余，需要从已知条件开始计算，并记录计算过程中的中间结果 f(5) f(5) 录计算过程中的中间结果 f(4) f(3) f(3) f(2) f(2) f(1) f(2) f(1) f(1) f(0) f(1) f(0) 1 1 1 0 1 0 f(1) f(0) 1 0 冗余计算! 5

树形递归存在冗余计算去除冗余： int f[n+1]; int f[n+1]; f[1]=f[2]=1; int i; for(i=3;i<=n;i++) ( ) f[i] = f[i-1]+f[i-2]; cout << f[n] <

什么是动态规划?  动态规划是求解包含重叠子问题的最优化方法 基本思想: 将原问题分解为相似的子问题 在求解的过程中通过保存子问题的解求出原问题的解 在求解的过程中通过保存子问题的解求出原问题的解（注意:不是简单分而治之） 只能应用于有最优子结构的问题（即局部最优解能决定全局最优解，或问题能分解成子问题来求解）最解，解来解  动态规划=记忆化搜索 7

 例2 POJ 1163 数字三角形数字角动态规划是如何工作的 7 3 8 2 4 2 7 4 4 7 4 8 1 0 4 5 2 6 5  在上面的数字三角形中寻找一条从顶部到底边的路径，在上面的数字角形中寻找条从顶部到底边的路径使得路径上所经过的数字之和最大  路径上的每步都只能往左下或右下走只需要求出这  路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径  三角形的行数大于1小于等于100  三角形的行数大于1小于等于100  数字为 0 - 99 8

POJ 1163 数字三角形问题输入格式: 5 //三角形行数,下面是三角形 77 3 8 8 1 08 1 0 2 7 4 4 4 5 2 6 5 要求输出最大和 9

分享到：

赞收藏

资料库

北京大学-动态规划-讲解PDF.pdf

相关推荐

课程资源

热门标签

最新资料