文档介绍：最优化原理
,根据一类多阶段问题的特点,把多阶
段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。一些静
态模型,只要人为地引进“时间”因素,分成时段,就可以转化成多阶段的动
态模型,用动态规划方法去处理。与此同时,他提出了解决这类问题的“最优
化原理”(Principle of optimality):
“一个过程的最优决策具有这样的性质:即无论其初始状态和初始决策如
何,其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言,必
须构成最优策略”。简言之,一个最优策略的子策略,对于它的初态和终态而
言也必是最优的。
这个“最优化原理”如果用数学化一点的语言来描述的话,就是:假设为
了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序
列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以
后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,
Dk+2,…,Dn也是最优的。
最优化原理是动态规划的基础。任何一个问题,如果失去了这个最优化原
理的支持,就不可能用动态规划方法计算。能采用动态规划求解的问题都需要
满足一定的条件:
(1) 问题中的状态必须满足最优化原理;
(2) 问题中的状态必须满足无后效性。
所谓的无后效性是指:“下一时刻的状态只与当前状态有关,而和当前状
态之前的状态无关,当前的状态是对以往决策的总结”。
问题求解模式
动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通
过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同
时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示
。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
图1 动态规划决策过程示意图
(1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划
分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无
法求解。
(2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况
用不同的状态表示出来。当然,状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,
状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定
了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两段
各状态之间的关系来确定决策。
(4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终
止条件或边界条件。
算法实现
动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦
设计完成,实现部分就会非常简单。使用动态规划求解问题,最重要的就是确
定动态规划三要素:问题的阶段,每个阶段的状态以及从前一个阶段转化到后一
个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大的问题之间
的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递
推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题
来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。确定了动态
规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表
是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数
据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共
子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行
或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍
或者运算求得问题的最优解。下面分别以求解最大化投资回报问题和最长公共
子序列问题为例阐述用动态规划算法求解问题的一般思路
动态规划
在数学与计算机科学领域,动态规划用于解决那些可分解为重复子问题(overlapping subproblems,想想递归求阶乘吧)并具有最优子结构(optimal substructure,想想最短路径算法)(如下所述)的问题,动态规划比通常算法花费更少时间。
上世纪40年代,Richard Bellman最早使用动态规划这一概念表述通过遍历寻找最优决策解问题的求解过程。1953年,Richard Bellman将动态规划赋予现代意义,该领域被IEEE纳入系统分析和工程中。为纪念Bellman的贡献,动态规划的核心方程被命名为贝尔曼方程,该方程以递归形式重申了一个优化问题。
在“动态规划”(dynamic pr