下载文档原格式
动态规划入门1(2008-09-20 21:40:51)第一节动态规划基本概念一，动态规划三要素：阶段，状态，决策。
他们的概念到处都是，我就不多说了，我只说说我对他们的理解：如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。
显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。
每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。
下面举个例子：要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=||）。
每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。
一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。
经过这个例子相信大家对动态规划有所了解了吧。
下面在说说我对动态规划的另外一个理解：用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。
这样就形成了一个有向无环图AOE网（为什么无环呢？往下看）。
对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。
这样对图求最优路径就是动态规划问题的求解。
二，动态规划的适用范围动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：最优子结构（最优化原理）无后效性最优化原理在下面的最短路径问题中有详细的解答；什么是无后效性呢？就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。
目录１、 动态规划（一） 基础知识２、 动态规划（二） 资源分配类３、 动态规划（三） 合并类型动态规划模型动态规划专题（一）基础知识篇长沙雅礼中学 朱全民一、什么是动态规划近年来，在信息学竞赛中，每次竞赛几乎都有涉及运用动态规划解题的试题，动态规划问题已越来越受到出题者的青昧。
那么，什么是动态规划呢?在了解动态规划之前，我们先来看一道简单题。
例１如下图是一个带权的有向分层网络图，如果要求点A到点D的最短路径，怎么求呢？首先，我们看这里共有４条路径：AÆB1 Æ C1 Æ D，A Æ B1 Æ C2 Æ D，A Æ B2 ÆC2 Æ D，A Æ B2 Æ C3 Æ D它们的长度分别为：5+3+4＝12，5+2+3＝10，2+7+3＝12，2+4+5＝11。
方法1：如果采用枚举算法，枚举4条路径，然后比较每条路径的长度，得出最优解10，路径为A Æ B1 Æ C2 Æ D。
方法2：如果我们采用分层递推的思想来做这个题，会出现什么效果呢?我们设G[i]为点i到点D的距离，显然G[C1]=4，G[C2]=3，G[C3]=5，根据上面的分析，有：G[B1]=min{G[C1]+3，G[C2]+2}=5，G[B2]=min{G[C2]+7，G[C3]+4}=9，再就有：G[A]=min{G[B1]+5，G[B2]+2}=10，所以A到D的最短距离是10，最短路径是A Æ B1 Æ C2 Æ D。
分析：方法1采用枚举法对于边A-B1，A-B2，C2-D都计算了2次；而方法2采用逐层递推的方法，每条边都只计算了1次，因此，方法2要比方法1优秀。
那么造成两种方法效率不同的根本原因是什么呢? 从例1可以看出，方法2采用的逐层递推的方法从根本上消除了枚举法对路径过程中部分重复路径的冗余运算。
像上面先把一个问题递归地分解成若干与之类似的子问题，再从这些子问题的解中递推回去以得到原问题的解，就是动态规划。
动态规划是运筹学的一个分支。
它是解决多阶段决策过程最优化问题的一种方法。
1951年，美国数学家贝尔曼(R．Bellman)提出了解决这类问题的“最优化原则”；1957年发表了他的名著《动态规划》，该书是动态规划方面的第一本著作。
动态规划问世以来，在工农业生产、经济、军事、工程技术等方面都得到了广泛的应用，取得了显著的效果。
下面我们来熟悉一些动态规划的基本概念。
1．状态与状态的特征我们把每个子问题的中间解称为一个状态，例如例1中的G[A]、G[Bl]、G[C3]等就是不同的状态。
状态的特征是指影响问题目标的一个或几个因素，我们根据这些因素来区分不同的状态。
例1中的状态的特征就是顶点的序号，根据序号我们才能把C[A]、G[B1]和G[C3]这些状态区分开。
2．决策与策略在递推的过程中，我们要做出一些取舍(选择)，以决定如何从已知的状态推知未知的状态，对于特定状态的选择就被叫做决策。
如例1中，在决定C[A]的值时，取G[Bl]+5而舍G[B2]+2，就是一个明智的决策。
由一连串的决策所构成的序列称为策略，能够得到满足要求的解的策略就称为最优策略。
如例1中的最优策略就是选择A Æ B1 Æ C2 Æ D作为最短路径上的点。
3．规划方向与阶段因为所有状态在整个解题过程中的地位和作用并不完全相同，所以每个问题的解决必须依照一定的次序。
如例1中，G[B1]与G[B2]的地位是相同的，所以哪个先求解都没有关系；而G[A]与G[B1]处在不同的地位，因此G[(B1]必须在C(A]之前求解。
我们把这种解题的次序称为规划方向，把地位相同的状态称为一个阶段。
可以看出，例1的规划方向是从后向前的：由C到B，再到A；阶段A由C[A]独立构成，而阶段B 包括G[Bl]和G[B2]，阶段C包括G[C1]、G[C2]和G[C3]。
4．边界在实践中，问题一般包含多个阶段才有讨论的意义，问题的最初的阶段，我们就称为边界。
边界必须在递推之前根据题意人为给定，它是递推的基础。
这就像是在运用数学归纳法证明命题的正确性，首先要证明命题在n=n0时是成立的，接下来才能证明在n>n0时命题也是成立的，因为前者是后者的基础。
在例1中，阶段C就是边界，所以我们一开始便根据C1，C2，C3到D点的距离给G[Cl]，G[C2]和G[C3]赋了值。
5．状态转移方程我们知道，除边界外的任一阶段都得由其前面的阶段递推得到，这递推的过程就表现出了阶段的动态演变。
这种根据已有状态求得未知状态的过程，我们称之为状态转移，状态转移的规则用数学语言来描述，就称为状态转移方程。
状态转移方程的形式多样，如例1中的形式为G[i]=min{G[j]+e(i,j)}，e(i,j)∈E。
6．表上操作动态规划一个显著的特点就是“表上操作”。
也就是说，动态规划把所有的状态都保存在了一张表格之中，这表格称为状态变量，如例子中的G。
状态变量可以是一维、二维，也可以是三维、四维，这就要由阶段的划分和状态的特征来决定。
二、动态规划的基本原理运用动态规划解题往往编程简单，但效率很高，如何使用动态规划，它的核心实质上是对问题进行状态的设计和阶段的划分。
那么阶段的划分和状态描述能否符合动态规划的解题原理，是解决问题的根本所在。
1. 无后效性对于每个阶段的状态而言，如果确定了某一阶段的状态后，则在这一阶段以后过程的发展不再受这阶段以前各段状态的影响。
在例1中，要求G(A)的最优值，只会跟G(Bi)的最优值有关，而跟G(Ci)的各个状态无关。
换句话说，每个状态都是“过去历史的一个完整总结”。
这就是无后效性。
例2 多米诺骨牌有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。
例如，现有一行骨牌排列在桌面上，如下图：顶行骨牌的点数之和为6+1+1+1=9，底行骨牌点数之和为1+5+3+2=11。
顶行和底行的差值是2。
这个差值是两行点数之和的差的绝对值。
每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。
现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。
对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。
[分析]因为各骨牌的翻转顺序没有限定，因此，如果我们按例1的方法进行阶段划分，可以看出决策不具有无后效性，前面的骨牌翻转次数与后面骨牌是否翻转的最优性没有必然联系。
因此不能按骨牌编号作为阶段来划分。
怎么办呢?考虑到骨牌差值与骨牌翻转次数的关系，因此我们可以骨牌的差值来划分阶段，将最初骨牌序列上下两部分的差值I作为初始状态，把是否翻转某张骨牌作为决策，设f(i)表示骨牌差值为i时的最少翻转次数，于是有，F(i)=min{f(i+2*j)+1} 其中，-6≤j≤6，j为翻转点数差值为j的骨牌。
本题样例，f(-2)=0，由该初始状态可递推出其他差值的状态。
[注意]每个骨牌最多翻一次，在计算各状态差值时，除记录最少步数外，还需记录到达这一状态时各骨牌的放置情况，直到计算每个骨牌都已翻转或达到差值最小为止。
2．最优性原理对于每个阶段的决策而言，无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。
这就是最优化原理。
简言之，就是“最优策略的子策略也是最优策略”。
[例3] mod 4最优路径问题在下图中找出从第1点到第4点的一条路径，要求路径长度mod4的余数最小。
这个图是一个多段图，而且是一个特殊的多段图。
虽然这个图的形式比一般的多段图要简单，但是这个最优路径问题却不能用类似例1的分阶段形式来进行动态规划。
因为一条从第1点到第4点的最优路径，在它走到第2点、第3点时，路径长度mod 4的余数不一定是最小，也就是说最优策略的子策略不一定最优——这个问题不满足最优化原理。
但是我们可以把它转换成判定性问题，用递推法来解决。
判断从第1点到第k点的长度mod 4为Sk的路径是否存在，用fk(Sk)来表示，则递推公式如下：True (s1=0)F1(s1)= (边界条件)Flase (s1=1,2,3)F k-1(s k-len k,1) mod 4)F k(s k)= F k-1((s k-len k,2) mod 4)F k-1((s k-len k,3) mod 4)这里len k,i表示从第k-1点到第k点之间的第i条边的长度，方括号表示或运算，这里S k=0,1,2,3。
这个递推法的递推公式和动态规划的规划方程非常相似，我们在这里借用了动态规划的符号也就是为了更清楚地显示这一点。
其实它们的思想也是非常相像的，可以说是递推法借用了动态规划的思想解决了动态规划不能解决的问题。
有的多阶段决策问题(像这一题的阶段特征就很明显)，由于不能满足最优化原理等使用动态规划的先决条件，而无法应用动态规划。
在这时可以将最优指标函数的值当做“状态”放到下标中去，从而变最优化问题为判定性问题，再借用动态规划的思想，用递推法来解决问题。
三、动态规划的基本运用[例4]机器分配总公司拥有高效生产设备M台，准备分给下属的N个公司。
各分公司若获得这些设备，可以为国家提供一定的盈利。
问：如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。
其中M<=100，N<=100。
分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。
保存数据的文件名从键盘输入。
数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。
接下来是一个N*M的矩阵，其中，第1行第J个数表明第1个公司分配J台机器的盈利。
[分析]这是一个资源分配问题，如果我们采用搜索或枚举的方法，每个公司都能分配0-m 台机器，因此时间复杂度将达到O(n m+1)，显然时间复杂度巨大。
那么我们是否能用动态规划来解决呢?设F(i，j)表示前i个公司分配了j台机器的所获得的最大盈利。
则状态转移方程为：F(i,j)=Max(F(i-1,k) + value[i,j-k]) (0≤k≤j≤m，1≤i≤n)F(i,0)=0时间复杂度0(nm2)。
[参考程序1／pascal语言]program mechine;varvalue,f : array[0..100,0..100] of longint;n,m : integer;procedure init;vari,j : integer;beginassign(input,'input.txt'); reset(input);readln(m,n);for i:=1 to n dobeginfor j:=1 to m doread(value[i,j]);readln;end;close(input);end;dynamic; //动态规划procedurevari,j,k : integer;beginassign(output,'output.txt'); rewrite(output);for i:=1 to n do //枚举阶段ifor j:=0 to m do //枚举决策变量jfor k:=0 to j do //枚举决策变量kif f[i-1,k]+value[i,j-k]>f[i,j] then //决策转移条件f[i,j]:=f[i-1,k]+value[i,j-k]; //更新最优值writeln(f[n,m]);close(output);end;begininit;dynamicend.总结：可以看出，采用动态规划解题，程序非常简单，当然上题F(i,j)只与F(i-1,k)有关，因此可以采用滚动数组（一维数组）存储每个阶段的状态。
