算法 第四章 动态规划.ppt

2017-2-23 1第四章动态规划 2017-2-23 2第四章动态规划 一般方法 1. 多阶段决策问题多阶段决策过程:问题的活动过程分为若干相互联系的阶段,任一阶段 i以后的行为仅依赖于 i阶段的过程状态,而与 i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策,这一系列的决策称为多阶段决策过程(multistep decision process) 。最优化问题:问题的每一阶段可能有多种可供选择的决策,必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同,所导致的问题的结果可能不同。多阶段决策的最优化问题就是:求能够获得问题最优解的决策序列——最优决策序列。 2017-2-23 3 2. 多阶段决策过程的求解策略 1)枚举法穷举可能的决策序列,从中选取可以获得最优解的决策序列 2)动态规划 20 世纪 50 年代初美国数学家 . Bellman 等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理(principle of optimality) ,把多阶段过程转化为一系列单阶段问题,创立了解决这类过程优化问题的新方法——动态规划。动态规划(dynamic programming) 是运筹学的一个分支,是求解决策过程(decision process) 最优化的数学方法。应用领域:动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。 2017-2-23 4 3. 最优性原理(Principle of Optimality) 过程的最优决策序列具有如下性质:无论过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。对于一个多阶段过程问题,上述最优决策是否存在依赖于该问题是否有最优子结构性质:原问题的最优解包含了其子问题的最优解。而能否采用动态规划的方法还要看该问题的子问题是否具有重叠性质。问题的子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。子问题重叠性质:在求解具有最优子结构的问题时,每次产生的子问题并不总是新问题,有些问题被反复计算多次。 2017-2-23 5 利用动态规划求解问题的前提 1) 证明问题满足最优性原理如果对所求解问题证明满足最优性原理,则说明用动态规划方法有可能解决该问题 2) 获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。 2017-2-23 6 例 [ 多段图问题]多段图 G=(V,E) 是一个有向图,且具有特性: 结点:结点集 V被分成 k≥2个不相交的集合 V i,1≤i≤k, 其中 V 1和V k分别只有一个结点 s(源结点)和t(汇点)。·每一集合 V i定义图中的一段。边:所有的边(u,v) 均具有如下性质: 若<u,v> ∈E,则该边将是从某段 i指向 i+1 段,即若 u∈V i,则v∈V i+1, 1 ≤i≤k-1。·每条边(u,v) 均附有成本 c(u,v) 。 s到t的路径:从第 1段开始,至第 2段、第 3段、…、最后在第 k段终止。路径的成本是这条路径上边的成本和。多段图问题:求由 s到t的最小成本路径。 2017-2-23 7 1 2345 678 9 10 11 12 9732 4227 11 118 1 4 5 6356 425 V 1V 2V 3V 4V 55段图 2017-2-23 8 多段图问题的多阶段决策过程:生成从 s到t的最小成本路径是在 k-2 个阶段(除 s和t外)进行某种决策的过程:从 s开始, 第i 次决策决定 V i+1 (1≤i≤ k-2) 中的哪个结点在从 s到t的最短路径上。最优性原理对多段图问题成立假设 s,v 2 ,v 3,…,v k-1 ,t是一条由 s到t的最短路径。●初始状态:s●初始决策: (s,v 2),v 2∈V 2●初始决策产生的状态:v 2则,其余的决策: v 3 ,...,v k-1相对于 v 2将构成一个最优决策序列——最优性原理成立。反证:若不然,设 v 2 ,q 3,…,q k-1 ,t是一条由 v 2到t的更短的路径, 则 s, v 2 ,q 3,…,q k-1 ,t将是比 s,v 2 ,v 3,…,v k-1 ,t更短的从 s到t的路径。与假设矛盾。故,最优性原理成立 2017-2-23 9 ?例 [0/1 背包问题] KNAP(1,j,X) 目标函数: 约束条件: 0/1 背包问题: KNAP(1,n,M) ???ji iixp 1jiwpx Xxw iii ji ii?????????1,0,0,10