第二节　动态规划

    动态规划是近来发展较快的一种组合算法，是运筹学的一个分支，是解决多阶段决策过程最优化的一种数学方法。我们可以用它来解决最优路径问题，资源分配问题，生产调度问题，库存问题，装载问题，排序问题，设备更新问题，生产过程最优控制问题等等。

   在生产和科学实验当中，有一类活动的过程，可将它分成若干个阶段，在它的每个阶段要作出决策，从而使全局达到最优。当各个阶段决策确定后，就组成一个决策序列，因而也就决定了整个过程的一条活动路线。这种把一个过程看作一个前后相关具有链状结构的多阶段过程就称为多阶段决策过程。

   所谓动态是指在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生，故有"动态"的含义。

   下面，我们结合最短路径问题来介绍动态规划的基本思想。

   求下图中点O到点U的最短距离(假设只许往上和往右走)。

    从点O到点U，可以按经过的路径，分成七个阶段，分别为：O->AB->CDE->FGHJ->

KLMN->PQR->ST->U。

   最短路径有一个重要特性：如果点O经过点H到达点U是一条最短路径，则在这条最优路径上由点H出发到达点U的子路径，是由点H出发到达点U所有可能选择的不同路径的最短路径(证明略)。根据这一特点，寻找最短路径的时候，可以从最后一段开始，用由后向前逐段递推的方法，求出个点到点U的最短路径。

   如若考虑到从点O到点U的最短路径，也是该路径上个点到点的最短路径，令O点到U点的最短距离为dO，A点到U点的最短距离为dA，...，故有：

           dO=min{2+dA，1+dB}，

           dA=min{3+dC，2+dD}，

           dB=min{2+dD，3+dE}，

           ................

           dQ=min{5+dT，2+dS}.

   下面按照动态规划的方法，将上例从最后一段开始计算，由后向前逐步递推移至O点。计算步骤如下：

   阶段7：从S点或T点到达U点，这时各自只有一种选择，故：

           dS=2;dT=3;

   阶段6：出发点有P，Q，R三个，其中Q点到达U点有两种选择，或是经过S点，或是经过T点，故：

           dQ=min{2+dS，5+dT}=min{4，8}=4;

           dP=min{1+dS}=min{3}=3;

           dR=min{3+dT}=min{6}=6;

   阶段5：出发点有K，L，M，N四个，同理有：

           dK=min{3+dP}=min{6}=6;

           dL=min{2+dP，4+dq}=min{5，8}=5;

           dM=min{2+dQ，4+dR}=min{6，10}=6;

           dN=min{4+dR}=min{10}=10;

   阶段4：出发点有F，G，H，J四个，同理有：

           dF=min{2+dK}=min{8}=8;

           dG=min{1+dK，3+dL}=min{7，8}=7;

           dH=min{1+dL，1+d}=min{6，7}=6;

           dJ=min{3+dM，3+dN}=min{9，13}=9;

   阶段3：出发点有C，D，E三个，同理有：

           dC=min{2+dF，2+dG}=min{10，9}=9;

           dD=min{4+dG，2+dH}=min{11，8}=8;

           dE=min{1+dH，2+dJ}=min{7，11}=7;

   阶段2：出发点有A，B两个，同理有：

           dA=min{3+dC，2+dD}=min{12，10}=10;

           dB=min{2+dD，3+dE}=min{10，10}=10;

   阶段1：出发点是O，同理有：

           dO=min{2+dA，1+dB}=min{12，11}=11.

   由此得到全过程的最短路径是11，并且可以由以上推导过程反推得最短的路线是：O->B->D->H->L->P->S->U;或O->B->E->H->L->P->S->U。

   从上可以知道，能应用动态规划解决的问题，必须满足最优性原则，动态规划的关键在于正确的写出基本的递推关系式和恰当的边界条件。它需要把问题的过程化成几个互相联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，都利用到前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整个问题的最优解。

例一、数字三角形：下图给出了一个数字三角形.请编一个程序计算从顶至底的某处的一条路径，使得该路径所经过的数字的总和最大。对于路径规定如下：

    (1)每一步可沿左斜线向下走或右斜线向下走;                  ⑦       

    (2)1<三角形的行数<=100;                                 ③   8     

    (3)三角形中的数字为整数0，1，...，99;                  ⑧   1   0   

    输入数据：由文件INPUT.TXT中首先读出的            2   ⑦   4   4 

是三角形的行数。在例子中INPUT.TXT表示如下：        4   ⑤   2   6   5

     5       

     7       

     3 8     

     8 1 0   

     2 7 4 4    

     4 5 2 6 5   

    输出最大的总和。如上例为：30(其路径如图圈的数字)。

分析：(1)假设最优路径(即总和最大)为⑦→③→⑧→⑦→⑤，则子路径⑦→③→⑧→⑦必定是从初始点⑦到中间点⑦的所有路径中最优的，否则，如果从初始点⑦到中间点⑦还有另一条的路径更优，假设为⑦→a1→a2→⑦，则新路径⑦→a1→a2→⑦→⑤则优于原来假设的最优路径⑦→③→⑧→⑦→⑤，与假设矛盾。从以上反证法可以清楚地知道：数字三角形问题满足动态规划的最优性原则，可以利用动态规划求解。

    (2)采用顺推法：记第i行第j列的数字为a(i，j)，从初始点到a(i，j)的最大总和记为f(i，j);则应有第一层上的数字的a(1，1)的最大总和为它本身，即：

    f(1，1)=a(1，1);

以下各层按如下方法递推：

    f(i，j)=a(i，j)+max{f(i-1，j-1)，f(i-1，j)}

   (3)用以上方法递推计算完最后一层，最后一中寻最大值即为本题的解.

解：Pascal程序：

Program lt10_2_1;

uses crt;

const max=100;

var n：integer;

    a：array[0..max，0..max] of longint;

procedure work;

  var f：text;

      i，j：integer;

  begin

    assign(f，'input.txt');

    reset(f);

    readln(f，n);

    fillchar(a，sizeof(a)，0);

    for i：=1 to n do

      for j：=1 to i do

        begin

          read(f，a[i，j]);

          if a[i-1，j-1]>a[i-1，j] then

             a[i，j]：=a[i，j]+a[i-1，j-1]

             else a[i，j]：=a[i，j]+a[i-1，j];

        end;

    close(f);

  end;

procedure print;

  var max：longint;

      i：integer;

  begin

    max：=0;

    for i：=1 to n do

      if a[n，i]>max then max：=a[n，i];

    writeln('Max='，max);

  end;

begin

  clrscr;

  work;print;

end.

习题二：

1、某工业生产部门根据国家计划的安排，拟将某种高效率的五台机器，分配给所属的A，B，C三个工厂，各工厂若获得这种机器后，可以为国家盈利如下表，问：这五台机器如何分配给各工厂，才能使国家盈利最大?

     单位：万元

   其中：p为盈利，s为机器台数。

2、己知：f(x)=x1^2+2x2^2+x3^2-2x1-4x2-2x3

       x1+x2+x3=3 且 x1，x2，x3均为非负整数。

  求f(x)的最小值。

3、N块银币中有一块不合格，不合格的银币较正常为重，现用一天平找出不合格的来，要求最坏情况不用天平的次数最少。

4、某一印刷厂有6项加工任务，对印刷车间和装订车间所需时间见下表：

     时间单位：天

     完成每项任务都要先去印刷车间印刷，再到装订车间装订。问怎样安排这6项加工任务的加工工序，使得加工总工时最少。

5、有一个由数字1，2，...，9组成的数字串(长度不超过200)，问如何M(1<=M<=20)个加号插入这个数字串中，使得所形成的算术表达式的值最小。

注意：(1)加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻;

     (2)M保证小于数字串的长度。

  例如：数字串79846，若需加入两个加号，则最佳方案是79+8+46，算术表达式的值是133。

  输入格式：从键盘读入输入文件名。数字串在输入文件的第一行行首(数字串中间无空格且不换行)，M的值在输入文件的第二行行首。

  输出格式：在屏幕上输出最小的和。