经典算法——动态规划教程.doc

动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的没计法对不同的问题，有各具特色的表示方式。不存在一种万能的动态规划算法。但是可以通过对若干有代表性的问题的动态规划算法进行讨论，学会这一设计方法。多阶段决策过程最优化问题动态规划的基本模型 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。【例题1】最短路径问题。图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少? 【分析】把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路。用dk(xk，xk+1)表示在第k阶段由初始状态xk到下阶段的初始状态xk+1的路径距离，Fk(xk)表示从第k阶段的xk到终点E的最短距离，利用倒推方法求解A到E的最短距离。具体计算过程如下： S1：K=4，有：F4(D1)=3，F4(D2)=4，F4(D3)=3 S2: K=3，有：F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)=min8,10=8 F3(C2)=d3(C2,D1)+f4(D1)=5+3=8 F3(C3)=d3(C3,D3)+f4(D3)=8+3=11 F3(C4)=d3(C4,D3)+f4(D3)=3+3=6 S2: K=2，有：F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+f3(C2),d2(B1,C3)+F3(C3)=min9,12,14=9 F2(m)=mind2(B2,c2)+f3(C2),d2(B2,C4)+F3(C4)=min16,10=10 S4：k=1，有：F1(A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2)=min13,13=13因此由A点到E点的全过程的最短路径为AB2一C4D3E。最短路程长度为13。从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到过程终点E的最短路径和最短距离，当逆序倒推到过程起点A时，便得到了全过程的最短路径及最短距离，同时附带得到了一组最优结果(即各阶段的各状态到终点E的最优结果)。 在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。根据上例分析和动态规划的基本概念，可以得到动态规划的基本模型如下：(1)确定问题的决策对象。(2)对决策过程划分阶段。(3)对各阶段确定状态变量。(4)根据状态变量确定费用函数和目标函数。(5)建立各阶段状态变量的转移过程，确定状态转移方程。动态规划的基本知识动态规划是研究一类最优化问题的方法，在经济、工程技术、企业管理、工农业生产及军事等领域中都有广泛的应用。近年来，在ACM/ICPC中，使用动态规划(或部分应用动态规划思维)求解的题不仅常见，而且形式也多种多样。而在与此相近的各类信息学竞赛中，应用动态规划解题已经成为一种趋势，这和动态规划的优势不无关系。1、动态规划的常用名词在学习动态规划之前，先得对下面的名词有所了解。本书将标准名词作了一些简化，便于大家更好的理解。(1)状态(smte)对于一个问题，所有可能到达的情况(包括初始情况和目标情况)都称为这个问题的一个状态。(2)状态变量(sk)对每个状态k关联一个状态变量sk，它的值表示状态k所对应的问题的当前解值。(3)决策(decision)决策是一种选择，对于每一个状态而言，你都可以选择某一种路线或方法，从而到达下一个状态。(4)决策变量(dk)在状态k下的决策变量dk的值表示对状态k当前所做出的决策。(5)策略策略是一个决策的集合，在我们解决问题的时候，我们将一系列决策记录下来，就是一个策略，其中满足某些最优条件的策略称之为最优策略。(6)状态转移函数(t)从一个状态到另一个状态，可以依据一定的规则来前进。我们用一个函数t来描述这样的规则，它将状态i和决策变量di映射到另一个状态j，记为t(i，di)=j(7)状态转移方程(f)状态转移方程f描述了状态变量之间的数学关系。一般来说，与最优化问题相应，状态转移方程表示si的值最优化的条件，或者说是状态i所对应问题的最优解值的计算公式，用代数式表示就是：si=f(sj,dj)|i=t(j,dj)，对决策变量dj所有可行的取值)2、最优化原理1951年美国数学家RBellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。一些静态模型，只要人为地引进“时间”因素，分成时段，就可以转化成多阶段的动态模型，用动态规划方法去处理。与此同时，他提出了解决这类问题的“最优化原理”(Principleofoptimality)：“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。简言之，一个最优策略的子策略，对于它的初态和终态而言也必是最优的。这个“最优化原理”如果用数学化一点的语言来描述的话，就是：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 k n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，Dn也是最优的。最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。3、什么是动态规划动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。许多隐式图上的算法，例如求单源最短路径的Dijkstra算法、广度优先搜索算法，都渗透着动态规划的思想。还有许多数学问题，表面上看起来与动态规划风马牛不相及，但是其求解思想与动态规划是完全一致的。因此，动态规划不像深度或广度优先那样可以提供一套模式，需要的时候，取来就可以使用；它必须对具体问题进行具体分析处理，需要丰富的想象力去建立模型，需要创造性的思想去求解。4、动态规划适于解决什么样的问题准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。或许，大家听到这个结论会很失望：其实，这个结论并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许多看似不是这个范围中的问题都可以转化成这类问题。上面所说的“满足一定条件”主要指下面两点：(1)状态必须满足最优化原理；(2)状态必须满足无后效性。所谓的无后效性是指：“过去的决策只能通过当前状态影响未来的发展，当前的状态是对以往决策的总结”。这条特征说明什么呢?它说明动态规划适于解决当前决策和过去状态无关的问题。状态，出现在策略的任何一个位置，它的地位都是相同的，都可以实施同样的决策。这就是无后效性的内涵。5、用动态规划解题的好处说了这么多的动态规划，它到底给我们解题能带来什么好处呢?其实动态规划的最大优势在于它具有极高的效率，而且动态规划还有其他的优势，例如：动态规划可以得出一系列解，算法清晰简便，程序易编、易调，等等。最优化原理与无后效性上面已经介绍了动态规划模型的基本组成，现在需要解决的问题是：什么样的“多阶段决策问题”才可以采用动态规划的方法求解?一般来说，能够采用动态规划方法求解的问题必须满足.最优化原理和.无后效性原则。(1)动态规划的最优化原理。作为整个过程的最优策略具有如下性质：无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。在例题1最短路径问题中，A到E的最优路径上的任一点到终点E的路径也必然是该点到终点E的一条最优路径，满足最优化原理。下面来讨论另外一个问题。【例题2】余数最少的路径。 如图所示，有4个点，分别是A、B、C、D，相邻两点用两条连线C2k，C2k-1(1k3)表示两条通行的道路。连线上的数字表示道路的长度。定义从A到D的所有路径中，长度除以4所得余数最小的路径为最优路径。求一条最优路径。【分析】在这个问题中，如果还按照例题1中的方法去求解就会发生错误。按照例题1的思想，A的最优取值可以由B的最优取值来确定，而B的最优取值为(1+3) mod 4 = 0，所以A的最优值应为2，而实际上，路径C1C3C5可得最优值为(2+1+1) mod 4 = 0，所以，B的最优路径并不是A的最优路径的子路径，也就是说，A的最优取值不是由B的最优取值决定的，即其不满足最优化原理，问题不具有最优子结构的性质。由此可见，并不是所有的“决策问题”都可以用“动态规划”来解决，运用“动态规划”来处理问题必须满足最优化原理。(2)动态规划的无后效性原则。所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。从图论的角度去考虑，如果把这个问题中的状态定义成图中的顶点，两个状态之间的转移定义为边，转移过程中的权值增量定义为边的权值，则构成一个有向无环加权图，因此，这个图可以进行“拓扑排序”，至少可以按他们拓扑排序的顺序去划分阶段。看一看下面的两个具体例子。【例题3】货郎担问题。对于平面给定的n个点，编程确定一条连结各点的、闭合的游历路线问题。图中给出了7个点的情况问题的解。【例题4】旅行路线问题。在货郎担问题的基础上，若规定这种游历路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求整个路程最短的路径长度。图中给出了7个点问题的解。例3图 货郎担问题例4图 旅行路线图【分析】这两个问题看起来很非常相似，但本质上是完全不同的。为了方便讨论，可以将每个顶点标记号码。由于必然经过最右边的顶点7，所以一条路(P1P2)可以看做两条路(P17)与(P27)的结合。因此，这个题目的状态可以用两条道路结合的形式表示。可以把这些状态中，两条路中起始顶点相同的状态归于一个阶段，设为阶段P1，P2。那么，对于旅行路线问题来说，阶段P1，P2如果可以由阶段Q1，Q2推出，则必须满足的条件就是：Pl Q1或P2 0且存在1in使k-wi0，0否则。有了计算各个子问题的最优值的递归式，我们就可以直接编写对应的程序。下述的函数knapsack是输入背包的负重能力k，返回对应的子背包问题的最优值sk： function knapsack(k:integer):integer； begin knapsack:=0； for i:=1 to n do if k-wi=0 then begin t:=knapsack(k-wi)+vi； if knapsack =0 then begin t:=memorized_knapsack(k-Wi)+Vi； if sk =0 then begin t:=sj-wi+vi; if sj =0 then begin t:=sj-wi+vi; if sj t then sj:=t; end; end;/主程序begin read_data; knapsack_order; writeln(sm);end.如果想知道选择了哪些物品，那么应将程序作些改动，具体就是对选中的物品做一标记。见参考程序，其中的数据输入采用文件输入，输入文件为bbinput.txt（第1行为背包负重能力和物品种数，第2行为每种物品的价值，第三行为每种物品的重量）。 动态规划的正向思维法正向思维法是指从初始状态或边界状态出发，利用某种规则不断到达新的状态，直到问题目标状态的方法。动态规划的正向思维法，正是从已知最优值的初始状态或边界状态开始，按照一定的次序遍历整个状态空间，递推出每个状态所对应问题的最优值。提出动态规划的正向思维法的根本原因，是为了摆脱逆向思维法当中那种将大问题转化为子问题的思维框框，提供一种新的思维方式。在正向思维法中，我们不再区分原问题和子问题，将动态规划的过程看成是从状态到状态的转移。我们将所有的状态构造出一个状态空间，并在状态空间中设想一个状态网络，若对两个状态i,j，存在决策变量di使t(i，di)=j，则向状态网络添加有向边。给定己知最优值的初始状态或边界状态，我们可以沿着有向边推广到未知最优值的新状态，利用状态转移方程得到新状态的状态变量的最优值。我们可以用这种方式遍历整个状态空间，得到每个状态的状态变量的最优值。因为正向思维法中不再区分原问题、子问题、子子问题，所以我们不再按照问题被递归调用求解的相反次序的方法确定状态最优值的计算次序。从上面我们知道可以按照状态的拓扑序列来计算每个状态的最优值，于是我们用一个新的名词“阶段”来描述在状态空间遍历的过程中，各个状态最优值的计算次序。我们将每个状态和一个阶段挂钩，前一个阶段的状态先计算，后一个阶段的状态后计算。有的时候我们甚至将一组状态和一个阶段挂钩，前一个阶段的那组状态先计算，后一个阶段的那组状态后计算，而在同一个阶段内，那些状态的计算次序可以是任意的。动态规划的正向思维法的要点可归纳为以下三个步骤：(1)构造状态网络；(2)根据状态转移关系和状态转移方程建立最优值的递推计算式：(3)按阶段的先后次序计算每个状态的最优值。在下一节“最短路问题”当中，我们将结合最短路问题来示范动态规划的正向思维法。动态规划的正向思维法带给我们什么启示呢?动态规划需要按阶段遍历整个状态空间，因此动态规划的效率取决于状态空间的大小和计算每个状态最优值的开销：如果状态空间的大小是多项式的，那么应用动态规划的算法就是多项式时间的；如果状态空间的大小是指数的，那么应用动态规划的算法也是指数时间的。因此，找一个好的状态划分对动态规划的效率是至关重要的。将这个结论应用到逆向思维上，我们得出如下结果：一个问题的最优子结构常常暗示了动态规划的状态空间。典型的情况是，某一个特定问题可有几类“自然”的子问题，不同的子问题往往意味着不同的最优子结构，从而我们得到不同的状态划分方案。但是由这些不同的状态得到的算法的效率可能差异极大。例如，某个问题的输入是一个有序序列，有两类“自然”的子问题，一类子问题的输入是原问题输入序列的所有子序列，另一类子问题的输入是原问题输入序列的任意元素构成的新序列。显然若我们采用后者的最优子结构来建立状态，它的状态空间必然远远大于基于前者的状态空间。那末基于后者的状态空间的动态规划则要解许多不必要的问题，使得算法的效率骤然下降。从动态规划的正向思维法的分析可以看出，我们从已知最优值的初始状态和边界状态出发，利用最优化原理，一步一步向未知的目标状态推进，直到目标状态的最优值解决。这种“从己知推广到未知”的思维，正是动态规划正向思维法的精髓。大家在运用动态规划的正向思维法时如果能掌握这一点，那么就能达到应用自如的境界。在应用动态规划求解的问题的过程中，希望读者能够注意从题目的分析中领会：应用动态规划解题是富于技巧和创造性的，没有固定的模式可套；题目出现的形式多种多样，而且大部分表面上与动态规划看不出直接的联系。只有在充分把握其思想精髓的前提下大胆联想，才能达到得心应手，灵活运用的境界。动态规划设计方法的一般模式 动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。初始状态决策决策决策结束状态 图1 动态规划决策过程示意图(1)划分阶段：，按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。(5)程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据上述动态规划设计的步骤，可得到大体解题框架如图2所示。图2 动态规划设计的一般模式上述提供了动态规划方法的一般模式，对于简单的动态规划问题，可以按部就班地进行动态规划的设计。下面，给出一个利用动态规划方法求解的典型例子。【例题6】数字三角形问题。图3示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。任务一：假设三角形行数10，键盘输入一个确定的整数值M，编程确定是否存在一条路径，使得沿着该路径所经过的数字的总和恰为M，若存在则给出所有路径，若不存在，则输出“NOAnswer!”字样。任务二：假设三角形行数100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，任务一中文件第一行是三角形的行数N和整数值M。以后的N行分别是从最顶层到最底层的每一层中的数字。任务二中文件数据格式同任务一，只是第一行中没有整数值M。在例子中任务二的文件数据表示如下： 输入：5 7 输出： 3 8 7 输出路径和最大值 8 1 0 38 或“No Answer!”字样。 2 7 7 4 810 4 5 2 6 5 2744图3 数字三角形45265【分析】对于这一问题，很容易想到用枚举的方法去解决，即列举出所有路径并记录每一条路径所经过的数字总和。然后判断数字总和是否等于给定的整数值M或寻找出最大的数字总和，这一想法很直观，而且对于任务一，由于数字三角形的行数不大(10)，因此其枚举量不是很大，应该能够实现。但对于任务二，如果用枚举的方法，当三角形的行数等于100时，其枚举量之大是可想而知的，显然，枚举法对于任务二的求解并不适用。其实，只要对对任务二稍加分析，就可以得出一个结论：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该问题是一个典型的多阶段决策最优化的问题。算法设计与分析如下：对于任务一，合理地确认枚举的方法，可以优化问题的解法。由于从塔顶到底层每次都只有两种走法，即左或右。设“0”表示左，“1”表示右，对于层数为N的数字塔，从顶到底的一种走法可用一个N-1位的二进制数表示。如例中二进制数字串1011，其对应的路径应该是：8146。这样就可以用一个Nl位的二进制数来模拟走法和确定解的范围。穷举出从0到2n-1个十进制数所对应的N-1位二进制串对应的路径中的数字总和，判定其是否等于M而求得问题的解。对于任务二，采用动态规划中的顺推解法。按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段第n1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。设：fk(Uk)为从第k阶段中的点Uk至三角形顶点有一条最佳路径，该路径所经过的数字的总和最大，fk(Uk)表示为这个数字和；由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设：Uk1为k-1阶段中某点Uk沿左斜线向下的点；Uk2为k-1阶段中某点Uk沿右斜线向下的点；dk(Uk1)为k阶段中Uk1的数字；dk(Uk2)为k阶段中Uk2的数字。因而可写出顺推关系式(状态转移方程)为：fk(Uk)=maxfk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(Uk2)(k=1，2，3，n)f0(U0)0经过一次顺推，便可分别求出由顶至底N个数的N条路径，在这N条路径所经过的N个数字和中，最大值即为正确答案。动态规划方法实现的灵活性与技巧性上述例子给出了一般情况下的动态规划思维过程。一些较为简单的问题可以“按部就班”来操作，但大多数的“动态规划”问题，特别是作为信息学竞赛中的“动态规划”问题，考察的知识是多方面的，应用的技巧是灵活多变的。下面给出上述例5变形的例子。【例题7】花店橱窗布置问题(99IOI试题)。假设以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果I pathi。在明确两题的不同之后，就可以对动态规划方程进行修改了。假设用bi，j表示美学值表格中第i行的第j个数字，用qi，j表示从表格最底层到bi，j这个数字的最佳路径(路径经过的数字总和最大)的数字和，修改后的动态规划转移方程为：qi,V+1=-(1iF+1)qF，j=bF，j(1jV)qi，j=maxqi+1，k(jKV+1)+AI,J(1IF，1JV)这样，得出的maxq1，k(1jV)就是最大的美学值，算法的时间复杂度为O(FV2)。(3)对算法时间效率的改进。先来看一下这样两个状态的求解方法：qi,j=maxqi+1，k(jkV+1)+bi，j(1iF，1jV)qi