上海大学运筹学动态规划课件.pdf

第五章 动态规划 Dynamic Programming，DP 顺序决策问题 最短路问题 动态规划的基本概念、基本原理 应用举例 资源分配问题 市场营销问题 背包问题 生产库存问题…………… 2009-11-5 1 5.1 引论 动态规划研究的问题顺序决策 问题: 可以在时间或空间上划分为若 干阶段 单独看每个阶段，也是一个优化问题。 注意：之前学过的知识与动态规划的结合 2009-11-5 2 引例 最短路径问题 12 B1 C1 3 14 9 2 10 D 1 5 6 6 A 5 B2 10 C2 E 5 4 2 D 1 13 8 2 12 10 B3 C3 11 求从A到E 的最短路径 2009-11-5 3 设 s ：第k阶段初所处的结点 k x (s ) ：在s 状态时第k阶段所作的决定 k k k d(s x ) ：第k阶段，采取策略x 所发生的距离 k ， k k f (s )：第k阶段，在s 状态时到终点E的最短距离 k k k 2009-11-5 4 12 B1 C1 3 14 9