(7) 动态规划(下) 矩阵链乘与OBST树

矩阵链乘问题

问题描述:
如何实现对A1·A2·A3...An个矩阵链乘的打括号(分割), 使得其乘法次数m是最少的?
已知: A[x,y] B[y,z] 两个矩阵相乘, 消耗的乘法次数是x · y · z次;

• 最优子结构: 最后一次分割选择了一个位置后, 左右两个block的本身已经应该被最优分割过了.
• 递归式:
  m(i, j) = min{ m(i,k) + m(k+1,j) + p[i-1]·p[k]·p[j] } , 当i<j;
  m(i, j) = 0, 当i=j
  • 其实从这个递归式能看出, 写算法的时候要有一个k循环, 把k从k=i~j-1所有位置的可能情况都遍历一遍, 找min;
• 写出自底向上的计算方法: 动态规划节省时间的奥秘在自底向上计算, 也就是和最开始写最优子结构刚好相反, 从m(i, i) -> m(i, i+1) -> m(i, i+2)这样算;
  • 长度l=1, 即只有一个矩阵的边界情况, m(i, i) = 0 (i=1~n进行遍历)
  • 长度l=2, j = i+1, 有两个矩阵, k只有一个值, 即取i, m(i, j) = p[i-1]·p[i]·p[j]; 同样进行遍历, i = 1~n-1, j = 2~n
  • 长度l=3, j = i+2, 这次每个block有3个矩阵, k有i, i+1两个取值, m(i, j) = min {k=i情形的值, k=i+1情形的值};
  • 剩下以此类推...一直到长度l = n为止.

/*Matrix-Chain-Order*/
//@p: 从p[0]~p[n], 代表A[1]~A[n]矩阵的行数和列数;
//其中, A[1]为p[0]xp[1]规模, A[x]为p[x-1]p[x]规模
Matrix-Chain-Order(int p[])
n = p.length-1;
let m[1~n][1~n] and s[1~n][1~n] be new arrays;
for (i = 1~n)
    m[i][i] = 0;  //m[i][i] 其实就是A[i]自己一个p[i-1]*p[i]规模的矩阵, 类似于递归树的T(1)根部情形;
for (l = 2 ~ n)  // l: length
    for (i = 1 ~ n-l+1)  //i: head of a block;
        j = i+l-1;  //j: end of a block;
        m[i][j] = 9999;  //放一个无穷大值, 等着被替换;
        for (k = i ~ k-1)  //k: 代表砍下分割成两个block的位置, 注意是在A[k]矩阵的右侧分开来;
            q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
            if (q <= m[i][j])
                m[i][j] = q;
                s[i][j] = k; //记录分割位置;
return m, s arrays;

时间复杂度: 有三层for循环, 所以T(n) = Θ(n^3)

最优二分搜索树

问题描述: a[1]~a[n]的关键字, 已知出现概率为p[1]~p[n], 另外落入a[i]两侧间隙的概率是q[0]~q[n], 求最小比较次数e和OBST的构成; 其中q[i]代表是落入(i, i+1)区间的概率

• 最优子结构: 最顶层根节点选择了a[1]~a[n]其中一个以后, 左右子树都也已经是最优子树了.

• 递归式: e(i, j) =
  (1) min { e(i, k-1) + e(k+1, j) + [ p[k]·1+w(i, k-1)+w(k+1, j) ] } , 当i<=j (note: 此处中括号中的部分可以化为w(i, j) )
  (2) q(i-1) , 当i>j (比如e(4, 3)这样)

• 写出自底向上的计算方法: 这时候要用相反的思路, 从树底层往上算, 底层是那些伪结点, 也就是q[0]~q[n]代表的结点

  • 长度l=0, 是边界条件情况, e[i, i-1] = q[i-1] , 让i = 1~n+1遍历一下, 从而过完q[0]~q[n]; 也不要忘了把辅助的"概率和的矩阵"w[i, i-1] = q[i-1]一起过一下;
  • 长度l=1, k只能取i, 所以e[i, i] = e[1, 0] + e[2, 1] + w[1, 1], 同样让i = 1~n遍历一下;
  • 长度l=2, k能取i, i+1=j两个值, 所以e[i, j] = min{ k=i情形, k=i+1情形 };
  • 剩下以此类推...一直到长度l = n 为止;

/*Optimal-Binary-Search-Tree*/
//@p: p[n]存放着a[1]~a[n]关键词出现的概率
//@q: q[n+1]存放着q[0]~q[n]的落入缺失区间的概率
//即q[i]是落入(a[i],a[i+1]) 开区间的概率
Optimal-BST(p[], q[], n)
let e[1~n+1][0~n], w[1~n+1][0~n], root[1~n][1~n] be new arrays;
for (i = 1~n+1)
    e[i][i-1] = q[i-1];  //边界情况, 覆盖了落入小于a[i]的情形
    w[i][i-1] = q[i-1]; 
for (l = 1~n)
    for (i = 1~n-l+1)    //i是头部
        j = i+l-1;  //j是尾部
        e[i][j] = 9999;  //让e[i][j]无穷大
        w[i][j] = w[i][j-1] + p[j] + q[j]
        for (k = i~j)
            t = e[i, k-1] + e[k+1, j] + w[i][j];
            if (t<=e[i][j])
                e[i][j] = t;
                root[i][j] = k;
return e, root arrays;

时间复杂度: 因为有三层for循环, 所以T(n)=Θ(n^3);