计算机算法设计与分析：第四章 动态规划.ppt
版权申诉
120 浏览量
2022-06-14
11:53:54
上传
评论
收藏 3.33MB PPT 举报
第四章 动态规划
4.1 一般方法
一、面向的问题类：多阶段决策过程。
多阶段决策过程：活动的过程可以分为若干个阶段，而且在任一阶段后的行为都
仅依赖于该阶段的过程状态，而与该阶段之前的过程如何达到这种状态的方式无关。
二、目标：获得问题最优解的决策序列，即最优决策序列。
在多阶段决策的每一阶段，都可能有多种可供选择的决策，必须从中选取一种决
策。一旦各个阶段的决策选定之后，就构成了解决这一问题的一个决策序列。决策
序列不同，所导致的问题的结果也不同。动态规划的目标就是要在所有容许选择的
决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。
三、方法：
① 穷举—笨。
② 贪心—太严格。它要求每一决策步上都能得到局部最优解。（有时不能
仅从局部信息获得最优判定序列）
③ 动态规划—每一步上列出各种可能的局部解，然后按某些条件放弃哪些
不能得到最优解的局部解。
剩余57页未读，继续阅读
评论0
最新资源