矩陣鏈乘問(wèn)題
問(wèn)題描述:
如何實(shí)現(xiàn)對(duì)A1·A2·A3...An個(gè)矩陣鏈乘的打括號(hào)(分割), 使得其乘法次數(shù)m是最少的?
已知: A[x,y] B[y,z] 兩個(gè)矩陣相乘, 消耗的乘法次數(shù)是x · y · z次;
- 最優(yōu)子結(jié)構(gòu): 最后一次分割選擇了一個(gè)位置后, 左右兩個(gè)block的本身已經(jīng)應(yīng)該被最優(yōu)分割過(guò)了.
- 遞歸式:
m(i, j) = min{ m(i,k) + m(k+1,j) + p[i-1]·p[k]·p[j] } , 當(dāng)i<j;
m(i, j) = 0, 當(dāng)i=j- 其實(shí)從這個(gè)遞歸式能看出, 寫(xiě)算法的時(shí)候要有一個(gè)k循環(huán), 把k從k=i~j-1所有位置的可能情況都遍歷一遍, 找min;
- 寫(xiě)出自底向上的計(jì)算方法: 動(dòng)態(tài)規(guī)劃節(jié)省時(shí)間的奧秘在自底向上計(jì)算, 也就是和最開(kāi)始寫(xiě)最優(yōu)子結(jié)構(gòu)剛好相反, 從m(i, i) -> m(i, i+1) -> m(i, i+2)這樣算;
- 長(zhǎng)度l=1, 即只有一個(gè)矩陣的邊界情況, m(i, i) = 0 (i=1~n進(jìn)行遍歷)
- 長(zhǎng)度l=2, j = i+1, 有兩個(gè)矩陣, k只有一個(gè)值, 即取i, m(i, j) = p[i-1]·p[i]·p[j]; 同樣進(jìn)行遍歷, i = 1~n-1, j = 2~n
- 長(zhǎng)度l=3, j = i+2, 這次每個(gè)block有3個(gè)矩陣, k有i, i+1兩個(gè)取值, m(i, j) = min {k=i情形的值, k=i+1情形的值};
- 剩下以此類(lèi)推...一直到長(zhǎng)度l = n為止.
/*Matrix-Chain-Order*/
//@p: 從p[0]~p[n], 代表A[1]~A[n]矩陣的行數(shù)和列數(shù);
//其中, A[1]為p[0]xp[1]規(guī)模, A[x]為p[x-1]p[x]規(guī)模
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] 其實(shí)就是A[i]自己一個(gè)p[i-1]*p[i]規(guī)模的矩陣, 類(lèi)似于遞歸樹(shù)的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; //放一個(gè)無(wú)窮大值, 等著被替換;
for (k = i ~ k-1) //k: 代表砍下分割成兩個(gè)block的位置, 注意是在A[k]矩陣的右側(cè)分開(kāi)來(lái);
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;
時(shí)間復(fù)雜度: 有三層for循環(huán), 所以T(n) = Θ(n^3)
最優(yōu)二分搜索樹(shù)
問(wèn)題描述: a[1]~a[n]的關(guān)鍵字, 已知出現(xiàn)概率為p[1]~p[n], 另外落入a[i]兩側(cè)間隙的概率是q[0]~q[n], 求最小比較次數(shù)e和OBST的構(gòu)成; 其中q[i]代表是落入(i, i+1)區(qū)間的概率
最優(yōu)子結(jié)構(gòu): 最頂層根節(jié)點(diǎn)選擇了a[1]~a[n]其中一個(gè)以后, 左右子樹(shù)都也已經(jīng)是最優(yōu)子樹(shù)了.
遞歸式: e(i, j) =
(1) min { e(i, k-1) + e(k+1, j) + [ p[k]·1+w(i, k-1)+w(k+1, j) ] } , 當(dāng)i<=j (note: 此處中括號(hào)中的部分可以化為w(i, j) )
(2) q(i-1) , 當(dāng)i>j (比如e(4, 3)這樣)-
寫(xiě)出自底向上的計(jì)算方法: 這時(shí)候要用相反的思路, 從樹(shù)底層往上算, 底層是那些偽結(jié)點(diǎn), 也就是q[0]~q[n]代表的結(jié)點(diǎn)
- 長(zhǎng)度l=0, 是邊界條件情況, e[i, i-1] = q[i-1] , 讓i = 1~n+1遍歷一下, 從而過(guò)完q[0]~q[n]; 也不要忘了把輔助的"概率和的矩陣"w[i, i-1] = q[i-1]一起過(guò)一下;
- 長(zhǎng)度l=1, k只能取i, 所以e[i, i] = e[1, 0] + e[2, 1] + w[1, 1], 同樣讓i = 1~n遍歷一下;
- 長(zhǎng)度l=2, k能取i, i+1=j兩個(gè)值, 所以e[i, j] = min{ k=i情形, k=i+1情形 };
- 剩下以此類(lèi)推...一直到長(zhǎng)度l = n 為止;
/*Optimal-Binary-Search-Tree*/
//@p: p[n]存放著a[1]~a[n]關(guān)鍵詞出現(xiàn)的概率
//@q: q[n+1]存放著q[0]~q[n]的落入缺失區(qū)間的概率
//即q[i]是落入(a[i],a[i+1]) 開(kāi)區(qū)間的概率
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ú)窮大
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;
時(shí)間復(fù)雜度: 因?yàn)橛腥龑觙or循環(huán), 所以T(n)=Θ(n^3);
