矩阵链乘问题
问题描述:
如何实现对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);
