搜索
动态规划初步江苏省大丰高级中学陈鹏2009.7无锡☆引例：数塔问题☆什么是动态规划☆如何运用动态规划☆动态规划小结☆引例：数塔问题一、引入设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，若要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。1315141124131211876872612☆引例：数塔问题☆引例：数塔问题知识回顾一：贪心算法所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。贪心算法并不能对所有问题都能得到整体最优解，但是对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。[问题分析]☆引例：数塔问题如下图，根据贪心法，得出的解为：13-11-21；而实际上最优解应为：13-8-40。贪心法往往得不到最优解。贪心法问题所在：目光短浅。知识回顾二：搜索算法搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵搜索树并寻找符合目标状态的节点的过程。☆引例：数塔问题使用深度优先搜索：从根结点开始，将所有可能的路径求和，找出最大值，但算法时间复杂性使问题解成为不可能。☆引例：数塔问题当N=1P=1N=2P=2N=3P=4……N=KP=2^(K-1)例如：当N=50，P=2^49=500万亿条路径。知识回顾三：递归程序调用自身的编程技巧称为递归。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。☆引例：数塔问题程序清单：vara:array[1..5,1..5]ofinteger;i,j,s,max:integer;proceduref(i,j:integer);begins:=s+a[i,j];ifi=5thenbeginifsmaxthenmax:=s;endelsebeginf(i+1,j);s:=s-a[i+1,j];f(i+1,j+1);s:=s-a[i+1,j+1];end;end;☆引例：数塔问题beginfori:=1to5doforj:=1to5doread(a[i,j]);f(1,1);write(max);end.☆引例：数塔问题F(1,1)F(2,1)F(2,2)F(3,1)F(3,2)F(3,2)F(3,3)F(4,1)F(4,2)F(4,2)F(4,3)F(4,2)F(4,3)F(4,3)F(4,4)F(5,1)F(5,2)F(5,2)F(5,3)F(5,4)F(5,5)☆引例：数塔问题存在的问题：出现重复子问题，需要解决重复计算问题。☆引例：数塔问题知识回顾四：分治算法分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。用分治的策略来分析：将原问题分解为K个子问题，使子问题的解为当前问题规模下的最终解。一层的数塔两层的数塔三层的数塔……N层的数塔保留上一层计算的结果，给下一层使用。如：两个f(3,2)，只需保留较大的那个。☆引例：数塔问题☆引例：数塔问题知识回顾五：递推算法递推算法是一种通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。1311812726614158127132411数据结构：a,b:array[1..n,1..n]ofinteger;☆引例：数塔问题132421363147425062555457758666b[1,1]=a[1,1](i=1)b[i,1]=b[i-1,1]+a[i,1]b[i,i]=b[i-1,i-1]+a[i,i](i1)b[i,j]=max{b[i-1,j-1],b[i-1,j]}+a[i,j]☆引例：数塔问题递推公式：programex;constn=5;vari,j,max:integer;a,b:array[1..n,1..n]ofinteger;beginfori:=1tondoforj:=1toidoread(a[i,j]);☆引例：数塔问题b[1,1]:=a[1,1];fori:=2tondobeginb[i,1]:=b[i-1,1]+a[i,1];//第一行b[i,i]:=b[i-1,i-1]+a[i,i];//斜边forj:=2toi-1do//中间部分ifb[i-1,j-1]b[i-1,j]thenb[i,j]:=b[i-1,j-1]+a[i,j]elseb[i,j]:=b[i-1,j]+a[i,j];end;☆引例：数塔问题max:=b[n,1];forj:=2tondoifmaxb[n,j]thenmax:=b[n,j];writeln('max=',max);end.☆引例：数塔问题解题过程回顾：1、分阶段：子问题如何划分？2、确立状态及状态变量：考虑最终解跟什么相关？3、决策：取数方向是向下还是右下？4、策略和最优策略：最终解在哪儿？5、状态转移方程：b[i,j]=max{b[i-1,j-1],b[i-1,j]}+a[i,j]☆引例：数塔问题动态规划（DynamicProgramming）动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年，美国数学家R.Bellman提出了解决这类问题的“最优化原则”，1957年发表了他的名著《动态规划》，该书是动态规划方面的第一本著作。动态规划问世以来，在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用，取得了显著的效果。动态规划成为了信息学竞赛中必不可少的一个重要方法，几乎在所有的国内和国际信息学竞赛中，都至少有一道动态规划的题目。所以，掌握好动态规划，是非常重要的。☆什么是动态规划动态规划中的相关概念：1、阶段用动态规划求解一个问题时，需要将问题的全过程恰当地划分成若干个相互联系的阶段，以便按一定的次序去求解。阶段的划分一般是根据时间和空间的自然特征来定的，一般要便于把问题转化成多阶段决策的过程。2、状态状态表示的是事物某一阶段的性质，状态通过一个变量来描述，这个变量称为状态变量。各个状态之间是可以相互转换的。☆什么是动态规划3、决策对问题的处理中做出某种选择性的行动就是决策。一个实际问题可能要有多次决策，在每一个阶段中都需要有一次决策。一次决策就会从一个阶段进入另一个阶段，状态也就发生了转移。4、策略和最优策略所有阶段按照约定的决策方法，依次排列构成问题的求解全过程。这些决策的总体称为策略。在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略。☆什么是动态规划5、状态转移方程前一阶段的终点就是后一阶段的起点，这种关系描述了由K阶段到K+1阶段状态的演变规律，是关于两个相邻阶段状态的方程，称为状态转移方程，是动态规划的核心。☆什么是动态规划⑤编写程序。动态规划算法的一般模式：①划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。（在划分阶段时，注意有序或可排序）②确定状态和状态变量：将问题发展到各个阶段时所处的各种情况用不同状态表示出来；③确定决策并写出状态转移方程：一般是根据相邻两个阶段各状态之间的关系来确定决策；④寻找终止条件：给出的状态转移方程是一个递推式，必须有一个递推的终止条件；☆什么是动态规划例1：求一组数列的最长的不下降序列。[问题描述]设有一个正整数序列b1，b2，b3，…，bn，若下标为i1i2i3…ik且有bi1≤bi2≤…≤bik则称存在一个长度为k的不下降序列。可能有多个不下降序列，输出最长序列的长度。[样例输入]13791638243718[样例输出]5(79162437)☆如何运用动态规划[问题分析]1、分阶段：以数的个数为阶段。3、决策：跟前面的哪个数拼接成最长不下降序列。4、策略和最优策略：最终解在哪儿。5、状态转移方程：2、确立状态及状态变量：n个数的最长不下降序列长度。b[1]=1,b[2]=1,b[3]=1,......i-1b[i]=max{b[j]|a[i]=a[j]}+1j=1☆如何运用动态规划12345678a[i]13791638243718b[i]11111111数据结构：设定有n个元素的一维数组整型数组a和b；a[i]表示第i个数的数值本身；b[i]表示第1项到第i项中以a[i]为最后一个值时的最长不下降序列的长度；用表格表示所构造出的b[1..n]初始表如下：☆如何运用动态规划12345678a[i]13791638243718b[i]11234454求解过程：（1）以个数为阶段，从第二项开始计算，由于前面仅有1项，所以做一次比较，因713，不符合问题要求，不作任何改变，长度仍为1。（2）第三项的前面有2项，因此需要做两次比较，得到目前最长的不下降序列为2，情况如下表：☆如何运用动态规划☆如何运用动态规划（3）一般处理过程是：在1，2，……，i-1项中，找出比a[i]小于等于的最长长度L；若L0，则b[i]:=L+1；programex1;vari,j,n,len:integer;a,b:array[1..100]ofinteger;beginreadln(n);fori:=1tondobeginread(a[i]);b[i]:=1;end;☆如何运用动态规划fori:=2tondobeginlen:=0;forj:=1toi-1doif(a[i]=a[j])and(b[j]len)thenlen:=b[j];iflen0thenb[i]:=len+1;end;len:=1;forj:=2tondoifb[j]lenthenlen:=b[j];writeln('maxlen=',len);end.☆如何运用动态规划☆如何运用动态规划思考：如果b[i]表示前i项最长不下降序列的长度，问题的求解过程有什么不同？最优化原理是使用动态规划的条件之一。注意：☆如何运用动态规划作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为：子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质。也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。81432659871013219151732452711131916251120例2：在下列交通路线中，求节点1到节点10的最短路径的长度。☆如何运用动态规划1、分阶段：根据问题最优解划分为子问题为阶段3、决策：从前一阶段的哪个结点走来4、策略和最优策略：最终解在哪儿5、状态转移方程：2、确立状态及状态变量：k阶段的最短路径f[j]=min{f[ki]+a[ki,j],……}☆如何运用动态规划[问题分析]f[ki]就是上阶段子问题各状态的最优解，而a[ki,j]则是某个子状态转移到当前状态产生的决策效应（或者是代价）。解法1：从初始阶段出发的顺推求解第一阶段：f[2]=f[1]+13=13;f[3]=f[1]+21=21;f[4]=f[1]+9=9☆如何运用动态规划第二阶段：f[5]=min{f[2]+15,f[3]+17,f[4]+24}=28;f[6]=min{f[2]+3,f[3]+5,f[4]+27}=16第三阶段：f[7]=min{f[5]+11,f[6]+8}=24;f[8]=min{f[5]+13,f[6]+19}=35;f[9]=min{f[6]+16}=32第四阶段：f[10]=min{f[7]+25,f[8]+11,f[9]+20}=46动态规划的算法设计☆如何运用动态规划如果用i表示当前需求解的阶段号，j表示当前阶段各个状态（或者说是阶段的各个节点编号），k表示前一阶段各个子状态能选择的策略，用f[i,j]表示起点1到第i阶段编号为j的结点（也可理解为状态）的最短距离，那么上面问题用动态规划求解的大致程序结构如下：穷举所有的