动态规划

1动态规划顾铁成2动态规划(DynamicProgramming)是在上世纪50年代，为了解决一类多阶段决策问题而诞生的。那么，什么样的问题被称作多阶段决策问题呢？3【例1】最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，我们想从A城市到达E城市，问怎样走才能使得路径最短。最短路径的长度是多少？438655163358AB2B1C1C2C3C4D1D2D3E43435从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题：多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间或空间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。——用宽搜也可以解决这类问题?6原问题可以分解成一系列的子问题话(如一些递归、递推问题)，也可以视同“多阶段决策”问题一样来套用DP方法解决其实，这也是在介绍DP方法时，为什么总是要提“多阶段决策”的原因，因为，DP方法正是针对解决这类有着大量重叠子问题、需要靠穷举才能解决的问题的不足而提出来的7问题：这一问题可以用哪几种方法来解决?可以采用某种比较原始的方法，如穷举法吗？可以用搜索策略吗?例如，深搜、宽搜?代价如何?当图的规模较大时，还能搜索吗?可以采用贪心策略吗?可以对该问题进行图论方法建模，然后再采用某种图论算法吗?8问题及解法分析可以用以下算法来解决这一问题。设：dis[x]为城市x到城市E的最短路径map[i,j]表示i、j两个城市间的距离。若两个城市间不通，则map[i,j]=09vars:未访问的城市集合;functionsearch(city):integer;{求城市city与城市E间的最短距离}beginifcity=Ethensearch:=0elsebeginmin:=maxint;fori取遍所有城市do{穷举搜索}if(map[city,i]0)and(i∈S)thenbeginS:=S–[i];{S为未访问过的城市集合;标记城市i为已访问}10j:=map[city,i]+search(i){计算城市E至城市city间的路径长度}S:=S+[i];{恢复城市i为未访问状态。为什么要恢复?}ifjminthenmin:=j;end;{ofthenandendoffor}search:=min;{循环/穷举搜索后得到的最短距离}end;{ofelse}end;{ofsearch}11begin{main}S:=除E外的所有城市;dis[A]:=search(A);输出dis[A];end.{ofmain}12现在来关注一个问题：该算法的效率如何呢?可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度较高。问题：这是一种怎样的策略?是穷举搜索?是深搜?是宽搜?13分析用以上算法来解决这类问题是非常直观的，但效率却很低下(这种低效是搜索策略内在吗?)：在求B1到E的最短路径时，先求出从C2到E的最短路径，而在求从B2到E的最短路径时，又求了一遍从C2到E的最短路径。也就是说，从C2到E的最短路径求了两遍。14分析同样可以发现，在求从C1、C2到E的最短路径的过程中，从D1到E的最短路径也被求了两遍，这样在整个计算过程中，从D1到E的最短路径被求了四遍——这是一种浪费(问题：在带回溯的深搜中也有这个问题吗?)15分析如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。就本题而言，可以得出一种新的思路，即由后往前(为什么要从后往前?)，依次推出每个Dis值(并记录在案)，直到推出Dis[A]时为止。类比：求F(n)=F(n-1)+F(n-2)的两种方法，即递归(自顶向下分解)和迭代(自底向上合成)实现16分析那么，在本例中，究竟什么是“由后往前”呢？所谓前后关系，是指对于任意一对城市i和j来说，如果满足“Dis[i]+map[i,j]=Dis[j]”这一条件，则定义为城市i在前，城市j在后。问题：“从后往前”本质上反映了什么东西?例如，F(n)=F(n-1)+F(n-2)也能这样从后往前处理吗?17我们注意到：越是接近底层的子问题被重复计算的次数也就越多。我们能不能将上述递归法的求解过程进行优化，避免重复计算，使所有的子问题都只计算一次？(即倒用递归法，用其递归上升阶段)18要实现这一点,必须做到两件事：1.自底向上地计算子问题最优解(为什么要自底向上?)。越是靠近底层的子问题,越是先计算出来。2.用表格存储计算出的子问题的最优解的值,以便在计算它的“上层”子问题时能够直接引用，而不是去重新计算。此处表格即数组。19分析这是因为，如果城市i和城市j连通，并且有Dis[i]+map[i,j]Dis[j]，则说明城市i至城市E的最短路径长度应该比Dis[j]更优。可是，城市j位于城市i后不可能推出此情况，以至于影响最后的解。那么，我们应该如何来划分先后次序呢？20阶段的性质按照从后往前的阶段划分方式，可知这种阶段划分方式有以下的性质：1)阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响；2)每个阶段的顺序是确定的，不可以调换任两个阶段的顺序。21阶段的性质我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段1的城市A。在求解的各个阶段，利用了阶段k与阶段k+1之间的如下关系：(x属于第k阶段，y属于第k+1阶段)由此可以得出以下的算法片段：[]1[]min{[][,]|(,)}kykDisxdisymapxyxyG阶段的城市集22dis[e]:=0;fork:=4downto1do{体现倒推}forx取遍k阶段的所有城市dobegindis[x]:=∞;fory取遍k+1阶段的所有城市doifdis[y]+map[x,y]dis[x]thendis[x]:=dis[y]+map[x,y];end;{offor}输出dis[A];23这个程序的时间复杂度为O(n2)，比回溯法的时间复杂度O(n!)要小得多(这两个复杂度是如何得出来的?)，其解题的思路就是下面要介绍的动态规划方法。24动态规划方法的基本概念通过上面的例子，我们对动态规划方法有了一定的感性认识，即它所处理的问题是一种“多阶段决策问题”。下面介绍该方法涉及的一些基本概念。25动态规划方法的基本概念1)阶段将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求解每一阶段的解。设阶段变量为k。26动态规划方法的基本概念2)状态各阶段开始时的客观条件叫做状态，如上例中城市A、B1、D2、E等都是单个状态，描述各阶段状态的变量称为状态变量，常用sk表示阶段k的状态变量。状态变量sk的取值集合称为状态集合，用Sk表示，例如，S2={C1,C2,C3,C4}27动态规划方法的基本概念每个阶段的状态都是由前一阶段的状态以某种方式的“变化”而得到的，这种“变化”称为状态转移应用动态规划方法的一个重要条件：将各阶段按照一定的顺序排列好之后，阶段i的状态只能由阶段i+1的状态，通过状态转移方程得到，与其他状态无关，尤其是与未发生的状态无关(此处的i、i+1、“未发生”等都与顺推还是逆推有关)，这就是“无后效性”（应用DP为什么需要这一特性？）28动态规划方法的基本概念例如，在上例中，计算城市B1至E的最短路径时，必须在C1至E、C2至E、C3至E的最短路径已经求出的基础上才能得到，与其他城市(如城市A)无关n个阶段的决策过程有n+1个状态变量29动态规划方法的基本概念3)决策当前阶段的状态取定后，就可以做出不同的决定，从而确定下一阶段的状态。这种决定称为决策。表示决策的变量称为决策变量，常用Uk(Sk)表示第k阶段当状态为Sk时的决策变量。30动态规划方法的基本概念在实际问题中，决策变量的取值往往限制在某一范围内，称此范围为允许决策集合。常用Dk(Sk)表示第k阶段从状态Sk出发的允许决策集合，如D1(B1)={C1,C2,C3}。显然有Uk(sk)Dk(sk)。31动态规划方法的基本概念前面说过，由第k阶段的状态Sk和决策Uk来确定第k+1阶段的状态Sk+1的过程称为状态转移(与搜索中的状态扩展，如魔板问题、电梯问题?)，状态转移规律的数学表示：Sk+1=Tk(Sk,Uk)称为状态转移方程。问题：逆推也可以写出这样的公式吗?或者说，在逆推方式下，如何来写出、利用这种状态转移方程?32动态规划方法的基本概念4)策略各阶段决策确定后，整个问题的决策序列就构成了一个策略，用P1,n={U1(S1),U2(S2),…,Un(Sn)}表示。使整个问题达到最有效果的策略就是最优化策略。(注意：顺推、逆推情况下都是策略；非最优化问题也可以有策略)33最优化原理可以运用动态规划方法的又一项前提/标志：整个过程的最优策略应具有这样的性质，即无论初始状态和决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略，这就是最优化原理。换句话说，最优策略的子策略也是最优策略。(“最优子结构”)（如何理解？运用DP时为什么需要这一原理？顺推或逆推对这一原理的要求有无不同的要求？不是最优化的问题是否满足这一原理？能否应用DP？）34例如，在上例中，通过动态规划方法求解后，不仅A到E的路径是所有路径中的最短者，且该路径上的任何一个城市至城市E的路径也是最短的(在本问题中，最优化原理是如何表现的?这一原理与逆推的关系?)前一个城市到E的距离是最优(即最短的)，则后一个城市到E也是最优的贪心法问题是否满足最优子结构特性？35最优子结构性质表明我们可以利用子问题的最优解来构造问题的最优解。(思考：在我们接触过的问题中，哪些具有较为明显的最优子结构特点?“最优子结构”与无后效性的关系?)问题：只有求“最优解”问题才适用动态规划方法吗?可以用动态规划解决的问题非得具有“最优子结构”吗?36我们能否这样来看待最优子结构特性，即把它改造或活用一下，即在有的题目中这样来理解：问题的一个(最优)解中包含着子问题的(最优解)。例如，F(n)=F(n-1)+F(n-2)问题要否用动态规划这样的方法来解决?37对最短通路问题，子问题的最优解这样来构造问题的最优解：问题的最优解=MIN(B1~E的最优解+A~B1的长度，B2~E的最优解+A~B2的长度){这是一个递归的表达式，可以用递归或递推(逆推)来实现。}38因此，为了解决A~E的最短通路问题，我们必须首先解决B1~E的最短通路问题和B2~E的最短通路问题。这显然是一个递归的过程39可以应用动态规划解题的两个基本条件是什么？题目性质具有“最优子结构”特征，即问题的一个最优解中包含着子问题的最优解。(无后效性)重叠子问题，即求解问题的解时要反复计算若干个相同的子问题。同理，求解各个子问题时又要反复计算若干子子问题，这些子子问题可能是新产生的，也可能是重复产生的。40最优化原理作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质。也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。41最优化原理在“数塔问题”例子中，如果我们想求走到某一位置的最优路径，我们只需要知道其(左上方或正)上方两个位置之一的最优值，而不用考虑其他的路径，因为其他的非最优路径肯定对当前位置的结果没有影响。42最优化原理如果我们把该问题稍微改变一下：将三角形中的数字改为-100～100之间的整数，计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最接近于零。43最优化原理这个问题就不具有最优子结构性质了，因为子问题最优(最接近于零)反而可能