日志

思考问题的一种途径------动态规划

已有 936 次阅读2014-8-4 00:17 |系统分类:知识| 表达式, 创造性, 想象力, 动态, 技巧

----备忘------

动态规划（dynamic programming）是运筹学的一个分支，主要是求解决策过程（decision process）最优化的数学方法。

动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。

动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

动态规划的主要缺点是：

（i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。

（ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有m个取值，那么对于n维问题，状态xk 就有m的n次方个值，对于每个状态值都要计算、存储函数

，对于n稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。

动态规划最优化原理：

作为整个过程的最优策略具有这样的性质: 无论过去的状态和决策如何，对以前的决策所形成的状态而言，余下的诸决策必须构成最优策略。（无论过程的初始状态/初始决策是什么，其余决策活动必须相对于初始决策所产生的状态构成一个最优决策序列，才可能使整个决策活动构成最优决策序列。）
简单地说，一个整体过程的最优策略的子策略一定是最优策略。
利用这个原理，可以把多阶段决策问题的求解过程看成是一个连续的逆推过程。由后向前逐步推算。在求解时，各种状态前面的状态和决策，对后面的子问题，只不过相当于其初始条件而己，不影晌后面过程的最优策略。原理的证明可用反证法。

动态规划问题的特征：
动态规划算法的有效性依赖于问题本身所具有的两个重要性质：
1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

分析问题的基本步骤（抽象）：

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

图1 动态规划决策过程示意图

(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

实际应用中可以按以下几个简化的步骤进行设计：

（1）分析最优解的性质，并刻画其结构特征。

（2）递归的定义最优解。