动态规划入门(论文)研讨.doc

动态规划思想入门作者:陈喻( 2008 年 10月7 日) 关键字:动态规划,最优子结构,记忆化搜索引言动态规划(dynamic programming) 是运筹学的一个分支,是求解决策过程(decisionprocess) 最优化的数学方法。 20 世纪 50 年代初美国数学家 等人在研究多阶段决策过程(multistep decision process) 的优化问题时, 提出了著名的最优化原理(principle of optimality) , 把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。 1957 年出版了他的名著 Dynamic Programming ,这是该领域的第一本著作。动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。动态规划的基本思想动态规划是:将待求的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它直接求解,并把答案保存起来,让以后再次遇到是直接引用答案,不必从新求解,其实质是分治思想和解决冗余。例1:求 A—>B 的最短路径图 1 这是一个利用动态规划思想的经典问题,通过直接观察图 1我们可以枚举出 20多条路径,并可以计算出其中最短的路径长度为 16 用动态规划的思想来分析,我们可以把这个问题转换成下面这个模型图 2 阶段:根据问题的特点和需要,将问题按时间或空间特征分解为若干相互联系的阶段。在本例中,我们根据空间特性将问题分成了 6个阶段。状态:各阶段的开始条件,本例中, A,B,C …… P这些节点都属于状态,表示从该点到 B的最短路径,在这里我们计做 S(i) ,表示从第 i个节点(状态)到 B的最短路径决策:某阶段状态确定后,从该状态到下阶段某状态的选择。比如 S(A) ,它可以选择通过 C到达 B,也可以选择通过 D到达 B。状态转移方程:系统由某阶段的一个状态转变到下一阶段的另一状态称状态转移,体现转移规律的方程称状态转移方程。在本例中,我们不难推出 S(A ) =MIN{S(C)+4,S(D)+3},S(C)=MIN{S(E)+5,S(F)+3} ………… S(B)=0 ,由此我们可以得出状态转移方程S (i)=MIN{S(j)+Vij}(j 为与 i相邻接的节点, Vij 表示邻接状态决策阶段节点 i,j之间的距离)。一个动态规划模型应该满足以下几个性质: 1. 最优子结构性质最优子结构可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之, 一个最优化策略的子策略总是最优的。例如在图 2的模型中, S(A) 是 A到 B的最短路径(最优策略),而它所依赖的 S(C) 和 S(D) 作为 S(A) 的子策略分别是 C到B的最短路径和 D到B的最短路径,也是最优的。因此根据最优子结构性质我们得出了上面的状态转移方程。证明:如图 2设路线 W1={(A,C),(C,F),(F,J)} W2={(J,M),(M,O),(O,B)} 若路线 W1 和 W2 是A到B的最优路径,则根据最优化原理,路线 W2 必是从 J 到 B的最优路线。用反证法证明:假设有另一路径 W2 '是 J到 B的最优路径, 则A到B的路线取 W1 和 W2 '比 W1 和 W2 更优,矛盾。从而证明 W2 '必是 J 到B的最优路径 W2 。最优子结构性质是动态规划的基础,任何问题,如果失去了最优子结构性质的支持,就不可能用动态规划方法计算。根据最优子结构性质导出的动态规划状态转移方程是解决一切动态规划问题的基本方法。可以看出, 图2的模型是满足最优子结构性质的。 ,每次产生的子问题并不总是新的,而且某些子问题会被重复计算多次,比如,在求 S( C)时需要递归求出 S(F)的值,而在求 S(D)时也需要递归求出 S(F)的值,因此整个求解过程中 S(F)的值会被求解两次,如果我们能把这多余的一次重复计算剔除,将可以最大程度的提高程序执行效率;动态规划正是利用了这种子问题的重叠性质,对每个子问题只计算一次,然后将其结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单的