信息学奥赛——动态规划法专题

1、全国青少年信息学奥林匹克联赛动态规划算法一、动态规划的定义在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程(如图)就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在

2、变化的状态中产生出来的，故有"动态"的含义，我们称这种解决多阶段决策最优化的过程为动态规划方法。应指出，动态规划是考察求解多阶段决策问题的一种途径、一种方法，而不是一种特殊算法。不像线性规划那样，具有一个标准的数学表达式和明确定义的一组规划。因此我们在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。二、动态规划最优化原理作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何，对以前的决策所形成的状态而言，余下的诸决策必须构成最优策略。（无论过程的初始状态/初始决策是什么，其余决策活动必须相对于初始

3、决策所产生的状态构成一个最优决策序列，才可能使整个决策活动构成最优决策序列。）简单地说，一个整体过程的最优策略的子策略一定是最优策略。利用这个原理，可以把多阶段决策问题的求解过程看成是一个连续的逆推过程。由后向前逐步推算。在求解时，各种状态前面的状态和决策，对后面的子问题，只不过相当于其初始条件而己，不影晌后面过程的最优策略。原理的证明可用反证法。在此把它略去。三、动态规划的求解方法是先把问题分成多个子问题（一般地每个子问题是互相关联和影响的），再依次研究逐个问题的决策。决策就是某个阶段的状态确定后，从该状态演变到下一阶段状态的选择。当全体子问题都解决时，整体问题也随之解决。用枚举的方法从所有

4、可能的决策序列中去选取最优决策序列可能是较费时的笨拙的方法，但利用最优性原理去找出递推关系，再找最优决策序列就可能使得枚举数量大大下降，这就是动态规划方法设计算法的主要思路。四、动态规划问题的经典实例首先，例举一个典型的且很直观的多阶段决策问题:例 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。如图从A到E共分为4个阶段，即第一阶段从A到B，第二阶段从B到C，第三阶段从C到D，第四阶段从D到E。除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。例如从A到B的第一阶段中，A为起点，终点有B1，B2

5、，B3三个，因而这时走的路线有三个选择，一是走到B1，一是走到B2，一是走到B3。若选择B2的决策，B2就是第一阶段在我们决策之下的结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，对于B2点就有一个可供选择的终点集合(C1，C2，C3)；若选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到各个阶段的决策不同，线路就不同。很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段的影响。故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些

6、决策组成的一个决策序列所决定的一条路线，其总路程最短。如何解决这个问题呢？二、用枚举法把所有由A->E可能的每一条路线的距离算出来，然后互相比较，找出最短者，相应地得出了最短路线。三、用动态规划法求解决策过程：（1）由目标状态E向前推，可以分成四个阶段，即四个子问题。如上图所示。（2）策略：每个阶段到E的最省费用为本阶段的决策路径。（3）D1，D2是第一次输人的结点。他们到E都只有一种费用，在D1框上面标5，D2框上面标2。目前无法定下，那一个点将在全程最优策略的路径上。第二阶段计算中，5，2都应分别参加计算。（4）C1，C2，C3是第二次输入结点，他们到D1，D2各有两种费用。此时应计

7、算C1，C2，C3分别到E的最少费用。C1的决策路径是 min（C1D1），（C1D2）。计算结果是C1+D1+E，在C1框上面标为8。同理C2的决策路径计算结果是C2+D2+E，在C2框上面标为7。同理C3的决策路径计算结果是C3+D2+E，在C3框上面标为12。此时也无法定下第一，二阶段的城市那二个将在整体的最优决策路径上。（5）第三次输入结点为B1，B2，B3，而决策输出结点可能为C1，C2，C3。仿前计算可得Bl，B2，B3的决策路径为如下情况。Bl:B1C1费用 12+8=20， 路径:B1+C1+D1+EB2:B2C1费用 6+8=14， 路径:B2+C1+D1+EB3:B2C2费

8、用 12+7=19， 路径:B3+C2+D2+E此时也无法定下第一，二，三阶段的城市那三个将在整体的最优决策路径上。（6）第四次输入结点为A，决策输出结点可能为B1，B2，B3。同理可得决策路径为A：AB2，费用5+14=19，路径 A+B2+C1+D1+E。此时才正式确定每个子问题的结点中，那一个结点将在最优费用的路径上。19将结果显然这种计算方法，符合最优原理。子问题的决策中，只对同一城市（结点）比较优劣。而同一阶段的城市（结点）的优劣要由下一个阶段去决定。四、小结及比较动态规划的最优化原理是“作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。” 与穷举法相比，动态规划的方法有两个明显的优点:(1)大大减少了计算量(2)丰富了计算结果从上例的求解结果中，我们不仅得到由A点出发到终点E的最短路线及最短距离，而且还得到了从所有各中间点到终点的最短路线及最短距离，这对许多实际问题来讲是很有用的。动态规划的最优化概念是在一定条件下，我到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优。五、应用动态规划要注意1阶段的划分是关键，必须依据题意分析，寻求合理