文档介绍：动态规划
一、动态规划简介
动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年,美国数学家贝尔曼()提出了解决这类问题的“最优化原则”,1957年发表了他的名著《动态规划》,该书是动态规划方面的第一本著作。动态规划问世以来,在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用,取得了显著的效果。
动态规划运用于信息学竞赛是在90年代初期,它以独特的优点获得了出题者的青睐。此后,它就成为了信息学竞赛中必不可少的一个重要方法,几乎在所有的国内和国际信息学竞赛中,都至少有一道动态规划的题目。所以,掌握好动态规划,是非常重要的。
动态规划是一种方法,是考虑问题的一种途径,而不是一种算法。因此,它不像深度优先和广度优先那样可以提供一套模式。它必须对具体问题进行具体分析。需要丰富的想象力和创造力去建立模型求解。
二、动态规划的几个基本概念
想要掌握好动态规划,首先要明白几个概念:阶段、状态、决策、策略、指标函数。
:把所给问题的过程,恰当地分为若干个相互联系的阶段,以便能按一定的次序去求解。描述阶段的变量称为阶段变量。
:状态表示每个阶段开始所处的自然状况和客观条件,它描述了研究问题过程中的状况,又称不可控因素。
:决策表示当过程处于某一阶段的某个状态时,可以作出不同的决定(或选择),从而确定下一阶段的状态,这种决定称为决策,在最优控制中也称为控制。描述决策的变量,称为决策变量。
:由所有阶段的决策组成的决策函数序列称为全过程策略,简称策略。
:状态转移方程是确定过程由一个状态到另一个状态的演变过程。
:用来衡量所实现过程优劣的一种数量指标,称为指标函数。指标函数的最优值,称为最优值函数。
三、确定动态规划的思路
1、采用动态规划来解决问题,必须符合两个重要的条件。
(1)“过去的历史只能通过当前状态去影响它未来的发展,当前的状态是对以往历史的一个总结”,这种特性称为无后效性,是多阶段决策最优化问题的特征。
(2)作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简言之,一个最优策略的子策略总是最优的。这就是最优化原理。
2、如果碰到一个问题,能够满足以上两个条件的话,那么就可以去进一步考虑如何去设计使用动态规划:
(1)划分阶段。把一个问题划分成为许多阶段来思考
(2)设计合适的状态变量(用以递推的角度)
(3)建立状态转移方程(递推公式)
(4)寻找边界条件(已知的起始条件)
如果以上几个步骤都成功完成的话,我们就可以进行编程了。
四、动态规划解题的一些技巧
由于动态规划并没有一个定式,这就需要去开拓我们创造力去构造并且使用它。以下,通过一些具体的竞赛实例谈谈使用动态规划过程中的一些技巧。
数塔问题:
-8所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一起走到底层,要求找出一条路径,使路径上的值最大。
 
 
                           -8
这道题如果用枚举法,在数塔层数稍大的情况下(如40),则需要列举出的路径条数将是一个非常庞大的数目。
如果用贪心法又往往得不到最优解。
在用动态规划考虑数塔问题时可以自顶向下的分析,自底向上的计算。从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去,直到倒数第二层时就非常明了。如数字2,只要选择它下面较大值的结点19前进就可以了。所以实际求解时,可从底层开始,层层递进,最后得到最大值。
实际求解时应掌握其编程的一般规律,通常需要哪几个关键数组来存储变化过程这一点非常重要。
数塔问题的样例程序如下:
var a:array[1..50,1..50,1..3] of longint;
{第一维记原状态,第二维参与计算,第三维记录决策,0向左,1向右。浪费啊,不如开三个一维,或三元组(指针处理麻烦,类似三角矩阵存储)}
i,j,n:integer;
begin
     write( 'please input the number of rows:');
     readln(n);
     for i:=1 to n do
         for j:=1 to i do {行元素数等于行数}
         begin
              rea