算法设计与分析课件 26 动态规划算法_第1页
算法设计与分析课件 26 动态规划算法_第2页
算法设计与分析课件 26 动态规划算法_第3页
算法设计与分析课件 26 动态规划算法_第4页
算法设计与分析课件 26 动态规划算法_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析本节要点CONTENTS动态规划算法动态规划算法动态规划（DynamicProgramming，DP）是理查德·贝尔曼在研究多阶段决策过程优化问题时，提出的最优化原理。动态规划是一种表格处理法，它把原问题分解为若干子问题，自底向上先求解最小的子问题，把结果存储在表格中，在求解大的子问题时直接从表格中查询小子问题的解，避免重复计算，从而提高效率。动态规划算法0102哪些问题可以使用动态规划？常用的动态规划模板有哪些？03动态规划求解的秘籍是什么？动态规划算法01哪些问题可以使用动态规划？0102最优子结构子问题重叠03无后效性动态规划算法02常用的动态规划模板有哪些？动态规划算法03动态规划求解的秘籍是什么？决策阶段状态动态规划算法动态规划把原问题划分为若干子问题，每个子问题的求解过程构成一个阶段，求解完前一阶段后再求解后一阶段。根据无后效性，动态规划的求解过程构成一个有向无环图，求解的顺序就是该有向无环图的一个拓扑序。在有向无环图中，节点对应问题的状态，有向边对应状态之间的转移，转移时作出的选择就是决策。状态、阶段、决策是动态规划的三个要素。动态规划算法例如，使用动态规划求解单源最短路径问题。动态规划算法（1）确定状态。dp[i]表示源点到节点i的最短距离。（2）划分阶段。根据拓扑序列划分阶段。（3）决策选择。考察当前节点的逆邻接点，将所有逆邻接点的最短距离与边权之和取最小值得到dp[i]。

状态转移方程：

dp[i]=min(dp[j]+w[j][i])

（4）边界条件。若源点为1，则令dp[1]=0。（5）求解目标。dp[i]，i=2,3,…,n。动态规划算法求解动态规划问题时，如何确定状态和状态转移方程是关键，也是难点。不同状态表示和状态转移方程的算法复杂度可能不同。动态规划问题灵活

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论