第五章 动态规划

• 动态规划算法与分治法类似，其基本思想也是将求解问题分解为若干个子问题。与分治法不同的是，动态规划问题中子问题不是独立的，可能重复计算，所以动态规划旨在优化问题减少重复子问题的计算。
• 简言之，动态规划的实质是分治和消除冗余。

矩阵链相乘

• 假设我们要计算三个矩阵的乘积即，这个矩阵的维数分别为，我们可以有两种方式。前者需要次乘法，后者需要次乘法。可见对于个矩阵链乘的耗费，取决于个乘法的执行顺序。下面我们讨论找出个矩阵链相乘的最小数乘次数。

Catalan数

• 设是求个矩阵相乘的所有放置括弧的方法数。对于，对于前个矩阵有种放置方法，对于余下的有种放置方法，总共有种放置方法，则对于个矩阵的所有放置方法数：

  ，显然（两个矩阵只有一种乘法，三个矩阵有两种乘法），我们假定，可以证明：。

• 上述递推式产生了Catalan数，定义，它的前项为：。因此矩阵个数逐渐变大时，采用简单的暴力算法是十分低效的。

最小矩阵链乘数MATCHCHAIN

• 对于每个，矩阵的列数一定等于矩阵的行数。因此我们指定维数，其中分别表示矩阵的行数和列数（最右边的矩阵的列数与前面无关，所以会有）。并且，我们用表示的乘积，的数量乘法耗费记为。

• 设，那么有。显然这样按划分后，（实际上也是两个维数分别为的新矩阵相乘）。

• 于是我们得到，对于求，则我们需要解决递推式。

• 为避免重复计算，考虑到，我们将计算二维数组的右上半部分（对角线向上计算），最终下图中的即为所求。

  zeO8P0.png

  • 例：给出个矩阵如下：（表示第一条对角线）

    

    易知，上的元素均为；

    

    • 

    

    • 

    ······

    

    • 
    • 
    • 

    ······依次计算得到如下表格：

    0	1	2	3	4
    C[1,1]=0	C[1,2]=200	C[1,3]=320	C[1,4]=620	C[1,5]=348
    	C[2,2]=0	C[2,3]=240	C[2,4]=640	C[2,5]=248
    		C[3,3]=0	C[3,4]=240	C[3,5]=168
    			C[4,4]=0	C[4,5]=120
    				C[5,5]=0

MATCHCHAIN

输入：n个矩阵的链的维数对应于正整数数组r[1···n+1]。

输出：n个矩阵相乘的数量乘法最小次数。

for i <- 1 to n
    C[i,i] <- 0 #对角线0的元素填充0
end for
for d <- 1 to n-1 #遍历n条对角线
    for i <- 1 to n-d #遍历第d条对角线的所有元素
        j <- i+d
        C[i,j] <- infty
        for k <- i+1 to j #尝试所有可能的k值求min
            C[i,j] <- min{C[i,j], C[i,k-1]+C[k,j]+r[i]r[k]r[j+1]}
        end for
    end for
end for
return C[1,n]

• 观察MATCHCHAIN算法易知，三层循环嵌套，时间复杂度为，算法的空间复杂度取决于所需要的数组，即。

0/1背包问题

• 背包问题的定义如下：设是项物品的集合，现要将他们放入一个容量为的背包中，对于第个物品，分别表示其体积和价值。

  数学化描述：给出有项元素的集合，找出一个子集合，使得在约束条件下最大。

• 之所以被称为0/1背包问题，是因为对于集合的每个物品，要么被选中，要么不被选中。

• 为了装满背包我们给出以下递推式，设表示从前项中取出物品放入体积为的背包的最大价值（）。显然，因为对于所有体积为的背包，从个物品中取得的最大价值为；因为对于体积为的背包，前项物品无法放入该背包。

  

  • ：当时，不能再容纳更多的物品，所以就为的价值；
  • ：当时，可以容纳第个物品，但要腾出的体积去容纳第个物品。

• 例：有容量为的背包，要装入种体积为的物品，它们的价值分别是，即物品。

  znQoPs.png

  • 对于的行和列全部填；

  • ，放入物品，由于，所以从开始考虑，填入其价值；

  • ，放入物品，由于，所以从开始考虑，得到更新；，均可得到更新；

  • ，放入物品，从开始考虑，显然把（5）取出放入（4）的价值是缩小的······；直到，可以同时放入价值最大为；

  • ，放入物品，从开始考虑，所以更新；对于，取出放入的价值更大，······

    ······

  • 最终依据表格，选择价值最大为；

背包KNAPSACK算法

KNAPSACK

输入：物品集合U={u1, u2,..., un}，体积分别为s1, s2,..., sn，价值分别为v1, v2,..., vn，容量为C的背包。

输出：在约束条件下最大，。

for i <- 0 to n
    V[i,0] <- 0 
end for
for j <- 0 to C
    V[0,j] <- 0
end for
for i <- 1 to n
    for j <- 1 to C
        V[i,j] <- V[i-1,j]
        if si <= j then V[i,j] <- max{V[i,j], V[i-1,j-si]+vi}
    end for
end for
return V[n,C]

• 由于计算表格中的每一项需要的时间，所以KNAPSACK算法的时间复杂度为，空间复杂度为。

所有点对的最短路径问题

• 设是一个有向图，问题描述为：找出每个顶点到其他所有顶点的距离，这里到的距离是指从到的最短路径长度。
• 为方便研究，设个顶点在集合中，顶点的距离为。初始时，就是有向图的边长，若不直接连通则。

Floyd算法

• 对于任意两个顶点，它们可以通过其他顶点间接连通，所以我们可以通过比较直接连通的长度与通过顶点间接连通的长度，选取较小值。当然，顶点间接连通不一定只经过一个顶点，这是一个递归过程。

• 开始时，如果并且是中的边，则置，否则置。然后顺序迭代次，表示从顶点到的距离，且经过的中间顶点编号不大于，则：

  

FLOYD

输入：以矩阵表示的有向图G。

输出：矩阵D，使得D[i,j]表示顶点i到顶点j的距离。

D <- l #将l复制到矩阵D
for k <-  1 to n
    for i <- 1 to n
        for j <- 1 to n
            D[i,j]=min{D[i,j], D[i,k]+D[k,j]} #看是原距离更小，还是加入顶点k后更小
        end for
    end for
end for
return D

• 例如，考虑如下有向图，求矩阵。

  zn8nJJ.png

  • 即为有向图（中的，图片错误）；

  • ，以为媒介重新计算距离，对于，若借助顶点距离为所以不变；对于，借助顶点距离为得到更新；

    ······

zn8uW9.png

• FLOYD算法是三重循环嵌套，时间复杂度为。需要二维数组，空间复杂度为。