动态规划

应用

  • 0/1背包问题
  • 矩阵乘法链
  • 最短路径
  • 最长公共子序列

原理

  • 从算法设计的角度看,动态规划是一种在各个不同大小(size)的子问题的优化值之间建立递归关系并求解的过程;
  • 能用动态规划求解的问题必须满足优化原理:优化解包含的子问题的解也是优化的;
  • 利用优化原理,使用枚举法建立不同长度子问题的优化值之间的递归关系——动态规划方程;
  • 动态规划得到的是精确解;
  • 子问题的数目决定算法的复杂性;
  • 实现时要尽可能消去递归。

Example:多段图-最短路径

多段图

  • 多段图问题满足优化原理:最短路(1->3->5->7)上的子路径(3->5->7)是3到目的节点7在子图上的最短路;
  • 无论最短路的下一跳是{2,3,4}中的那个节点,其后的路径也应是最短路;
  • 节点1到目的的节点的最短路长度c(1)可从2,3,4到目的节点的最短路c(i)+节点1到这些节点的边成本cost(1,i)经枚举得到:c(1)=min{c(i)+cost(1,i)},i∈{2,3,4}。
  • 但2,3,4到目的节点的最短长度c(2),c(3),c(4)还不知道;
  • 我们需计算c(2),c(3),c(4);仍使用优化原理;
  • 一般情形:设c(i)为i到目的节点的最短路长度,A(i)为与i相邻的节点集合,有:c(i)=min{c(j)+cost(i,j)},j∈A(i);
  • 但c(i)由i到目的节点的子图在决定,和节点1怎样走到i没关系。

多段图的动态规划算法

  • 从c(7)开始向前计算;
  • 初始c(7)=0;
  • 依次计算c(6),c(5),…,c(1);
  • c(6)=1,c(5)=2;
  • c(4)=8+c(6);
  • c(3)=min{1+c(5),5+c(6)};
  • c(2)=min{7+c(5),6+c(6)};
  • c(1)=min{1+c(2),4+c(3),6+c(4)};
  • 递归还可以从前向后。

Example:0/1背包问题

  • 0/1背包问题的解指物品1,2,…,n的一种放法(x1,x2,…,xn的0/1赋值),使得效益值最大;
  • 假定背包容量不足以装入所有物品:面临选择;
  • 因为目标函数是非负数之和;
  • 优化原理:无论优化解是否放物品1,相对剩余背包容量,优化解对物品2,3,…,n的放法也是优化解。

背包问题满足的优化原理

优化值间的递归式

  • 虽然我们不知道优化解是否放物品1,但我们可以利用优化原理,从枚举"放"和"不放"两种情形建立优化值之间的递归式:
  • 设f(i,y)为以背包容量y,放物品i,i+1,…,n,得到优化效益值,一下递归关系成立:
  • f(1,c)=max{f(2,c),f(2,c-w1)+p1}(不放1和放1);
  • 先求子问题的优化值(递归),再从2种可能性中选出最优的;
  • 需求解:任意给定容量y,任意i,i+1,…,n种物品的子问题。

动态规划法步骤

  • 在应用动态规划法时,须先验证欲求解的问题是否满足优化原理;
  • 应用优化原理建立子问题优化解的值(优化值)之间的递归式;
  • 解优化值满足的递归式;
  • 回溯从优化值构造优化解;

算法复杂性

  • 直接用递归实现动态规划递归方程往往会引发大量重复计算,算法的计算量变得非常可观;最好使用迭代法实现动态规划算法;
  • 迭代实现需要存贮所有子问题的优化解的值f(i,y),以便避免重复计算,所以算法往往需要较大的存储空间;
  • 算法的复杂性来自子问题的数目,通常子问题的数目很大。

0/1背包问题DP算法的实现

1.递归实现

f(n,y)={Pnywn00y<wnf(n,y)=\begin{cases} Pn & y≥wn\\ 0 & 0≤y<wn \end{cases}

f(i,y)={max(f(i+1,y),f(i+1,ywi)+pi)ywif(i+1,y)0y<wif(i,y)=\begin{cases} max(f(i+1,y),f(i+1,y-wi)+pi) & y≥wi\\ f(i+1,y) & 0≤y<wi \end{cases}

说明:f(i,y)中,y≥wi的情况中,前者为不放i,后者为放i

Example:

递归调用树

2.权为整数的迭代实现

  • 当物品重量为整数时,可设计一相当简单的算法来求解f(1,c);
  • 该实现用二维数组 f [i] [y] 来保存每个f(i,y)的值,并且只计算一次;
  • 二维数组需Θ(nc)空间;
  • 函数Traceback从 f [i] [y] 产生优化的xi值;
  • Knapsack的复杂性Θ(nc),似乎是多项式算法。但因c的二进制输入长度为logc(2为底),所以nc仍是输入长度的指数函数;
  • Traceback的复杂性为Θ(n)。

Example:n=5,p=[6,3,5,4,6],w=[2,2,6,5,4],且c=10,求f(1,10)

i\y 0 1 2 3 4 5 6 7 8 9 10

缺点:

  1. 要求物品重量为整数;
  2. 当背包容量c很大时,例如c>2n,需要Ω(n*2n)。
  3. 下述元组法克服了上述缺点。

3.元组法实现

  • 元组法将函数f(i,y)的跳跃点以元组(y,f(i,y))形式存储于一个线性表P(i)中;

  • 表P(i)中的元组(y,f(i,y))按y的增序排列;

  • P(i)中的元组(a,b)表示:存在一种装物品{i,i+1,…,n}的方案,能以容量y,a≤y<a‘,a’为下一元组的横坐标,得到效益值b;

  • 下面给出从f(i+1,y)的线性表P(i+1)得出f(i,y)的线性表P(i)的算法;

  • 按f(i,y)的定义:f(i,y)=max{f(i+1,y),f(i+1,y-wi)+pi},首先需要从P(i+1)得到函数f(i+1,y)=f(i+1,y-wi)+pi的元组集合Q;

  • 设(a,b)∈Q,则(a-wi,b-pi)必为P(i+1)的元组,反之亦然。所以,P(i+1)的每个元组(w,p)对应Q的一个元组(w+wi,p+pi);

  • Q的元组(u,v)代表装物品{i,i+1,…,y}的元组(即P(i)的元组);

  • 从P(i+1)和Q得到P(i)的元组:

    因P(i+1)和Q内元组均按w和p的增序排列,所以可以用以前学过的merge算法进行合并;

  • 合并时使用以下支配(选优)规则:

    设(a,b)和(u,v)是来自P(i+1)和Q的元组,若a≥u且b<v,则称(a,b)受(u,v)支配;

    因为(a,b)代表以容量a得到效益值b的方案;

    而(u,v)代表以较少的容量u得到较大效益值v的方案;

  • 在合并时舍弃被支配的元组(选优)。

  • P(i+1)于Q合并,并按支配规则舍弃被支配的元组即可得到P(i);

  • 在产生P(i)时丢弃w>c的元组(w,v);

  • 得到P(2)后不再产生P(1):

    P(2)的最后一个元组是f(2,c)对应的元组;

    设线性表P(2)中满足w+w1≤c的最后一个元组为(w,v);

    将v+p1于P(2)的最后一个元组对应的效益值p做比较,效益值大的即为优化效益值f(1,c)。

Example:n=5,p=[6,3,5,4,6],w=[2,2,6,5,4],且c=10,求f(1,10)

方便起见,w=[2,2,6,5,4],p=[6,3,5,4,6],(横坐标为W,纵坐标为P)

  1. P(5)={(0,0),(4,6)}, Q={(5,4),(9,10)};

  2. P(4)={(0,0),(4,6),(9,10)}, delete(5,4), Q={(6,5),(10,11)};

  3. P(3)={(0,0),(4,6),(9,10),(10,11)}, delete(6,5), Q={(2,3),(8,8),(7,7),(6,9)};

  4. P(2)={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)};

  5. (w1,p1)=(2,6),P2中满足w+w1≤c的最后一个元组为(6,9);

    ∵ (2,6)+(6,9)>(10,11)

    ∴15为最大效益值,通过回溯法找到解为[1,1,0,0,1]

矩阵乘法链

  • m×n矩阵A于n×p矩阵B相乘需要做mnp个元素乘法;
  • 计算三个矩阵A,B和C的乘积ABC有两种方法:(AB)C和A(BC);
  • 结果相同,但所需元素乘法数不同;
  • 问题:对任意给定长度q的矩阵乘法链M1×M2,…,Mq,求优化的乘法顺序使得计算该乘法链所用的乘法数最少;
  • 长度为q的矩阵乘法链有指数量级Ω(2^q)的可能乘法顺序(有q个叶节点的二叉树的数目);

动态规划解

  • 用M(i,j)表示Mi×Mi+1×…×Mj(i≤j)的乘积。假设优化的矩阵乘法顺序最后计算乘积M(i,k)×M(k+1,j);

  • 则计算M(i,j)的优化乘法顺序在计算子链M(i,k)和M(k+1,j)时也是优化的;

  • 设c(i,j)为计算M(i,j)的优化乘法数(优化值),根据优化原理,优化值之间满足:

    c(i,j)=min{c(i,k)+c(k+1,j)+ri*r(k+1)*r(j+1)},i≤k<j;

    令kay(i,j)为达到最小值的k;

  • 可用上述递归式计算c(1,q);

  • 用kay(i,j)回溯找到优化的乘法顺序。

Example:q=5,r=(10,5,1,10,2,10)

递归

  1. c(1,5)=min{c(1,1)+c(2,5)+500, c(1,2)+c(3,5)+100, c(1,3)+c(4,5)+1000, c(1,4)+c(5,5)+200};
  2. c(2,5)=min{c(2,2)+c(3,5)+50, c(2,3)+c(4,5)+500, c(2,4)+c(5,5)+100};
  3. c(3,5)=min{c(3,3)+c(4,5)+100,c(3,4)+c(5,5)+20};
  4. c(4,5)=min{c(4,4)+c(5,5)+200}=200;
  5. c(3,5)=c(3,4)+c(5,5)+20=20+0+20=40;
  6. c(2,5)=c(2,2)+c(3,5)+50=0+40+50=90;
  7. c(1,5)=c(1,2)+c(3,5)+100=50+40+100=190;
  8. 解为M(1,2)×M(3,4)×M(5,5);

迭代:可避免大量重复计算,但需要O(q²)的存储空间,时间复杂度为Θ(q³)。

s=2,3,4;

s=2,计算c(1,3),c(2,4),c(3,5);

s=3,计算c(1,4),c(2,5);

s=4,计算c(1,5).

All-Pair最短路问题

  • 最短路径:设G为有向图,其中每条边都有一个成本(cost),图中每条有向路径的长度(或成本)定义为该路径上各边的成本之和;
  • 对于没对顶点(i,j),定义从i到j的所有路径中,具有最小长度的路径为从i到j的最短路;
  • All-Pair最短路问题:求每对点间的最短路;
  • 假定图上无负成本的环路,这是只需考虑简单路径,加上环路只会增加路径成本。

动态规划解:

  • 将节点按1到n编号;

  • 定义c(i,j,k)=i到j的中间节点编号不超过k的最短路长度,即包含节点i和j即节点1,2,…,k的子图上的最短路;

  • c(i,j,n)是在原来的图上i到j的最短路长度,即我们要求的最短路长度;

  • 因为只考虑简单路径,所以:

    c(i,k,k)=c(i,k,k-1);

    c(k,j,k)=c(k,j,k-1);

    c(i,i,k)=0 for all k;

  • 特别地,c(i,j,0)=cost(i,j)或∞。

Example:

  • 建立c(i,j,k)和c(i,j,k-1)之间的递归关系;

  • 对于任意k>0,i到j的中间节点编号不超过k的最短路上,或包含节点k或不包含节点k,所以有递归如下:

    c(i,j,k)=min{c(i,j,k-1),c(i,k,k-1)+c(k,j,k-1)};

  • 如果直接用递归程序求解上式,则计算c(i,j,n)的复杂度极高。利用迭代方法可将计算c值得时间减少到O(n)³。

迭代算法伪代码:

  • n令C(k)代表矩阵(c(i,j,k))i,j=1,…,n,因c(i,i,k)=0 for all k,所以矩阵C(k)的对角线元素为0.

  • n算法迭代计算C(k) ,k=0,…,n

  • n初始C(0)=(c(i, j)),即图的邻接矩阵,无边相连的i和j 令c(i, j)=∞.

  • n因c(i,k,k)=c(i,k,k-1),c(k,j,k)=c(k,j,k-1),所以,矩阵C(k)的k行、k列上的元素不变:

  • C(k)(i,k)=C(k-1)(i,k), C(k)(k,j)=C(k-1)(k,j).

  • n矩阵C(k)非k行、k列上的元素,按下式计算

  • C(k)(i,j)←min{C(k-1)(i, j), C(k-1)(i, k)+

  • C(k-1)(k,j)},

  • 即C(k)(i,j)←min{C(k-1)(i, j), C(k)(i, k)+

  • ​ C(k)(k,j)},

  • n所以算法只需使用一个矩阵,每次迭代时, 用第k列的i行元素和第k行的j列元素之和去更新元素C(k-1)(i, j).

  • n算法迭代至多n次,每次迭代需O(n2)时间,所以算法的时间复杂度为O(n3).

Example:最短路径

最短路径实例

解:

C(3)(1,2)=min{C(2)(1,2), C(2)(1,3)+C(2)(3,2)}=min{4, 6+7}=min{4, 13}=4;

C(3)(2,1)=min{C(2)(2,1), C(2)(2,3)+C(2)(3,1)}=min{6, 2+3}=min{6, 5}=5.

最长公共子序列问题

  • 首先需要说明,子序列与字串不同

    一个给定的序列的子序列,就是将给定序列中零个或多个元素去掉之后的结果;

    字串指给定串中任意个连续的字符组成的子序列;

  • 可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中,可以避免大量的重复计算;

  • 递归方程如下:

  • C(i,j)={0,ifi=0orj=0C[i1j1],ifi,j>0andxi=yimax{C[i,j1],c[i1,j]}ifi,j>0andxiyiC(i,j)=\begin{cases} 0,&if&i=0orj=0\\ C[i-1,j-1],&if&i,j>0andx_i=y_i\\ max\{C[i,j-1],c[i-1,j]\}&if&i,j>0andx_i≠y_i \end{cases}

Example:s1=[1,3,4,5,6,7,7,8],s2=[3,5,7,4,8,6,7,8,2]

下标j 0 1 2 3 4 5 6 7 8 9
下标i s2 3 5 7 4 8 6 7 8 2
0 s1 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0
2 3 0 1 1 1 1 1 1 1 1 1
3 4 0 1 1 1 2 2 2 2 2 2
4 5 0 1 2 2 2 2 2 2 2 2
5 6 0 1 2 2 2 2 3 3 3 3
6 7 0 1 2 3 3 3 3 4 4 4
7 7 0 1 2 3 3 3 3 4 4 4
8 8 0 1 2 3 3 4 4 4 5 5

右下角元素即为最长公共子序列长度,得到问题的解。