动态规划基础篇

1579452039368前言动态规划算法在近几年的各级信息学奥林匹克竞赛中代替了搜索算法的统治地位，成为要想在信息学竞赛中取得好成绩必须掌握的一种算法。然而很多同学学习动态规划时，被它复杂的算法定义以及表示方法弄的晕头转向，不知所以，即便勉强掌握，往往一遇到复杂一点的动态规划，又不知如何下手分析出正确的结果。为了使同学们能熟练、透彻地掌握这种算法。我们通过动态规划准备篇、基础篇、中级篇和高级篇共四篇文章来进行一个系统地讲解。希望能对同学们的学习有所帮助。动态规划基础篇一、动态规划的算法思想（1-1）引例1：现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图所示，试找出从结点1到结点10的最短路径。解法一：本问题的解决可采用一般的穷举法，即把从结点1至结点10的所有道路列举出来，计算其长度，再进行比较，找出最小的一条。虽然问题能解决，但采用这种方法，当结点数增加，其运算量将成指数级增长，故而效率是很低的。解法二：分析上图可知，各结点的排列特征：（1）可将各结点分为5个阶段；（2）每个阶段上的结点只跟相邻阶段的结点相连，不会出现跨阶段或同阶段结点相连的情况，如不会出现结点1与结点4连、结点4与结点5连的情况。（3）除起点1和终点10外，其它各阶段的结点既是上一阶段的终点，又是下一阶段的起点。例如第三阶段的结点4、5、6，它即是上一阶段结点2、3中某结点的终点，又是下一阶段结点7、8、9中某结点的起点。所以根据分析划分若干个阶段（如图）第一阶段第二阶段第三阶段第四阶段第五阶段划分阶段后我们思考从结点10向结点1逆向来推导：即第五阶段由第四阶段推出，第四阶段由第三阶段推出，…，第二阶段由第一阶段推出。具体的每阶段的推出又时相同的：每个阶段的点与起始点的距离等于与其上一阶段相连的所有点与起始点的距离加上与上一阶段相连的所有点的两点的距离的最小值。15794520393681234567891011122132142152此话念起来相当拗口，但是理解起来并不难。举例：我们设f(n)表示最短路径，d(a,b)表示结点a到结点b的两点距离。f(10)=min{f(7)+d(10,7),f(8)+d(10,8),f(9)+d(10,9)};f(9)=min{f(4)+d(9,4)};f(8)=min{f(5)+d(8,5),f(6)+d(8,6)};f(7)=min{f(5)+d(7,5)};f(6)=min{f(3)+d(6,3)};f(5)=min{f(3)+d(5,3),f(4)+d(5,4)};f(4)=min{f(3)+d(4,3),f(2)+d(4,2)};f(3)=min{f(1)+d(3,1)};f(2)=min{f(1)+d(2,1)};f(1)=0。我们在对其中的某个点具体分析，如第三阶段的结点5，可选择1-2-5和1-3-5这两条路径，后者的费用要小于前者。那么考虑一下，假设在所求的结点1到结点10最短路径中要经过结点5，那我们在结点1到结点5之间会取那条路径呢？显然，无论从结点5出发以后的走法如何，前面选择1-3-5这条路都总是会优于1-2-5的。也就是说，当某阶段结点一定时，后面各阶段路线的发展不受这点以前各阶段中的点（如2，3）的影响。反之，到该点的最优决策也不受该点以后各点的发展影响。现在我们计算最短路径时，该正向思考了，从阶段1开始，往后依次求出结点1到阶段2、3、4、5各结点的最短距离，最终得出答案。在计算过程中，到某阶段上一结点的决策，只依赖于上一阶段的计算结果，与其它无关。例如，已求得从结点1到结点5的最优值是6，到结点6的最优值是5，那么要求到下一阶段的结点8的最优值，只须比较min{6+5,5+5}即可。（1-2）引例2：数字三角形，在下图中求从顶至低某处的一条路径，使该路径所经过的数字的总和最大。（1）每一步可任意走但不能跳跃下一行（2）每一步只能向左下或右下走也不能不能跳跃下一行。738810274445265解：对于第一问很简单，将每行的最大值找出来，再连起来就可以了。这是贪心算法，也可写成一个递推公式：n表示行数，max(n)表示第n行的最大值，sum(n)=sum(n-1)+max(n);sum(1)=max(1)；对于第二问可不可以用贪心算法呢？答案是否定的。首先贪心有两种，一种是从顶端向左下或右下的两个选择中选择最大的一个。一种是选择整个数中最大的，从顶端向这个最大数方向前进。首先这两种贪心都不能保证数字之和最大，反例请同学们自己给出。其次这两种贪心并不能同时使用，绝大多数二者取其一，所以两种贪心都不算是真正的贪心。那么如何思考呢？其实很简单，我们将每个位置编上号，并且将所有的路线连上。如图所示，看一看，与上面的多段图是不是类似。所以我们也完全利用上例的解题思路来解决本题。首先我们设data(i,j)为(i,j)位置的数据，sum(i,j)为到达该点的最大数字和。有如下公式：在n行数字三角形中sum(i,j)=max{sum(i+1,j),sum(i+1,j+1)}+data(i,j);(in)sum(n,j)=data(n,j);(i=n)以例中给出的实例得出：sum(1,1)=max{sum(2,1),sum(2,2)}+7;1579452039368sum(2,1)=max{sum(3,1),sum(3,2)}+3;sum(2,2)=max{sum(3,2),sum(3,3)}+8sum(3,1)=max{sum(4,1),sum(4,2)}+8sum(3,2)=max{sum(4,2),sum(4,3)}+1sum(3,3)=max{sum(4,3),sum(4,4)}+0sum(4,1)=max{sum(5,1),sum(5,2)}+2sum(4,2)=max{sum(5,2),sum(5,3)}+7sum(4,3)=max{sum(5,3),sum(5,4)}+4sum(4,4)=max{sum(5,4),sum(5,5)}+4sum(5,1)=4sum(5,2)=5sum(5,3)=2sum(5,4)=6sum(5,5)=5有经验的同学在编程时可利用逆推来求出最大数字和，而不用递归实现程序。二、动态规划中的主要概念有了上面两个实例，我们理解一下动态规划所设计的一些理论性的内容。（2-1）阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,..,n表示。引例1中阶段是点与点的关系划分的，引例2明显是行划分，后面我们也会设计到按时间划分。从阶段的定义中，还可以看出阶段的两个特点，一是段与段“相互联系”，二是阶段之间的“次序”。阶段之间是怎样相互联系的？就是通过状态和状态转移。（2-2）状态、状态变量、状态转移我们在宽搜时接触过状态，由一个初始状态到一个目标状态，而且其间存在若干个中间（过渡）状态。在动态规划中也有状态的描述，其核心含义是一样的。状态表示事物的性质，它包括各阶段开始时的客观条件和所处的自然状况，是描述“动态规划”中的“单元”的量。这个描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表示。注意不要将这个“变量”与pascal中的变量混淆，这个“变量”的表示范围要比pascal的变量要大的多。也可理解为你要确定一个数据结构来表示状态。状态是阶段的属性，每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。即当前处于哪一个阶段的哪一个状态。在引例1中，出发点①走过两个阶段之后，可能出现的情况有三种，即处于⑦、⑧或⑨点。那么第三个阶段就有三个状态S4={⑦,⑧,⑨}。每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移。上例中⑧点可以从⑤点过来，也可以从⑥点过来，从阶段3的⑤或⑥状态走到阶段4的⑧状态就是状态转移。状态转移是导出状态的途径，也是联系各阶段的途径。（2-3）状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态的方程，是改变状态所需要的计算公式，是“动态规划”的中心。它与递推关系式的表达方式近似，后面我们还要讲到。（2-4）决策、决策变量、策略、最优策略引入决策的原因：无后效性。对于某个给定的阶段的状态，它以前各阶段的状态无法直接影响它未来的发展，而只能通过当前的这个状态。换句话说，每个状态都是“过去历史的一个完整总结”。这也就意味着状态本身不能通过自己转移到下一个阶段的某个状态，或者说所在解决整个问题时没有一个固定不变的公式使一个阶段某个状态转移到另一个阶段的某个状态。这一点与产生式系统是1579452039368不一样的。在产生式系统中一旦找出产生式规则，这个规则在所有的状态转化中都适用。所以我们当各个阶段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种不同的决定称为决策。如图：表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。显然有uk(sk)Dk(sk)。决策是问题的解的属性。决策的目的就是“确定下一阶段的状态”，还是回到上例，从阶段3的⑤状态出发有两条路，也就是两个决策，分别导向阶段4的⑦、⑧两个状态，即D3(⑤)={⑦,⑧}。有了决策的定义，我们知道动态规划中本阶段的状态往往是上一阶段和上一阶段的决策结果，由第k段的状态sk和本阶段的决策uk共同确定第k+1段的状态sk+1的过程叫状态转移。状态转移规律的形式化表示sk+1=Tk(sk,uk)称为状态转移方程。如上面引例中的各个推导公式。策略是某些决策的集合，在我们解决问题的时候，我们将一系列决策记录下来，就是一个策略，其中满足某些最优条件的策略称之为最优策略。三、动态规划的充分必要条件（3-1）无后效性在上边的决策讲解中已经解释了，这里不详细解释了。我们只来看一个具体例子：例：如图欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的游历路线问题。图5(a)给出了七个点问题的解。Bitonic旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。图（b）给出了七个点问题的解。这两个问题看起来很相似。但实质上是不同的。为了方便讨论，我将每个顶点标记了号码。由于必然经过最右边的顶点7，所以一条路(P1—P2)可以看成两条路（P1—7）与(P2—7)的结合。所以，这个题目的状态可以用两条道路结合的形式表示。我们可以把这些状态中，两条路中起始顶点相同的状态归于一个阶段，设为阶段[P1,P2]。那么，对于Bitonic旅行路线问题来说，阶段[P1,P2]如果可以由阶段[Q1,Q2]推出，则必须满足的条件就是:P1Q1或P2Q2。例如，阶段[3,4]中的道路可以由阶段[3,5]中的道路加一条边4－5得出，而阶段[3,5]的状态却无法由阶段[3,4]中的状态得出，因为Bitonic旅行路线要求必须严格地由左到右来旅行。所以如果我们已经知道了阶段[3,4]中的状态，则阶段[3,5]1579452039368中的状态必然已知。因此我们可以说，Bitonic问题满足“无后效性原则”，可以用“动态规划”算法来解决。对于欧几里德货郎担问题,阶段与阶段之间没有什么必然的“顺序”。如道路{3－2－5－7,4－6－7}属于阶段[3,4]，可由属于阶段[2,4]的道路{2－5－7，4－6－7}推出；而道路{2－3－6－7，4－5－7}属于阶段[2,4]，可由属于阶段[3,4]的道路{3－6－7，4－5－7}推出。如果以顶点表示阶段，推出关系表示边，那么，阶段[3,4]与阶段[2,4]对应的关系就如图6所示。我们可以很清晰地看出，这两个阶