广度双向搜索的概念

1、1.1 广度双向搜索的概念 所谓双向搜索指的是搜索沿两个力向同时进行：正向搜索：从初始结点向目标结点方向搜索；逆向搜索：从目标结点向初始结点方向搜索；当两个方向的搜索生成同一子结点时终止此搜索过程。 1. 2 广度双向搜索算法广度双向搜索通常有两中方法：1. 两个方向交替扩展2. 选择结点个数较少的那个力向先扩展方法2克服了两方向结点的生成速度不平衡的状态，明显提高了效率。 算法说明：设置两个队列c:array0.1,1.maxn of jid，分别表示正向和逆向的扩展队列。设置两个头指针head:array0.1 of integer 分别表示正向和逆向当前将扩展结点的头指针。设置

2、两个尾指针tail:array0.1 of integer 分别表示正向和逆向的尾指针。maxn表示队列最大长度。算法描述如下：1.主程序代码 repeat  选择节点数较少且队列未空、未满的方向先扩展   if (tail0<=tail1) and not(head0>=tail0)or(tail0>=maxn) then expand(0);  if (tail1<=tail0) and not(head1>=tail1)or(tail1>=maxn) then expand(1);  如果一方

3、搜索终止，继续另一方的搜索，直到两个方向都终止  if not(head0>=tail0)or(tail0>=maxn) then expand(0);  if not(head1>=tail1)or(tail1>=maxn) then expand(1); Until (head0>=tail0)or(tail0>=maxn)   And (head1>=tail1)or(tail1>=maxn)2.expand(st:0.1)程序代码如下:  inc(headst;  取出

4、队列当前待扩展的结点cst,headst  for i:=1 to maxk do    begin       if tailst>=maxn then exit;      inc(tailst);     产生新结点;      check(st);检查新节点是否重复    end;3.check(st:0.1)程序

5、代码:  for i:=1 to tailst-1 do      if cst,tailst.*=cst,i.* then begin dec(tailst);exit end;    bool(st);如果节点不重复，再判断是否到达目标状态4.bool(st:0.1)程序代码:  for i:=1 to tail1-st do    if cst,tailst.*=c1-st,i.* then  print(st,tailst,i); 

6、60;   如果双向搜索相遇（即得到同一节点），则输出结果5.print(st,tail,k)程序代码：if st=0 then begin print0(tail);print1(k) end;        else begin print0(k);print1(tail) end;6.print0(m)程序代码： if m<>0 then begin print(c0,m.f);输出c0,m.* end;输出正方向上产生的结点7.print1(m)程序代码; n:=c

7、1,m.f while m<>0  begin    输出c1,n.*;   n:=c1,n.f;  end输出反方向上产生的结点1.3 例题与习题 例1：8数码难题 ：                2 8 3    1 2 3       &#

8、160;        1 6 4 -> 8   4（用最少的步数）                7   5    7 6 5程序如下：program num8;const maxn=4000;type jid=record     str:string9;&#

9、160;    f:0.maxn;     dep:byte;     end;    bin=0.1;var c:array0.1,1.maxn of jid;    head,tail:array0.1 of integer;    start,goal:string9;procedure init;var i,j:integer;begin start:='28316470

10、5' goal:='123804765' for i:=0 to 1 do  for j:=1 to maxn do    new(ci,j); c0,1.str:=start; c0,1.f:=0; c0,1.dep:=0; c1,1.str:=goal;  c1,1.f:=0; c1,1.dep:=0; for i:=0 to 1 do  begin headi:=0;taili:=1;end;end;procedure print(st:bin;tail,

11、k:integer);procedure print0(m:integer);beginif m<>0 then begin print0(c0,m.f);writeln(c0,m.str) end;end;procedure print1(m:integer);var n:integer;begin n:=c1,m.f; while n<>0 do  begin writeln(c1,n.str); n:=c1,n.f end;end;begin if st=0 then    begin

12、 writeln('step=',c0,tail.dep+c1,k.dep);         print0(tail); print1(k);end        else begin writeln('step=',c0,k.dep+c1,tail.dep);        print0(k); print1(tail); end ;halt

13、;end;procedure check(st:bin);procedure bool(st:bin);var i:integer;begin for i:=1 to tail1-st do  if cst,tailst.str=c1-st,i.str then  print(st,tailst,i);end;var i:integer;begin  for i:=1 to tailst-1 do   if cst,tailst.str=cst,i.str then    begin dec(tailst

14、);exit end;  bool(st);end;procedure expand(st:bin);var i,p0,p1,d:integer;str0,str1:string9;begin inc(headst); str0:=cst,headst.str; d:=cst,headst.dep; p0:=pos('0',str0); for i:=1 to 4 do   begin    if tailst>=maxn then exit; 

15、0;  p1:=p0+2*i-5;    if (p1 in 1.9) and not (p0=3) and (p1=4)and not(p0=4)and (p1=3)       and not(p0=6)and(p1=7)and not(p0=7)and(p1=6)      then       begin      &#

16、160; inc(tailst);        str1:=str0;        str1p0:=str1p1;        str1p1:='0'        cst,tailst.str:=str1;        cs

17、t,tailst.f:=headst;        cst,tailst.dep:=d+1;        check(st);       end;   end; end;begin init; check(0); repeat   if (tail0<=tail1) and not(head0>=ta

18、il0)or(tail0>=maxn)    then expand(0);   if (tail1<=tail0) and not(head1>=tail1)or(tail1>=maxn)    then expand(1);   if not(head0>=tail0)or(tail0>=maxn) then expand(0);   if not(head1>=tail1)or(tail1>=maxn) then expa

19、nd(1);Until(head0>=tail0)or(tail0>=maxn)And(head1>=tail1)or(tail1>=maxn);writeln('No answer');end.动态规划总结专题一 状态表示在用动态规划解题时，我么往往第一个考虑的是数组维数，其实数组维度（和状态表示）是有规律可循的：A. 二维空间的DP：一般采用二位数组di，j表示当i，j为某一边角时的极值（e：di，j可以表示以i，j为右上角时所能构成的正方形的边长最大值听不懂？接着往下看）。 还有一种表示方法：di，num表示走到第i各阶段的第num个位置：1 2

20、3 4 5 61234561，12，23，34，45，56，62，13，24，35，46，57，53，14，25，36，47，48，44，15，26，37，38，39，35，16，27，28，29，210，26，17，18，19，110，111，1这种表示解决“多次访问同一图”类的DP题很有用。阶段决策类的DP：这里指阶段划分十分明显的题（0/1背包）。一般采用di,j表示执行到第i各阶段，剩余代价为j时，所能取得的最高分。（如果限制条件多，可增加维度）。树形关系类的DP：一般用di来表示以i为根节点的最优值，可以加维来保证正确性。线性关系类的DP：这一类的DP最简单，是每一个OIER的必备基

21、础，在这里就不废话了。专题二 状态转移（专题二与专题一的分类标准不同，因为dugushuiyi说这样分更好，感谢他）线性转移一般公式：di= operation（dj+wj，i）（wi为由j转移到i的消耗）operation为求最值阶段性转移一般公式：di，j：= operation（di-1，k+wk，j，di-2，） 如果只涉及到前面的有限个阶段，可以使用滚动数组。DI mod n，j= operation（d(i-1)mod n，k+wk，j，d(i-2)mod n，）树性转移一般公式：Di，j=max（dlsoni，k1+wj，k1，drsoni，k2+wj，k2）遍历顺序一般为后序遍

22、历顺序。多维空间转移一般公式：di，j:=max(di-1,j+w1,di,j-1+w2)复杂度分析：DP的复杂度为:状态表示的数组维数*状态转移的代价So A 的复杂度为O（n2） BCD:O(n3);专题三 题目分类总结一般类试题题库：最长不下降子序列最长匹配前缀邮票组合共性总结：题目一般可以通过for 语句来枚举状态，所以时间复杂度为O（N2）本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。一般来说，有两种编号的状态：状态(i)表示前i个元素决策组成的一个状态。状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。01背包：（重点）题库：01背

23、包（USACO、vijos1025、1104）装箱问题（NOIP01 Trade 4）、取火柴问题(sgu153 Playing with matches)共性总结：一般都从阶段的角度来表示状态因为di，j只与di-1，k有关，所以可以用滚动数组来实现。Dodd（i），j各例分析：采药（NOIP2006、vijos） 一个背包，每个物品只能放一次。 (1)Di，j：=max（di，j，di，j-ti+pi）；DI,j表示决策了前i个物品，花费了j的代价优化：滚动数组.(2)Dodd（i），j：=max（di-1，j，dodd（i-1），j-ti+pi）；观察(2)不难发现，当我们算到j时，1&

24、#224;j-1并没有更新，而di-1，j-ti一定在1àj-1的范围内，所以完全可以用一位数组，方程为：di：=max（di，di-tj+pj）在最外层循环一下j就ok了。（精益求精）总分（USACO） 一个背包，可以重复放物品。 Di：=max（di，di-tj+pj） Di表示花费i各单位时间所能达到的最大值。（较简单）Raucous Rockers（USACO） 多个背包，不可以重复放物品，但放物品的顺序有限制。dI,j,k:=max(dI-1,j,k,dI-1,j,k-ti+pi,di-1,j-1,maxtime-ti) dI,j,k表示决策到第i个物品、第j个背包，此背包

25、花费了k的空间。dI-1,j,k表示不取i，dI-1,j,k-ti表示取了i病房入背包j中，di-1,j-1,maxtime-ti 表示取了i病房入背包j-1中。比较好理解。（本题也可以用滚动数组优化）Fence Rails（USACO）多个背包，不可以重复放物品，但放物品的顺序无限制。这道题只能用search做了，因为放物品的顺序无限制，无论怎么表示状态，都不能保证无后效性。（为什么1 、2题可以？想一想。因为只有一个背包）背包为题的版本还有很多，但万变不离其宗，我们应该抛开背景，来观察问题的实质。小锦言：我也做过和1、2、3类似的背包问题，有些版本和1、2、3极像，但不能使用DP，因为它将

26、一些本质的条件更改了。旅游DP：题库：方格取数(NOIP00 advance 4)旅行商简化版（VIJOS）（欧几里德回路）巡游加拿大（IOI95、USACO）三取方格数（VIJOS）Hill（VIJOS）花店橱窗布置(IOI99)共性分析：1、行走方向决定阶段性有规定源点与终点。每次行走方向都有一定的规定，使原点到终点的所有路径形成无环有向图。2、决策稀疏性就是所谓走法，若对于一个状态，它的前驱或者后继数很少(从无环有向图角度，就是入度或出度少)，称决策稀疏。3、状态稀疏性就是很多状态是没有用的，如排列的LCS,状态为2维的(x,y)，但对于一个x只有一个y是有效个。所以实质上状态数还是线形

27、的。4 、 阶段划分不明显（1、2、3 by Amber）各例分析：一取方格数m*n的方格内填上一些数，从1，1出发，只能向上或向右走， 走到m，n使得所经方格的数字之和最大。 题目很简单，不说了。三取方格数与上题类似，要求走三遍（可以重复），使得三遍所经方格的数字之和最大。本题的状态表示用到了开始时的表格（一个人走三次=三个人走一次）1234561，12，23，34，45，56，62，13，24，35，46，57，53，14，25，36，47，48，44，15，26，37，38，39，35，16，27，28，29，210，26，17，18，19，110，111，1dnum,i,j,k:=ma

28、x(dnum-1,i-1,j,k, dnum-1,i-1,j-1,kdnum-1,i-1,j-1,k-1, dnum-1,i-1,j,k-1dnum-1,i,j,k, dnum-1,i-1,j-1,kdnum-1,i,j-1,k-1, dnum-1,i-1,j,k-1)dnum，i，j，k表示三个人在第num各阶段，的i，j，k位置（i<=j<=k）是的最优值。1、 巡游加拿大（IOI95、USACO） 从东至西有m个城市，其中某些城市之间有航班，让你从最东边的城市出发，坐航班每次只能向西走，走到最西边之后再往回走到最东边的城市（除了两端的城市，其他城市只能经过一次），使得经过的城

29、市数量尽可能多。 （东至西至东=两个人同时向西走且经过的城市不相同）设di,j表示从起点出发，一个人到达i，另一个人到达j时经过的城市数。因为di,j=dj,i，所以我们限制i>j。分析状态(i,j)，它可能是(k,j)(j<k<i)中k到达i得到（方式1），也可能是(j,k)(k<j)中k超过j到达i得到（方式2）。但它不能是(i,k)(k<j)中k到达j得到，因为这样可能会出现重复路径。即使不会出现重复路径，那么它由(j,k)通过方式2同样可以得到，所以不会遗漏解。所以状态转移方程是：di,j=maxdk,j+1(k,i可达且j<k<i),dj,k

30、+1(k,i可达且k<j)。时间复杂度O(n3)（by forverstar）一、 环形DP：题库：数字游戏（VIJOS）HILL（VIJOS）看似很难，只要想清楚就可以了。二、 树形DP：题库：加分二叉树（NOI、VIJOS）选课（NOI、VIJOS）这两道题网上的解题报告很多，我就不罗嗦了。其他练习题：a) 括号序列(Problem B, NEERC 2001)b) 多边形(IOI98)c) 石子合并(NOI95 2)构造最优二叉排序树(CTSC96 2)a) 整数划分常应用在将一个权分配给一定的小分割块，如：将大堆的石子分成一定的小堆，小堆可为空，大堆要分完。有时应用在树型动态规划

31、（二叉转多叉）中。b) 乘积最大(NOIP00 Advance 2)推荐题库：VIJOS动态规划专题动态规划算法的优化技巧一、引言动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂

32、度，使其能够适用于更大的规模。二、动态规划时间复杂度的分析使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。下面给出动态规划时间复杂度的决定因素：时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间1下文就将分别讨论对这三个因素的优化。这里需要指

33、出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。三、动态规划时间效率的优化3.1 减少状态总数：我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。1、改进状态表示状态的规模与状态表示的方法密切相关，通过改进状态表示减小状态总数是应用较为普遍的一种方法。例一、 Raucous Rockers

34、 演唱组（USACO96）问题描述现有n首由Raucous Rockers 演唱组录制的珍贵的歌曲，计划从中选择一些歌曲来发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：（1） 这组唱片中的歌曲必须按照它们创作的顺序排序；（2） 包含歌曲的总数尽可能多。输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。（1n, m, t20）算法分析本题要求唱片中的歌曲必须按照它们创作顺序排序，这就满足了动态规划的无后效性要求，启发我们采用动态规划进行解题。分析可知，该问

35、题具有最优子结构性质，即：设最优录制方案中第i首歌录制的位置是从第j张唱片的第k分钟开始的，那么前j-1张唱片和第j张唱片的前k-1分钟是前1.i-1首歌的最优录制方案，也就是说，问题的最优解包含了子问题的最优解。设n首歌曲按照写作顺序排序后的长度为long1.n，则动态规划的状态表示描述为：gi, j, k，0in，0jm，0k<t，表示前i首歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数目，则问题的最优解为gn,m,0。由于歌曲i有发行和不发行两种情况，而且还要分另加的k分钟是否能录制歌曲i。这样我们可以得到如下的状态转移方程和边界条件：当klongi，i1时：gi, j,

36、k=maxgi-1,j,k-longi，gi-1,j,k当k<longi，i1时：gi, j, k=maxgi-1,j-1,t-longi，gi-1,j,k规划的边界条件为：当0k<t时：g0,0,k=0;我们来分析上述算法的时间复杂度，上述算法的状态总数为O(n*m*t)，每个状态转移的状态数为O(1)，每次状态转移的时间为O(1)，所以总的时间复杂度为O(n*m*t)。由于n，m，t均不超过20，所以可以满足要求。算法优化当数据规模较大时，上述算法就无法满足要求，我们来考虑通过改进状态表示提高算法的时间效率。本题的最优目标是用给定长度的若干张唱片录制尽可能多的歌曲，这实际上等价

37、于在录制给定数量的歌曲时尽可能少地使用唱片。所谓“尽可能少地使用唱片”，就是指使用的完整的唱片数尽可能少，或是在使用的完整的唱片数相同的情况下，另加的分钟数尽可能少。分析可知，在这样的最优目标之下，该问题同样具有最优子结构性质，即：设D在前i首歌中选取j首歌录制的最少唱片使用方案，那么若其中选取了第i首歌，则D-i是在前i-1首歌中选取j-1首歌录制的最少唱片使用方案，否则D前i-1首歌中选取j首歌录制的最少唱片使用方案，同样，问题的最优解包含了子问题的最优解。改进的状态表示描述为：gi, j=(a, b)，0in，0ji，0am，0bt，表示在前i首歌曲中选取j首录制所需的最少唱片为：a张唱

38、片另加b分钟。由于第i首歌分为发行和不发行两种情况，这样我们可以得到如下的状态转移方程和边界条件：gi, j=mingi-1,j，gi-1,j-1+longi 其中(a, b)+longi=(a, b)的计算方法为：当longit-b时： a=a; b=b+longi;当longi>t-b时： a=a+1; b=longi;规划的边界条件：gi,0=(0,0) 0in这样题目所求的最大值是：ans=maxk| gn, k(m-1,t)改进后的算法，状态总数为O(n2)，每个状态转移的状态数为O(1)，每次状态转移的时间为O(1)，所以总的时间复杂度为O(n2)。值得注意的是，算法的空间复

39、杂度也由改进前的O(m*n*t)降至优化后的O(n2)。（程序及优化前后的运行结果比较见附件）通过对本题的优化，我们认识到：应用不同的状态表示方法设计出的动态规划算法的性能也迥然不同。改进状态表示可以减少状态总数，进而降低算法的时间复杂度。在降低算法的时间复杂度的同时，也降低了算法的空间复杂度。因此，减少状态总数在动态规划的优化中占有重要的地位。2、选择适当的规划方向： 动态规划方法的实现中，规划方向的选择主要有两种：顺推和逆推。在有些情况下，选取不同的规划方向，程序的时间效率也有所不同。一般地，若初始状态确定，目标状态不确定，则应考虑采用顺推，反之，若目标状态确定，而初始状态不确定，就应该考

40、虑采用逆推。那么，若是初始状态和目标状态都已确定，一般情况下顺推和逆推都可以选用，但是，能否考虑选用双向规划呢？双向搜索的方法已为大家所熟知，它的主要思想是：在状态空间十分庞大，而初始状态和目标状态又都已确定的情况下，由于扩展的状态量是指数级增长的，于是为了减少状态的规模，分别从初始状态和目标状态两个方向进行扩展，并在两者的交汇处得到问题的解。上述优化思想能否也应用到动态规划之中呢？来看下面这个例子。例二、 Divide (Merc2000)问题描述有价值分别为1.6的大理石各a1.6块，现要将它们分成两部分，使得两部分价值和相等，问是否可以实现。其中大理石的总数不超过20000。(英文试题详

41、见附件)算法分析令S=(i*ai)，若S为奇数，则不可能实现，否则令Mid=S/2，则问题转化为能否从给定的大理石中选取部分大理石，使其价值和为Mid。这实际上是母函数问题，用动态规划求解也是等价的。mi, j，0i6，0jMid，表示能否从价值为1.i的大理石中选出部分大理石，使其价值和为j，若能，则用true表示，否则用false表示。则状态转移方程为：mi, j=mi, j OR mi-1,j-i*k (0kai)规划的边界条件为：mi,0=true； 0i6若mi, Mid=true，0i6，则可以实现题目要求，否则不可能实现。我们来分析上述算法的时间性能，上述算法中每个状态可能转移的

42、状态数为ai，每次状态转移的时间为O(1)，而状态总数是所有值为true的状态的总数，实际上就是母函数中项的数目。算法优化实践发现：本题在i较小时，由于可选取的大理石的价值品种单一，数量也较少，因此值为true的状态也较少，但随着i的增大，大理石价值品种和数量的增多，值为true的状态也急剧增多，使得规划过程的速度减慢，影响了算法的时间效率。另一方面，我们注意到我们关心的仅是能否得到价值和为Mid的值为true的状态，那么，我们能否从两个方向分别进行规划，分别求出从价值为1.3的大理石中选出部分大理石所能获得的所有价值和，和从价值为4.6的大理石中选出部分大理石所能获得的所有价值和。最后通过判

43、断两者中是否存在和为Mid的价值和，由此，可以得出问题的解。状态转移方程改进为：当i3时：mi, j=mi, j OR mi-1,j-i*k (1kai)当i>3时：mi, j=mi, j OR mi+1,j-i*k (1kai)规划的边界条件为：mi,0=true； 0i7这样，若存在k，使得m3,k=true, m4,Mid-k=true，则可以实现题目要求，否则无法实现。（程序及优化前后的运行结果比较见附件）从上图可以看出双向动态规划与单向动态规划在计算的状态总数上的差异。回顾本题的优化过程可以发现：本题的实际背景与双向搜索的背景十分相似，同样有庞大的状态空间，有确定的初始状态和目

44、标状态，状态量都迅速增长，而且可以实现交汇的判断。因此，由本题的优化过程，我们认识到，双向扩展以减少状态量的方法不仅适用于搜索，同样适用于动态规划。这种在不同解题方法中，寻找共通的属性，从而借用相同的优化思想，可以使我们不断创造出新的方法。3.2 减少每个状态转移的状态数：在使用动态规划方法解题时，对当前状态的计算都是进行一些决策并引用相应的已经计算过的状态，这个过程称为“状态转移”。因此，每个状态可能做出的决策数，也就是每个状态可能转移的状态数是决定动态规划算法时间复杂度的一个重要因素。本节将讨论减少每个状态可能转移的状态数的一些方法。1、四边形不等式和决策的单调性例三、石子合并问题(NOI

45、95)问题描述 在一个操场上摆放着一排n（n20）堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。算法分析这道题是动态规划的经典应用。由于最大得分和最小得分是类似的，所以这里仅对最小得分进行讨论。设n堆石子依次编号为1，2，.，n。各堆石子数为d1.n，则动态规划的状态表示为：mi,j，1ijn，表示合并di.j所得到的最小得分，则状态转移方程和边界条件为：mi,j=0 i=j ij同时令si,j=k，表示合并的断开位置，便于在计算出最优值后构造出最优解

46、。上式中的计算，可在预处理时计算，i=1.n；t0=0, 则：上述算法的状态总数为O(n2)，每个状态转移的状态数为O(n)，每次状态转移的时间为O(1)，所以总的时间复杂度为O(n3)。算法优化当函数wi,j满足时，称w满足四边形不等式2。当函数wi,j满足wi,jwi,j 时称w关于区间包含关系单调。在石子归并问题中，令wi,j= ，则wi,j满足四边形不等式，同时由di0,ti0可知wi,j满足单调性。mi,j=0 i=j i<j 对于满足四边形不等式的单调函数w，可推知由递推式定义的函数mi,j也满足四边形不等式，即。这一性质可用数学归纳法证明如下：我们对四边形不等式中“长度”l

47、=j-i进行归纳：当i=i或j=j时，不等式显然成立。由此可知，当l1时，函数m满足四边形不等式。下面分两种情形进行归纳证明：情形1：i<i=j<j在这种情形下，四边形不等式简化为如下的反三角不等式：mi,j+mj,j mi,j，设k=maxp | mi,j=mi,p-1+mp,j+wi,j ，再分两种情形kj或k>j。下面只讨论kj，k>j的情况是类似的。情形1.1：kj，此时：情形2：i<i<j<j设 y=maxp | mi,j=mi,p-1+mp,j+wi,j z=maxp | mi,j=mi,p-1+mp,j+wi,j 仍需再分两种情形讨论，即

48、zy或z>y。下面只讨论zy，z>y的情况是类似的。由i<zyj有：综上所述，mi,j满足四边形不等式。对于mi,j=maxmi,k+mk,j+wi,j有：mi,j+mi',j'<=mi,j'+mi',j设y=maxk|mi',j'=mi',y+my,j'+wi',j'情况1:y>jmi,j'+mi',j>=wi,j'+mi,y+my,j'+mi',j>=wi,j'+my,j'+mi,j+mi',y>=m

49、i,j+mi',y+my,j'+wi',j'=mi,j+mi',j'情况2:i'<y<jmi,j'+mi',j>=mi,j'+mi',y+my,j+wi',j>=mi,j+my,j'+mi',y+wi',j>=mi,j+mi',y+my,j'+wi',j'=mi,j+mi',j'令si,j=maxk | mi,j=mi,k-1+mk,j+wi,j 由函数mi,j满足四边形不等式可以推出函数si,j的

50、单调性，即si,jsi,j+1si+1,j+1, ij当i=j时，单调性显然成立。因此下面只讨论i<j的情形。由于对称性，只要证明si,jsi,j+1。令mki,j=mi,k-1+mk,j+wi,j。要证明si,jsi,j+1，只要证明对于所有i<kkj且mki,jmki,j，有：mki,j+1mki,j+1。事实上，我们可以证明一个更强的不等式mki,j-mki,jmki,j+1-mki,j+1也就是： mki,j+mki,j+1mki,j+1+mki,j利用递推定义式将其展开整理可得：mk,j+mk,j+1mk,j+mk,j+1，这正是kkj<j+1时的四边形不等式。综上

51、所述，当w满足四边形不等式时，函数si,j具有单调性。于是，我们利用si,j的单调性，得到优化的状态转移方程为：mi,j=0 i=j i<j用类似的方法可以证明，对于最大得分问题，也可采用同样的优化方法。改进后的状态转移方程所需的计算时间为（程序及优化前后的运行结果比较见附件）上述方法利用四边形不等式推出最优决策的单调性，从而减少每个状态转移的状态数，降低算法的时间复杂度。上述方法是具有普遍性的。对于状态转移方程与式类似，且wi,j满足四边形不等式的动态规划问题，都可以采用相同的优化方法，如最优二叉排序树（NOI96）等。下面再举一例。例四、邮局(IOI2000)问题描述按照递增顺序给出

52、一条直线上坐标互不相同的n个村庄，要求从中选择p个村庄建立邮局，每个村庄使用离它最近的那个邮局，使得所有村庄到各自所使用的邮局的距离总和最小。试编程计算最小距离和，以及邮局建立方案。算法分析本题也是一道动态规划问题，详细分析请看文本附件（邮局解题报告）。将n个村庄按坐标递增依次编号为1，2，n，各个邮局的坐标为d1.n，状态表示描述为：mi,j表示在前j个村庄建立i个邮局的最小距离和。所以，mp,n即为问题的解，且状态转移方程和边界条件为：m1,j=w1,j ij其中wi,j表示在di.j之间建立一个邮局的最小距离和，可以证明，当仅建立一个邮局时，最优解出现在中位数，即设建立邮局的村庄为k，则

53、，于是，我们有： ， 同时，令si,j=k，记录使用前i-1个邮局的村庄数，便于在算出最小距离和之后构造最优建立方案。上述算法中wi,j可通过O(n)时间的预处理，在O(1)的时间内算出，所以，该算法的状态总数为O(n*p)，每个状态转移的状态数为O(n)，每次状态转移的时间为O(1)，该算法总的时间复杂度为O(p*n2)。算法优化本题的状态转移方程与式十分相似，因此我们猜想其决策是否也满足单调性，即si-1,jsi,jsi,j+1首先，我们来证明函数w满足四边形不等式，即： 设，下面分为两种情形，zy或z>y，下面仅讨论zy，z>y的情况是类似的。由izyj有： 接着，我们用数学

54、归纳法证明函数m也满足四边形不等式。对四边形不等式中“长度”l=j-i进行归纳：当i=i或j=j时，不等式显然成立。由此可知，当l1时，函数m满足四边形不等式。下面分两种情形进行归纳证明：情形1：i<i=j<j，即mi,j+mj,j mi,j，设k=maxp | mi,j=mi,p-1+mp,j+wi,j ，再分两种情形kj或k>j。下面只讨论kj，k>j的情况是类似的。情形2：i<i<j<j设 y=maxp | mi,j=mi-1,p+wp+1,j z=maxp | mi,j=mi-1,p+wp+1,j 仍需再分两种情形讨论，即zy或z>y。情

55、形2.1，当zy<j<j时：情形2.2，当i-1<i-1y<z<j时：最后，我们证明决策si,j满足单调性。为讨论方便，令mki,j=mi-1,k+wk+1,j；我们先来证明si-1,jsi,j，只要证明对于所有ik<k<j且mki-1,jmki-1,j，有：mki,jmki,j。类似地，我们可以证明一个更强的不等式mki-1,j-mki-1,jmki,j-mki,j也就是： mki-1,j+mki,jmki,j+mki-1,j利用递推定义式展开整理的：mi-2,k+mi-1,kmi-1,k+mi-2,k，这就是i-2<i-1<k<k

56、时m的四边形不等式。我们再来证明si,jsi,j+1，与上文类似，设k<k<j，则我们只需证明一个更强的不等式： mki,j-mki,jmki,j+1-mki,j+1也就是： mki,j+mki,j+1mki,j+1+mki,j利用递推定义式展开整理的：wk+1,j+wk+1,j+1wk+1,j+1+wk+1,j，这就是k+1<k+1<j<j+1时w的四边形不等式。综上所述，该问题的决策si,j具有单调性，于是优化后的状态转移方程为：m1,j=w1,j ij si,j=k同上文所述，优化后的算法时间复杂度为O(n*p)。（程序及优化前后的运行结果比较见附件） 四边

57、形不等式优化的实质是对结果的充分利用。它通过分析状态值之间的特殊关系，推出了最优决策的单调性，从而在计算当前状态时，利用已经计算过的状态所做出的最优决策，减少了当前的决策量。这就启发我们，在应用动态规划解题时，不仅可以实现状态值的充分利用，也可以实现最优决策的充分利用。这实际上是从另一个角度实现了“减少冗余”。2、决策量的优化：通过分析问题最优解所具备的性质，从而缩小有可能产生最优解的决策集合，也是减少每个状态可能转移的状态数的一种方法。大家所熟悉的NOI96中的添加号问题，正是从“所得的和最小”这一原则出发，仅在等分点的附近添加号，从而大大减少了每个状态转移的状态数，降低了算法的时间复杂度。让我们在再来看一例。例五、石子归并的最大得分问题问题描述 见例三，本例只考虑最大得分问题。算法分析 设n堆石子依次编号为1，2，.，n。