文档介绍：1
第六章动态规划
动态规划的思想方法
多段图的最短路径问题
资源分配问题
设备更新问题
最长公共子序列问题
0/1 背包问题
RNA 最大碱基对匹配问题
2
动态规划的思想方法
一动态规划的最优决策原理
二动态规划实例、货郎担问题
3
一动态规划的最优决策原理
1. 活动过程的分阶段决策
2. 最优性原理
3. 最优决策的形成
4
1. 活动过程的分阶段决策
把活动过程划分为若干个阶段,每一阶段的决策,依赖于前一阶段的状态,由决策所采取的动作,使状态发生转移,成为下一阶段的决策依据
5
2. 最优性原理
无论过程的初始状态和初始决策是什么,其余决策都必须相对于初始决策所产生的状态,构成一个最优决策序列
6
3. 最优决策的形成
令最优状态为 s(2, 22),由此倒推
s(2, 22) p(2, 22) s(1, 2) p(1, 2) s0
最优决策序列: p(2, 22) p(1, 2)
状态转移序列:s0 s(1, 2) s(2, 2)
7
最优决策的形成(续)
1)最优决策在最后阶段形成,然后向前倒推,直到初始
阶段
2)决策的具体结果及所产生的状态转移,由初始阶段开
始进行计算,然后向后递归或迭代,直到最终结果
3)赖以决策的策略或目标,称为动态规划函数
4)动态规划函数可以递归地定义,也可以用递推公式
表达
5)整个决策过程,可以递归地进行,或用循环迭代的方
法进行
8
二动态规划实例、货郎担问题
1. 动态规划解货郎担问题的过程
2. 复杂性分析
9
1. 动态规划解货郎担问题的过程
1)货郎担问题实例:
4城市的费用矩阵
2)动态规划函数:
d(i, V’):从顶点 i 出发,经 V’中各顶点一次,最
终回到初始出发点的最短路径的长度
设初始出发点为 i
10
3)工作过程
由城市 1 出发,经城市 2, 3, 4
然后返回1的最短路径长度为:
①
②
③