動(dòng)態(tài)規(guī)劃是本書介紹的五種算法設(shè)計(jì)方法中難度最大的一種，它建立在最優(yōu)原則的基礎(chǔ)上。采用動(dòng)態(tài)規(guī)劃方法，可以優(yōu)雅而高效地解決許多用貪婪算法或分而治之算法無法解決的問題。在介紹動(dòng)態(tài)規(guī)劃的原理之后，本章將分別考察動(dòng)態(tài)規(guī)劃方法在解決背包問題、圖象壓縮、矩陣乘法鏈、最短路徑、無交叉子集和元件折疊等方面的應(yīng)用。
3.1 算法思想
和貪婪算法一樣，在動(dòng)態(tài)規(guī)劃中，可將一個(gè)問題的解決方案視為一系列決策的結(jié)果。不同的是，在貪婪算法中，每采用一次貪婪準(zhǔn)則便做出一個(gè)不可撤回的決策，而在動(dòng)態(tài)規(guī)劃中，還要考察每個(gè)最優(yōu)決策序列中是否包含一個(gè)最優(yōu)子序列。
例3-1 [最短路經(jīng)] 考察圖1 2 - 2中的有向圖。假設(shè)要尋找一條從源節(jié)點(diǎn)s= 1到目的節(jié)點(diǎn)d= 5的最短路徑，即選擇此路徑所經(jīng)過的各個(gè)節(jié)點(diǎn)。第一步可選擇節(jié)點(diǎn)2，3或4。假設(shè)選擇了節(jié)點(diǎn)3，則此時(shí)所要求解的問題變成：選擇一條從3到5的最短路徑。如果3到5的路徑不是最短的，則從1開始經(jīng)過3和5的路徑也不會(huì)是最短的。例如，若選擇的子路徑（非最短路徑）是3，2，5 (耗費(fèi)為9 )，則1到5的路徑為1，3，2，5 (耗費(fèi)為11 )，這比選擇最短子路徑3，4，5而得到的1到5的路徑1，3，4，5 (耗費(fèi)為9) 耗費(fèi)更大。
所以在最短路徑問題中，假如在的第一次決策時(shí)到達(dá)了某個(gè)節(jié)點(diǎn)v，那么不管v 是怎樣確定的，此后選擇從v 到d 的路徑時(shí)，都必須采用最優(yōu)策略。
例3-2 [0/1背包問題] 考察1 3 . 4節(jié)的0 / 1背包問題。如前所述，在該問題中需要決定x1 .. xn的值。假設(shè)按i = 1，2，.，n 的次序來確定xi 的值。如果置x1 = 0，則問題轉(zhuǎn)變?yōu)橄鄬?duì)于其余物品（即物品2，3，.，n），背包容量仍為c 的背包問題。若置x1 = 1，問題就變?yōu)殛P(guān)于最大背包容量為c-w1 的問題。現(xiàn)設(shè)r?{c，c-w1 } 為剩余的背包容量。
在第一次決策之后，剩下的問題便是考慮背包容量為r 時(shí)的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之后的一個(gè)最優(yōu)方案，如果不是，則會(huì)有一個(gè)更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一個(gè)更好的方案。
假設(shè)n=3, w=[100,14,10], p=[20,18,15], c= 11 6。若設(shè)x1 = 1，則在本次決策之后，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因?yàn)閇x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 并非最優(yōu)策略。即x= [ 1，0，1] 可改進(jìn)為x= [ 1，1，0 ]。若設(shè)x1 = 0，則對(duì)于剩下的兩種物品而言，容量限制條件為11 6。總之，如果子問題的結(jié)果[x2，x3 ]不是剩余情況下的一個(gè)最優(yōu)解，則[x1，x2，x3 ]也不會(huì)是總體的最優(yōu)解。
例3-3 [航費(fèi)] 某航線價(jià)格表為：從亞特蘭大到紐約或芝加哥，或從洛杉磯到亞特蘭大的費(fèi)用為$ 1 0 0；從芝加哥到紐約票價(jià)$ 2 0；而對(duì)于路經(jīng)亞特蘭大的旅客，從亞特蘭大到芝加哥的費(fèi)用僅為$ 2 0。從洛杉磯到紐約的航線涉及到對(duì)中轉(zhuǎn)機(jī)場(chǎng)的選擇。如果問題狀態(tài)的形式為（起點(diǎn)，終點(diǎn)），那么在選擇從洛杉磯到亞特蘭大后，問題的狀態(tài)變?yōu)椋▉喬靥m大，紐約）。從亞特蘭大到紐約的最便宜航線是從亞特蘭大直飛紐約，票價(jià)$ 1 0 0。而使用直飛方式時(shí)，從洛杉磯到紐約的花費(fèi)為$ 2 0 0。不過，從洛杉磯到紐約的最便宜航線為洛杉磯-亞特蘭大-芝加哥-紐約，其總花費(fèi)為$ 1 4 0（在處理局部最優(yōu)路徑亞特蘭大到紐約過程中選擇了最低花費(fèi)的路徑：亞特蘭大-芝加哥-紐約）。
如果用三維數(shù)組（t a g，起點(diǎn)，終點(diǎn)）表示問題狀態(tài)，其中t a g為0表示轉(zhuǎn)飛， t a g為1表示其他情形，那么在到達(dá)亞特蘭大后，狀態(tài)的三維數(shù)組將變?yōu)椋?0，亞特蘭大，紐約），它對(duì)應(yīng)的最優(yōu)路徑是經(jīng)由芝加哥的那條路徑。
當(dāng)最優(yōu)決策序列中包含最優(yōu)決策子序列時(shí)，可建立動(dòng)態(tài)規(guī)劃遞歸方程（ d y n a m i c -programming recurrence equation），它可以幫助我們高效地解決問題。
例3-4 [0/1背包] 在例3 - 2的0 / 1背包問題中，最優(yōu)決策序列由最優(yōu)決策子序列組成。假設(shè)f (i,y) 表示例1 5 - 2中剩余容量為y，剩余物品為i，i + 1，.，n 時(shí)的最優(yōu)解的值，即：和利用最優(yōu)序列由最優(yōu)子序列構(gòu)成的結(jié)論，可得到f 的遞歸式。f ( 1 ,c) 是初始時(shí)背包問題的最優(yōu)解。可使用（ 1 5 - 2）式通過遞歸或迭代來求解f ( 1 ,c)。從f (n, * )開始迭式， f (n, * )由（1 5 - 1）式得出，然后由（ 1 5 - 2）式遞歸計(jì)算f (i,*) ( i=n- 1，n- 2，.， 2 )，最后由（ 1 5 - 2）式得出f ( 1 ,c)。
對(duì)于例1 5 - 2，若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用遞歸式（1 5 - 2），可得f (2, y) = 0 ( 0≤y＜10 )；f（2，y）= 1 5（1 0≤y＜1 4）；f（2，y）= 1 8（1 4≤y＜2 4）和f（2，y）= 3 3（y≥2 4）。因此最優(yōu)解f ( 1 , 11 6 ) = m a x {f（2，11 6），f（2，11 6 - w1）+ p1} = m a x {f（2，11 6），f（2，1 6）+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
現(xiàn)在計(jì)算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩余容量c-w1中尋求最優(yōu)解，用f (2, c-w1) 表示最優(yōu)解。依此類推，可得到所有的xi (i= 1.n) 值。
在該例中，可得出f ( 2 , 11 6 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計(jì)算x2 及x3，此時(shí)r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時(shí)r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。
動(dòng)態(tài)規(guī)劃方法采用最優(yōu)原則（ principle of optimality）來建立用于計(jì)算最優(yōu)解的遞歸式。所謂最優(yōu)原則即不管前面的策略如何，此后的決策必須是基于當(dāng)前狀態(tài)（由上一次決策產(chǎn)生）的最優(yōu)決策。由于對(duì)于有些問題的某些遞歸式來說并不一定能保證最優(yōu)原則，因此在求解問題時(shí)有必要對(duì)它進(jìn)行驗(yàn)證。若不能保持最優(yōu)原則，則不可應(yīng)用動(dòng)態(tài)規(guī)劃方法。在得到最優(yōu)解的遞歸式之后，需要執(zhí)行回溯（t r a c e b a c k）以構(gòu)造最優(yōu)解。
編寫一個(gè)簡(jiǎn)單的遞歸程序來求解動(dòng)態(tài)規(guī)劃遞歸方程是一件很誘人的事。然而，正如我們將在下文看到的，如果不努力地去避免重復(fù)計(jì)算，遞歸程序的復(fù)雜性將非常可觀。如果在遞歸程序設(shè)計(jì)中解決了重復(fù)計(jì)算問題時(shí)，復(fù)雜性將急劇下降。動(dòng)態(tài)規(guī)劃遞歸方程也可用迭代方式來求解，這時(shí)很自然地避免了重復(fù)計(jì)算。盡管迭代程序與避免重復(fù)計(jì)算的遞歸程序有相同的復(fù)雜性，但迭代程序不需要附加的遞歸棧空間，因此將比避免重復(fù)計(jì)算的遞歸程序更快。
3.2 應(yīng)用
3.2.1 0/1背包問題
1. 遞歸策略
在例3 - 4中已建立了背包問題的動(dòng)態(tài)規(guī)劃遞歸方程，求解遞歸式（ 1 5 - 2）的一個(gè)很自然的方法便是使用程序1 5 - 1中的遞歸算法。該模塊假設(shè)p、w 和n 為輸入，且p 為整型，F(xiàn)(1,c) 返回f ( 1 ,c) 值。
程序15-1 背包問題的遞歸函數(shù)
int F(int i, int y)
{// 返回f ( i , y ) .
if (i == n) return (y < w[n]) ? 0 : p[n];
if (y < w[i]) return F(i+1,y);
return max(F(i+1,y), F(i+1,y-w[i]) + p[i]);
}
程序1 5 - 1的時(shí)間復(fù)雜性t (n)滿足：t ( 1 ) =a；t（n）≤2t（n- 1）+b（n＞1），其中a、b 為常數(shù)。通過求解可得t (n) =O( 2n)。
例3-5 設(shè)n= 5，p= [ 6 , 3 , 5 , 4 , 6 ]，w=[2,2,6,5,4] 且c= 1 0 ,求f ( 1 , 1 0 )。為了確定f ( 1 , 1 0 )，調(diào)用函數(shù)F ( 1 , 1 0 )。遞歸調(diào)用的關(guān)系如圖1 5 - 1的樹型結(jié)構(gòu)所示。每個(gè)節(jié)點(diǎn)用y值來標(biāo)記。對(duì)于第j層的節(jié)點(diǎn)有i=j，因此根節(jié)點(diǎn)表示F ( 1 , 1 0 )，而它有左孩子和右孩子，分別對(duì)應(yīng)F ( 2 , 1 0 )和F ( 2 , 8 )。總共執(zhí)行了2 8次遞歸調(diào)用。但我們注意到，其中可能含有重復(fù)前面工作的節(jié)點(diǎn)，如f ( 3 , 8 )計(jì)算過兩次，相同情況的還有f ( 4 , 8 )、f ( 4 , 6 )、f ( 4 , 2 )、f ( 5 , 8 )、f ( 5 , 6 )、f ( 5 , 3 )、f (5,2) 和f ( 5 , 1 )。如果保留以前的計(jì)算結(jié)果，則可將節(jié)點(diǎn)數(shù)減至1 9，因?yàn)榭梢詠G棄圖中的陰影節(jié)點(diǎn)。
正如在例3 - 5中所看到的，程序1 5 - 1做了一些不必要的工作。為了避免f (i,y)的重復(fù)計(jì)算，必須定義一個(gè)用于保留已被計(jì)算出的f (i,y)值的表格L，該表格的元素是三元組(i,y,f (i,y) )。在計(jì)算每一個(gè)f (i,y)之前，應(yīng)檢查表L中是否已包含一個(gè)三元組(i,y, * )，其中*表示任意值。如果已包含，則從該表中取出f (i,y)的值，否則，對(duì)f (i,y)進(jìn)行計(jì)算并將計(jì)算所得的三元組(i,y,f (i,y) )加入表L。L既可以用散列（見7 . 4節(jié)）的形式存儲(chǔ)，也可用二叉搜索樹(見11章)的形式存儲(chǔ)。
2. 權(quán)為整數(shù)的迭代方法
當(dāng)權(quán)為整數(shù)時(shí)，可設(shè)計(jì)一個(gè)相當(dāng)簡(jiǎn)單的算法（見程序1 5 - 2）來求解f ( 1 ,c)。該算法基于例3 - 4所給出的策略，因此每個(gè)f (i,y) 只計(jì)算一次。程序1 5 - 2用二維數(shù)組f [ ][ ]來保存各f 的值。而回溯函數(shù)Tr a c e b a c k用于確定由程序1 5 - 2所產(chǎn)生的xi 值。函數(shù)K n a p s a c k的復(fù)雜性為( n c），而Tr a c e b a c k的復(fù)雜性為( n )。
程序15-2 f 和x 的迭代計(jì)算
template<class T>
void Knapsack(T p[], int w[], int c, int n, T** f)
{// 對(duì)于所有i和y計(jì)算f [ i ] [ y ]
// 初始化f [ n ] [ ]
for (int y = 0; y <= yMax; y++)
f[n][y] = 0;
for (int y = w[n]; y <= c; y++)
f[n][y] = p[n];
// 計(jì)算剩下的f
for (int i = n - 1; i > 1; i--) {
for (int y = 0; y <= yMax; y++)
f[i][y] = f[i+1][y];
for (int y = w[i]; y <= c; y++)
f[i][y] = max(f[i+1][y], f[i+1][y-w[i]] + p[i]);
}
f[1][c] = f[2][c];
if (c >= w[1])
f[1][c] = max(f[1][c], f[2][c-w[1]] + p[1]);
}
template<class T>
void Traceback(T **f, int w[], int c, int n, int x[])
{// 計(jì)算x
for (int i = 1; i < n; i++)
if (f[i][c] == f[i+1][c]) x[i] = 0;
else {x[i] = 1;
c -= w[i];}
x[n] = (f[n][c]) ? 1 : 0;
}
3. 元組方法（ 選讀）
程序1 5 - 2有兩個(gè)缺點(diǎn)：1) 要求權(quán)為整數(shù)；2) 當(dāng)背包容量c 很大時(shí)，程序1 5 - 2的速度慢于程序1 5 - 1。一般情況下，若c＞2n，程序1 5 - 2的復(fù)雜性為W (n2n )。可利用元組的方法來克服上述兩個(gè)缺點(diǎn)。在元組方法中，對(duì)于每個(gè)i，f (i, y) 都以數(shù)對(duì)(y, f (i, y)) 的形式按y的遞增次序存儲(chǔ)于表P(i)中。同時(shí)，由于f (i, y) 是y 的非遞減函數(shù)，因此P(i) 中各數(shù)對(duì)(y, f (i, y)) 也是按f (i, y) 的遞增次序排列的。
例3-6 條件同例3 - 5。對(duì)f 的計(jì)算如圖1 5 - 2所示。當(dāng)i= 5時(shí)，f 由數(shù)對(duì)集合P( 5 ) = [ ( 0 , 0 ) , ( 4 , 6 ) ]表示。而P( 4 )、P( 3 )和P( 2 )分別為[ ( 0 , 0 ) , ( 4 , 6 ) , ( 9 , 1 0 ) ]、[ ( 0 , 0 ) ( 4 , 6 ) , ( 9 , 1 0 ) , ( 1 0 , 11)] 和[ ( 0 , 0 ) ( 2 , 3 ) ( 4 , 6 ) ( 6 , 9 ) ( 9 , 1 0 ) ( 1 0 , 11 ) ]。
為求f ( 1 , 1 0 )，利用式（1 5 - 2）得f ( 1 , 1 0 ) = m a x｛f ( 2 , 1 0 )，f ( 2 , 8 ) + p 1｝。由P( 2 )得f ( 2 , 1 0 ) = 11、f (2,8)=9 (f ( 2 , 8 ) = 9來自數(shù)對(duì)( 6，9 ) )，因此f ( 1 , 1 0 ) = m a x｛11 , 1 5｝= 1 5。現(xiàn)在來求xi 的值，因?yàn)閒 ( 1 , 1 0 ) =f ( 2 , 6 ) +p1，所以x1 = 1；由f ( 2 , 6 ) =f ( 3 , 6 - w 2 ) +p2 =f ( 3 , 4 ) +p2，得x2 = 1；由f ( 3 , 4 ) =f ( 4 , 4 ) =f ( 5 , 4 )得x3=x4 = 0；最后，因f ( 5 , 4 )≠0得x5= 1。
檢查每個(gè)P(i) 中的數(shù)對(duì)，可以發(fā)現(xiàn)每對(duì)(y,f (i,y)) 對(duì)應(yīng)于變量xi , ., xn 的0/1 賦值的不同組合。設(shè)（a,b）和（c,d）是對(duì)應(yīng)于兩組不同xi , ., xn 的0 / 1賦值，若a≥c且b＜d，則(a, b) 受(b, c) 支配。被支配者不必加入P(i)中。若在相同的數(shù)對(duì)中有兩個(gè)或更多的賦值，則只有一個(gè)放入P(i)。假設(shè)wn≤C，P(n)=[(0,0), (wn , pn ) ]，P（n）中對(duì)應(yīng)于xn 的兩個(gè)數(shù)對(duì)分別等于0和1。對(duì)于每個(gè)i，P(i)可由P(i+ 1 )得出。首先，要計(jì)算數(shù)對(duì)的有序集合Q，使得當(dāng)且僅當(dāng)wi≤s≤c且(s-wi , t-pi )為P(i+1) 中的一個(gè)數(shù)對(duì)時(shí)，（s,t）為Q中的一個(gè)數(shù)對(duì)。現(xiàn)在Q中包含xi = 1時(shí)的數(shù)對(duì)集，而P(i+ 1 )對(duì)應(yīng)于xi = 0的數(shù)對(duì)集。接下來，合并Q和P(i+ 1 )并刪除受支配者和重復(fù)值即可得到P(i)。
例3-7 各數(shù)據(jù)同例1 5 - 6。P(5)=[(0,0),(4,6)], 因此Q= [ ( 5 , 4 ) , ( 9 , 1 0 ) ]。現(xiàn)在要將P( 5 )和Q合并得到P( 4 )。因( 5 , 4 )受( 4 , 6 )支配，可刪除( 5 , 4 )，所以P（4）=[(0,0), (4,6), (9,10)]。接著計(jì)算P( 3 )，首先由P( 4 )得Q=[(6,5), (10,11 ) ]，然后又由合并方法得P(3)=[(0,0), (4,6), (9,10), (10,11 ) ]。最后計(jì)算P( 2 )：由P( 3 )得Q= [ ( 2 , 3 )，( 6 , 9 ) ]，P( 3 )與Q合并得P(2)=[(0,0), (2,3), (4,6), (6,9), (9,10). (10,11 ) ]。因?yàn)槊總€(gè)P(i) 中的數(shù)對(duì)對(duì)應(yīng)于xi , ., xn 的不同0 / 1賦值，因此P(i) 中的數(shù)對(duì)不會(huì)超過2n-i+ 1個(gè)。計(jì)算P(i) 時(shí)，計(jì)算Q需消耗( |P(i+ 1 ) |）的時(shí)間，合并P(i+1) 和Q同樣需要( |P(i+ 1 ) | )的時(shí)間。計(jì)算所有P(i) 時(shí)所需要的總時(shí)間為： (n ?i=2|P(i + 1)|= O ( 2n )。當(dāng)權(quán)為整數(shù)時(shí)，|P(i) |≤c+1, 此時(shí)復(fù)雜性為O ( m i n {n c, 2n } )。
如6 . 4 . 3節(jié)定義的，數(shù)字化圖像是m×m的像素陣列。假定每個(gè)像素有一個(gè)0 ~ 2 5 5的灰度值。因此存儲(chǔ)一個(gè)像素至多需8位。若每個(gè)像素存儲(chǔ)都用最大位8位，則總的存儲(chǔ)空間為8m2 位。為了減少存儲(chǔ)空間，我們將采用變長(zhǎng)模式（ variable bit scheme），即不同像素用不同位數(shù)來存儲(chǔ)。像素值為0和1時(shí)只需1位存儲(chǔ)空間；值2、3各需2位；值4，5，6和7各需3位；以此類推，使用變長(zhǎng)模式的步驟如下：
1) 圖像線性化根據(jù)圖15-3a 中的折線將m×m維圖像轉(zhuǎn)換為1×m2 維矩陣。
2) 分段將像素組分成若干個(gè)段，分段原則是：每段中的像素位數(shù)相同。每個(gè)段是相鄰像素的集合且每段最多含2 5 6個(gè)像素，因此，若相同位數(shù)的像素超過2 5 6個(gè)的話，則用兩個(gè)以上的段表示。
3) 創(chuàng)建文件創(chuàng)建三個(gè)文件：S e g m e n t L e n g t h, BitsPerPixel 和P i x e l s。第一個(gè)文件包含在2 )中所建的段的長(zhǎng)度(減1 )，文件中各項(xiàng)均為8位長(zhǎng)。文件BitsPerPixel 給出了各段中每個(gè)像素的存儲(chǔ)位數(shù)（減1），文件中各項(xiàng)均為3位。文件Pixels 則是以變長(zhǎng)格式存儲(chǔ)的像素的二進(jìn)制串。
4) 壓縮文件壓縮在3) 中所建立的文件，以減少空間需求。
上述壓縮方法的效率（用所得壓縮率表示）很大程度上取決于長(zhǎng)段的出現(xiàn)頻率。
例3-8 考察圖15-3b 的4×4圖像。按照蛇形的行主次序，灰度值依次為1 0，9，1 2，4 0，5 0，3 5，1 5，1 2，8，1 0，9，1 5，11，1 3 0，1 6 0和2 4 0。各像素所需的位數(shù)分別為4，4，4，6，6，6，4，4，4，4，4，4，4，8，8和8，按等長(zhǎng)的條件將像素分段，可以得到4個(gè)段[ 1 0，9，1 2 ]、[ 4 0，5 0，3 5 ]、[15, 12, 8, 10, 9, 15, 11] 和［130, 160, 240］。因此，文件SegmentLength 為2，2，6，2；文件BitsPerSegment 的內(nèi)容為3，5，3，7；文件P i x e l s包含了按蛇形行主次序排列的1 6個(gè)灰度值，其中頭三個(gè)各用4位存儲(chǔ)，接下來三個(gè)各用6位，再接下來的七個(gè)各用4位，最后三個(gè)各用8位存儲(chǔ)。因此存儲(chǔ)單元中前3 0位存儲(chǔ)了前六個(gè)像素：
1010 1001 1100 111000 110010 100011
這三個(gè)文件需要的存儲(chǔ)空間分別為：文件SegmentLength 需3 2位；BitsPerSegment 需1 2位；Pixels 需8 2位，共需1 2 6位。而如果每個(gè)像素都用8位存儲(chǔ)，則存儲(chǔ)空間需8×1 6 = 1 2 8位，因而在本例圖像中，節(jié)省了2位的空間。
假設(shè)在2) 之后，產(chǎn)生了n 個(gè)段。段標(biāo)題（segment header）用于存儲(chǔ)段的長(zhǎng)度以及該段中每個(gè)像素所占用的位數(shù)。每個(gè)段標(biāo)題需11位。現(xiàn)假設(shè)li 和bi 分別表示第i 段的段長(zhǎng)和該段每個(gè)像素的長(zhǎng)度，則存儲(chǔ)第i 段像素所需要的空間為li *bi 。在2) 中所得的三個(gè)文件的總存儲(chǔ)空間為11 n+n ?i = 1li bi。可通過將某些相鄰段合并的方式來減少空間消耗。如當(dāng)段i 和i+ 1被合并時(shí)，合并后的段長(zhǎng)應(yīng)為li +li + 1。此時(shí)每個(gè)像素的存儲(chǔ)位數(shù)為m a x {bi，bi +1 } 位。盡管這種技術(shù)增加了文件P i x e l s的空間消耗，但同時(shí)也減少了一個(gè)段標(biāo)題的空間。
例3-9 如果將例1 5 - 8中的第1段和第2段合并，合并后，文件S e g m e n t L e n g t h變?yōu)?，6，2，BitsPerSegment 變?yōu)?，3，7。而文件Pixels 的前3 6位存儲(chǔ)的是合并后的第一段：001010 001001 001100 111000 110010 100011其余的像素（例1 5 - 8第3段）沒有改變。因?yàn)闇p少了1個(gè)段標(biāo)題，文件S e g m e n t L e n g t h和BitsPerPixel 的空間消耗共減少了11位，而文件Pixels 的空間增加6位，因此總共節(jié)約的空間為5位，空間總消耗為1 2 1位。
我們希望能設(shè)計(jì)一種算法，使得在產(chǎn)生n 個(gè)段之后，能對(duì)相鄰段進(jìn)行合并，以便產(chǎn)生一個(gè)具有最小空間需求的新的段集合。在合并相鄰段之后，可利用諸如L Z W法（見7 . 5節(jié)）和霍夫曼編碼（見9 . 5 . 3節(jié)）等其他技術(shù)來進(jìn)一步壓縮這三個(gè)文件。
令sq 為前q 個(gè)段的最優(yōu)合并所需要的空間。定義s0 = 0。考慮第i 段(i＞0 )，假如在最優(yōu)合并C中，第i 段與第i- 1，i- 2，.，i-r+1 段相合并，而不包括第i-r 段。合并C所需要的空間消耗等于：第1段到第i-r 段所需空間+ l s u m (i-r+ 1 ,i) * b m a x (i-r+ 1 ,i) + 11
其中l(wèi) s u m(a, b)=b ?j =a
lj，bmax (a, b)= m a x {ba , ..., bb }。假如在C中第1段到第i-r 段的合并不是最優(yōu)合并，那么需要對(duì)合并進(jìn)行修改，以使其具有更小的空間需求。因此還必須對(duì)段1到段i-r 進(jìn)行最優(yōu)合并，也即保證最優(yōu)原則得以維持。故C的空間消耗為：
si = si-r +l s u m（i-r+1, i）*b m a x（i-r+1, i）+ 11
r 的值介于1到i 之間，其中要求l s u m不超過2 5 6 (因?yàn)槎伍L(zhǎng)限制在2 5 6之內(nèi))。盡管我們不知道如何選擇r，但我們知道，由于C具有最小的空間需求，因此在所有選擇中， r 必須產(chǎn)生最小的空間需求。
假定k a yi 表示取得最小值時(shí)k 的值，sn 為n 段的最優(yōu)合并所需要的空間，因而一個(gè)最優(yōu)合并可用kay 的值構(gòu)造出來。
例3-10 假定在2) 中得到五個(gè)段，它們的長(zhǎng)度為[ 6，3，1 0，2，3 ]，像素位數(shù)為[ 1，2，3，2，1 ]，要用公式（1 5 - 3）計(jì)算sn，必須先求出sn-1，.，s0 的值。s0 為0，現(xiàn)計(jì)算s1：s1 =s0 +l1 *b1+ 11 = 1 7k a y1 = 1s2 由下式得出：
s2 = m i n {s1 +l2 b2 , s0 + (l1 +l2 ) * m a x {b1 , b2} } + 11 = m i n { 1 7 + 6 , 0 + 9 * 2 } + 11 = 2 9
k a y2 = 2
以此類推，可得s1.s5 = [ 1 7，2 9，6 7，7 3，82] ，k a y1.k a y5 = [ 1，2，2，3，4 ]。因?yàn)閟5 = 8 2，所以最優(yōu)空間合并需8 2位的空間。可由k a y5 導(dǎo)出本合并的方式，過程如下：因?yàn)閗 a y5 = 4，所以s5 是由公式（1 5 - 3）在k=4 時(shí)取得的，因而最優(yōu)合并包括：段1到段( 5 - 4 ) = 1的最優(yōu)合并以及段2，3，4和5的合并。最后僅剩下兩個(gè)段：段1以及段2到段5的合并段。
1. 遞歸方法
用遞歸式（1 5 - 3）可以遞歸地算出si 和k a yi。程序1 5 - 3為遞歸式的計(jì)算代碼。l，b，和k a y是一維的全局整型數(shù)組，L是段長(zhǎng)限制（ 2 5 6），h e a d e r為段標(biāo)題所需的空間( 11 )。調(diào)用S ( n )返回sn 的值且同時(shí)得出k a y值。調(diào)用Tr a c e b a c k ( k a y, n )可得到最優(yōu)合并。
現(xiàn)討論程序1 5 - 3的復(fù)雜性。t( 0 ) =c（c 為一個(gè)常數(shù)）： （n＞0），因此利用遞歸的方法可得t (n) = O ( 2n )。Tr a c e b a c k的復(fù)雜性為(n)。
程序15-3 遞歸計(jì)算s , k a y及最優(yōu)合并
int S(int i)
{ / /返回S ( i )并計(jì)算k a y [ i ]
if (i == 0 ) return 0;
//k = 1時(shí), 根據(jù)公式（ 1 5 - 3）計(jì)算最小值
int lsum = l[i],bmax = b[i];
int s = S(i-1) + lsum * bmax;
kay[i] = 1;
/ /對(duì)其余的k計(jì)算最小值并求取最小值
for (int k = 2; k <= i && lsum+l[i-k+1] <= L; k++) {
lsum += l[i-k+1];
if (bmax < b[i-k+1]) bmax = b[i-k+1];
int t = S(i-k);
if (s > t + lsum * bmax) {
s = t + lsum * bmax;
kay[i] = k;}
}
return s + header;
}
void Traceback(int kay[], int n)
{// 合并段
if (n == 0) return;
Tr a c e b a c k ( k a y, n-kay[n]);
cout << "New segment begins at " << (n - kay[n] + 1) << endl;
}
2. 無重復(fù)計(jì)算的遞歸方法
通過避免重復(fù)計(jì)算si，可將函數(shù)S的復(fù)雜性減少到(n)。注意這里只有n個(gè)不同的si。
例3 - 11 再考察例1 5 - 1 0中五個(gè)段的例子。當(dāng)計(jì)算s5 時(shí)，先通過遞歸調(diào)用來計(jì)算s4，.，s0。計(jì)算s4 時(shí)，通過遞歸調(diào)用計(jì)算s3，.，s0，因此s4 只計(jì)算了一次，而s3 計(jì)算了兩次，每一次計(jì)算s3要計(jì)算一次s2，因此s2 共計(jì)算了四次，而s1 重復(fù)計(jì)算了1 6次！可利用一個(gè)數(shù)組s 來保存先前計(jì)算過的si 以避免重復(fù)計(jì)算。改進(jìn)后的代碼見程序1 5 - 4，其中s為初值為0的全局整型數(shù)組。
程序15-4 避免重復(fù)計(jì)算的遞歸算法
int S(int i)
{ / /計(jì)算S ( i )和k a y [ i ]
/ /避免重復(fù)計(jì)算
if (i == 0) return 0;
if (s[i] > 0) return s[i]; //已計(jì)算完
/ /計(jì)算s [ i ]
/ /首先根據(jù)公式（1 5 - 3）計(jì)算k = 1時(shí)最小值
int lsum = l[i], bmax = b[i];
s[i] =S(i-1) + lsum * bmax;
kay[i] = 1;
/ /對(duì)其余的k計(jì)算最小值并更新
for (int k = 2; k <= i && lsum+l[i-k+1] <= L; k++) {
lsum += l[i-k+1];
if (bmax < b[i-k+1]) bmax = b[i-k+1];
int t = S(i-k);
if (s[i] > t + lsum * bmax) {
s[i] = t + lsum * bmax;
kay[i] = k;}
}
s[i] += header;
return s[i];
}
為了確定程序1 5 - 4的時(shí)間復(fù)雜性，我們將使用分期計(jì)算模式（ amortization scheme）。在該模式中，總時(shí)間被分解為若干個(gè)不同項(xiàng)，通過計(jì)算各項(xiàng)的時(shí)間然后求和來獲得總時(shí)間。當(dāng)計(jì)算si 時(shí)，若sj 還未算出，則把調(diào)用S(j) 的消耗計(jì)入sj ；若sj 已算出，則把S(j) 的消耗計(jì)入si (這里sj依次把計(jì)算新sq 的消耗轉(zhuǎn)移至每個(gè)sq )。程序1 5 - 4的其他消耗也被計(jì)入si。因?yàn)長(zhǎng)是2 5 6之內(nèi)的常數(shù)且每個(gè)li 至少為1，所以程序1 5 - 4的其他消耗為( 1 )，即計(jì)入每個(gè)si 的量是一個(gè)常數(shù)，且si 數(shù)目為n，因而總工作量為(n)。
3. 迭代方法
倘若用式（1 5 - 3）依序計(jì)算s1 , ., sn，便可得到一個(gè)復(fù)雜性為(n)的迭代方法。在該方法中，在si 計(jì)算之前， sj 必須已計(jì)算好。該方法的代碼見程序1 5 - 5，其中仍利用函數(shù)Tr a c e b a c k（見程序1 5 - 3）來獲得最優(yōu)合并。
程序15-5 迭代計(jì)算s和k a y
void Vbits (int l[], int b[], int n, int s[], int kay[])
{ / /計(jì)算s [ i ]和k a y [ i ]
int L = 256, header = 11 ;
s[0] = 0;
/ /根據(jù)式（1 5 - 3）計(jì)算s [ i ]
for (int i = 1; i <= n; i++) {
// k = 1時(shí),計(jì)算最小值
int lsum = l,
bmax = b[i];
s[i] = s[i-1] + lsum * bmax;
kay[i] = 1;
/ /對(duì)其余的k計(jì)算最小值并更新
for (int k=2; k<= i && lsum+l[i-k+1]<= L; k++) {
lsum += l[i-k+1];
if (bmax < b[i-k+1]) bmax = b[i-k+1];
if (s[i] > s[i-k] + lsum * bmax){
s[i] = s[i-k] + lsum * bmax;
kay[i] = k; }
}
s[i] += header;
}
}
3.2.3 矩陣乘法鏈
m×n矩陣A與n×p矩陣B相乘需耗費(fèi)(m n p)的時(shí)間（見第2章練習(xí)1 6）。我們把m n p作為兩個(gè)矩陣相乘所需時(shí)間的測(cè)量值。現(xiàn)假定要計(jì)算三個(gè)矩陣A、B和C的乘積，有兩種方式計(jì)算此乘積。在第一種方式中，先用A乘以B得到矩陣D，然后D乘以C得到最終結(jié)果，這種乘法的順序可寫為(A*B) *C。第二種方式寫為A* (B*C) ,道理同上。盡管這兩種不同的計(jì)算順序所得的結(jié)果相同，但時(shí)間消耗會(huì)有很大的差距。
例3-12 假定A為1 0 0×1矩陣，B為1×1 0 0矩陣，C為1 0 0×1矩陣，則A*B的時(shí)間耗費(fèi)為10 0 0 0，得到的結(jié)果D為1 0 0×1 0 0矩陣，再與C相乘所需的時(shí)間耗費(fèi)為1 000 000，因此計(jì)算(A*B) *C的總時(shí)間為1 010 000。B*C的時(shí)間耗費(fèi)為10 000，得到的中間矩陣為1×1矩陣，再與A相乘的時(shí)間消耗為1 0 0，因而計(jì)算A*（B*C）的時(shí)間耗費(fèi)竟只有10 100！而且，計(jì)算（ A*B）*C時(shí)，還需10 000個(gè)單元來存儲(chǔ)A*B，而A*（B*C）計(jì)算過程中，只需用1個(gè)單元來存儲(chǔ)B*C。
下面舉一個(gè)得益于選擇合適秩序計(jì)算A*B*C矩陣的實(shí)例：考慮兩個(gè)3維圖像的匹配。圖像匹配問題的要求是，確定一個(gè)圖像需旋轉(zhuǎn)、平移和縮放多少次才能逼近另一個(gè)圖像。實(shí)現(xiàn)匹配的方法之一便是執(zhí)行約1 0 0次迭代計(jì)算，每次迭代需計(jì)算1 2×1個(gè)向量T：
T=?A(x, y, z) *B(x, y, z)*C(x, y, z )
其中A，B和C分別為1 2×3，3×3和3×1矩陣。(x , y, z) 為矩陣中向量的坐標(biāo)。設(shè)t 表示計(jì)算A(x , y, z) *B(x , y, z) *C(x , y, z)的計(jì)算量。假定此圖像含2 5 6×2 5 6×2 5 6個(gè)向量，在此條件中，這1 0 0個(gè)迭代所需的總計(jì)算量近似為1 0 0 * 2 5 63 * t≈1 . 7 * 1 09 t。若三個(gè)矩陣是按由左向右的順序相乘的，則t = 1 2 * 3 * 3 + 1 2 * 3 *1= 1 4 4；但如果從右向左相乘， t = 3 * 3 * 1 + 1 2 * 3 * 1 = 4 5。由左至右計(jì)算約需2 . 4 * 1 011個(gè)操作，而由右至左計(jì)算大概只需7 . 5 * 1 01 0個(gè)操作。假如使用一個(gè)每秒可執(zhí)行1億次操作的計(jì)算機(jī)，由左至右需4 0分鐘，而由右至左只需1 2 . 5分鐘。
在計(jì)算矩陣運(yùn)算A*B*C時(shí)，僅有兩種乘法順序（由左至右或由右至左），所以可以很容易算出每種順序所需要的操作數(shù)，并選擇操作數(shù)比較少的那種乘法順序。但對(duì)于更多矩陣相乘來說，情況要復(fù)雜得多。如計(jì)算矩陣乘積M1×M2×.×Mq，其中Mi 是一個(gè)ri×ri + 1 矩陣( 1≤i≤q)。不妨考慮q=4 的情況，此時(shí)矩陣運(yùn)算A*B*C*D可按以下方式（順序）計(jì)算：
A* ( (B*C) *D) A* (B* (C*D)) (A*B) * (C*D) (A* (B*C) ) *D
不難看出計(jì)算的方法數(shù)會(huì)隨q 以指數(shù)級(jí)增加。因此，對(duì)于很大的q 來說，考慮每一種計(jì)算順序并選擇最優(yōu)者已是不切實(shí)際的。
現(xiàn)在要介紹一種采用動(dòng)態(tài)規(guī)劃方法獲得矩陣乘法次序的最優(yōu)策略。這種方法可將算法的時(shí)間消耗降為(q3 )。用Mi j 表示鏈Mi×.×Mj （i≤j）的乘積。設(shè)c(i,j) 為用最優(yōu)法計(jì)算Mi j 的消耗，k a y(i, j) 為用最優(yōu)法計(jì)算Mi j 的最后一步Mi k×Mk+1, j 的消耗。因此Mij 的最優(yōu)算法包括如何用最優(yōu)算法計(jì)算Mik 和Mkj 以及計(jì)算Mik×Mkj 。根據(jù)最優(yōu)原理，可得到如下的動(dòng)態(tài)規(guī)劃遞歸式：k a y(i,i+s)= 獲得上述最小值的k. 以上求c 的遞歸式可用遞歸或迭代的方法來求解。c( 1，q) 為用最優(yōu)法計(jì)算矩陣鏈的消耗，k a y( 1 ,q) 為最后一步的消耗。其余的乘積可由k a y值來確定。
1. 遞歸方法
與求解0 / 1背包及圖像壓縮問題一樣，本遞歸方法也須避免重復(fù)計(jì)算c (i, j) 和k a y(i, j)，否則算法的復(fù)雜性將會(huì)非常高。
例3-13 設(shè)q= 5和r =（1 0 , 5 , 1 , 1 0 , 2 , 1 0），式中待求的c 中有四個(gè)c的s= 0或1，因此用動(dòng)態(tài)規(guī)劃方法可立即求得它們的值： c( 1 , 1 ) =c( 5 , 5 ) = 0 ;c(1,2)=50; c( 4 , 5 ) = 2 0 0。現(xiàn)計(jì)算C( 2，5 )：c( 2 , 5 ) = m i n {c( 2 , 2 ) +c(3,5)+50, c( 2 , 3 ) +c(4,5)+500, c( 2 , 4 ) +c( 5 , 5 ) + 1 0 0 } （1 5 - 5）其中c( 2 , 2 ) =c( 5 , 5 ) = 0；c( 2 , 3 ) = 5 0；c(4,5)=200 。再用遞歸式計(jì)算c( 3 , 5 )及c( 2 , 4 ) :c( 3 , 5 ) = m i n {c( 3 , 3 ) +c(4,5)+100, c( 3 , 4 ) +c( 5 , 5 ) + 2 0 } = m i n { 0 + 2 0 0 + 1 0 0 , 2 0 + 0 + 2 0 } = 4 0c( 2 , 4 ) = m i n {c( 2 , 2 ) +c( 3 , 4 ) + 1 0 ,c( 2 , 3 ) +c( 4 , 4 ) + 1 0 0 } = m i n { 0 + 2 0 + 1 0 , 5 0 + 1 0 + 2 0 } = 3 0由以上計(jì)算還可得k a y( 3 , 5 ) = 4，k ay( 2 , 4 ) = 2。現(xiàn)在,計(jì)算c(2,5) 所需的所有中間值都已求得，將它們代入式（1 5 - 5）得：
c(2,5)=min{0+40+50, 50+200+500, 30+0+100}=90且k a y( 2 , 5 ) = 2
再用式（1 5 - 4）計(jì)算c( 1 , 5 )，在此之前必須算出c( 3 , 5 )、c(1,3) 和c( 1 , 4 )。同上述過程，亦可計(jì)算出它們的值分別為4 0、1 5 0和9 0，相應(yīng)的k a y 值分別為4、2和2。代入式（1 5 - 4）得：
c(1,5)=min{0+90+500, 50+40+100, 150+200+1000, 90+0+200}=190且k a y( 1 , 5 ) = 2
此最優(yōu)乘法算法的消耗為1 9 0，由k a y(1,5) 值可推出該算法的最后一步， k a y(1,5) 等于2，因此最后一步為M1 2×M3 5，而M12 和M35 都是用最優(yōu)法計(jì)算而來。由k a y( 1 , 2 ) = 1知M12 等于M11×M2 2，同理由k a y( 3 , 5) = 4得知M35 由M3 4×M55 算出。依此類推，M34 由M3 3×M44 得出。因而此最優(yōu)乘法算法的步驟為：
M11×M2 2 = M1 2
M3 3×M4 4 = M3 4
M3 4×M5 5 = M3 5
M1 2×M3 5 = M1 5
計(jì)算c(i, j) 和k a y (i, j) 的遞歸代碼見程序1 5 - 6。在函數(shù)C中，r 為全局一維數(shù)組變量， k a y是全局二維數(shù)組變量，函數(shù)C返回c(i j) 之值且置k a y [a] [b] =k ay (a , b) (對(duì)于任何a , b)，其中c(a , b)在計(jì)算c(i,j) 時(shí)皆已算出。函數(shù)Traceback 利用函數(shù)C中已算出的k a y值來推導(dǎo)出最優(yōu)乘法算法的步驟。
設(shè)t(q)為函數(shù)C的復(fù)雜性，其中q=j-i+ 1（即Mij 是q個(gè)矩陣運(yùn)算的結(jié)果）。當(dāng)q為1或2時(shí)，t(q) =d，其中d 為一常數(shù)；而q> 2時(shí)，t (q)=2q-1?k = 1t (k ) +e q，其中e 是一個(gè)常量。因此當(dāng)q＞2時(shí)，t(q)＞2t (q- 1 ) +e，所以t (q)= W ( 2q)。函數(shù)Traceback 的復(fù)雜性為(q)。
程序15-6 遞歸計(jì)算c (i, j) 和kay (i, j)
int C(int i, int j)
{ / /返回c(i,j) 且計(jì)算k(i,j) = kay[i][j]
if (i==j) return 0; //一個(gè)矩陣的情形
if (i == j-1) { //兩個(gè)矩陣的情形
kay[i][i+1] = i;
return r[i]*r[i+1]*r[r+2];}
/ /多于兩個(gè)矩陣的情形
/ /設(shè)u為k = i 時(shí)的最小值
int u = C(i,i) + C(i+1,j) + r[i]*r[i+1]*r[j+1];
kay[i][j] = i;
/ /計(jì)算其余的最小值并更新u
for (int k = i+1; k < j; k++) {
int t = C(i,k) + C(k+1,j) + r[i]*r[k+1]*r[j+1];
if (r < u) {//小于最小值的情形
u = t;
kay[i][j] = k;
}
return u;
}
void Traceback (int i, int j ,int **kay)
{ / /輸出計(jì)算Mi j 的最優(yōu)方法
if ( i == j) return;
Traceback(i, kay[i][j], kay);
Traceback(kay[i][j]+1, j, kay);
cout << "Multiply M" << i << ", "<< kay[i][j];
cout << " and M " << (kay[i][j]+1) << ", " << j << end1;
}
2. 無重復(fù)計(jì)算的遞歸方法
若避免再次計(jì)算前面已經(jīng)計(jì)算過的c（及相應(yīng)的k a y），可將復(fù)雜性降低到（q3）。而為了避免重復(fù)計(jì)算，需用一個(gè)全局?jǐn)?shù)組c[ ][ ]存儲(chǔ)c(i, j) 值，該數(shù)組初始值為0。函數(shù)C的新代碼見程序1 5 - 7：
程序15-7 無重復(fù)計(jì)算的c (i, j) 計(jì)算方法
int C(int i,int j)
{ / /返回c(i,j) 并計(jì)算k a y ( i , j ) = k a y [ I ] [ j ]
/ /避免重復(fù)計(jì)算
/ /檢查是否已計(jì)算過
if （c[i][j] >） return c[i][j];
/ /若未計(jì)算,則進(jìn)行計(jì)算
if(i==j) return 0; //一個(gè)矩陣的情形
i f ( i = = j - 1 ) { / /兩個(gè)矩陣的情形
kay[i][i+1]=i;
c [ i ] [ j ] = r [ i ] * r [ i + 1 ] * r [ i + 2 ] ;
return c[i][j];}
/ /多于兩個(gè)矩陣的情形
/ /設(shè)u為k = i 時(shí)的最小值
int u=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];
k a y [ i ] [ j ] = i ;
/ /計(jì)算其余的最小值并更新u
for (int k==i+1; k<j;k++){
int t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1];
if (t<u) {// 比最小值還小
u = t ;
k a y [ i ] [ j ] = k ; }
}
c [ i ] [ j ] = u ;
return u;
}
為分析改進(jìn)后函數(shù)C 的復(fù)雜性，再次使用分期計(jì)算方法。注意到調(diào)用C(1, q) 時(shí)每個(gè)c (i, j)（1≤i≤j≤q）僅被計(jì)算一次。要計(jì)算尚未計(jì)算過的c(a,b)，需附加的工作量s =j-i＞1。將s 計(jì)入第一次計(jì)算c (a, b) 時(shí)的工作量中。在依次計(jì)算c(a, b) 時(shí)，這個(gè)s 會(huì)轉(zhuǎn)計(jì)到每個(gè)c (a, b) 的第一次計(jì)算時(shí)間c 中，因此每個(gè)c (i, i) 均被計(jì)入s。對(duì)于每個(gè)s，有q-s+ 1個(gè)c(i, j) 需要計(jì)算，因此總的工作消耗為q-1 ?s=1(q-s+ 1) = (q3 )。
3. 迭代方法
c 的動(dòng)態(tài)規(guī)劃遞歸式可用迭代的方法來求解。若按s = 2，3，.，q-1 的順序計(jì)算c (i, i+s)，每個(gè)c 和kay 僅需計(jì)算一次。
例3-14 考察例3 - 1 3中五個(gè)矩陣的情況。先初始化c (i, i) (0≤i≤5) 為0，然后對(duì)于i=1, ., 4分別計(jì)算c (i, i+ 1 )。c (1, 2)= r1 r2 r3 = 5 0，c (2, 3)= 5 0，c ( 3,4)=20 和c (4, 5) = 2 0 0。相應(yīng)的k ay 值分別為1，2，3和4。
當(dāng)s= 2時(shí)，可得：
c( 1 , 3 ) = m i n {c( 1 , 1 ) +c(2,3)+ r1 r2 r4 , c( 1 , 2 ) +c( 3 ,3 )+r1r3r4 }=min
=150
且k a y( 1 , 3 ) = 2。用相同方法可求得c( 2 , 4 )和c( 3 , 5 )分別為3 0和4 0，相應(yīng)k a y值分別為2和3。
當(dāng)s= 3時(shí)，需計(jì)算c(1,4) 和c( 2 , 5 )。計(jì)算c(2,5) 所需要的所有中間值均已知(見( 1 5 - 5 )式)，代入計(jì)算公式后可得c( 2 , 5 ) = 9 0，k a y( 2 , 5 ) = 2。c( 1 , 4 )可用同樣的公式計(jì)算。最后，當(dāng)s= 4時(shí)，可直接用（1 5 - 4）式來計(jì)算c( 1 , 5 )，因?yàn)樵撌接疫吽许?xiàng)都已知。
計(jì)算c 和kay 的迭代程序見函數(shù)M a t r i x C h a i n（見程序1 5 - 8），該函數(shù)的復(fù)雜性為(q3 )。計(jì)算出kay 后同樣可用程序1 5 - 6中的Traceback 函數(shù)推算出相應(yīng)的最優(yōu)乘法計(jì)算過程。
程序15-8 c 和kay 的迭代計(jì)算
void MatrixChain(int r[], int q, int **c, int **kay)
{// 為所有的Mij 計(jì)算耗費(fèi)和k a y
// 初始化c[i][i], c[i][i+1]和k a y [ i ] [ i + 1 ]
for (int i = 1; i < q; i++) {
c[i][i] = 0;
c[i][i+1] = r[i]*r[i+1]*r[i+2];
kay[i][i+1] = i;
}
c[q][q] = 0;
/ /計(jì)算余下的c和k a y
for (int s = 2; s < q; s++)
for (int i = 1; i <= q - s; i++) {
// k = i時(shí)的最小項(xiàng)
c[i][i+s] = c[i][i] + c[i+1][i+s] + r[i]*r[i+1]*r[i+s+1];
kay[i][i+s] = i;
// 余下的最小項(xiàng)
for (int k = i+1; k < i + s; k++) {
int t = c[i][k] + c[k+1][i+s] + r[i]*r[k+1]*r[i+s+1];
if (t < c[i][i+s]) {// 更小的最小項(xiàng)
c[i][i+s] = t;
kay[i][i+s] = k;}
}
}
}
3.2.4 最短路徑
假設(shè)G為有向圖，其中每條邊都有一個(gè)長(zhǎng)度（或耗費(fèi)），圖中每條有向路徑的長(zhǎng)度等于該路徑中各邊的長(zhǎng)度之和。對(duì)于每對(duì)頂點(diǎn)(i, j)，在頂點(diǎn)i 與j 之間可能有多條路徑，各路徑的長(zhǎng)度可能各不相同。我們定義從i 到j(luò) 的所有路徑中，具有最小長(zhǎng)度的路徑為從i 到j(luò) 的最短路徑。
例3-15 如圖1 5 - 4所示。從頂點(diǎn)1到頂點(diǎn)3的路徑有
1) 1,2,5,3
2) 1,4,3
3) 1,2,5,8,6,3
4) 1,4,6,3
由該圖可知,各路徑相應(yīng)的長(zhǎng)度為1 0、2 8、9、2 7，因而路徑3) 是該圖中頂點(diǎn)1到頂點(diǎn)3的最短路徑。
在所有點(diǎn)對(duì)最短路徑問題（ a l l - p a i r sshorest-paths problem）中，要尋找有向圖G中每對(duì)頂點(diǎn)之間的最短路徑。也就是說，對(duì)于每對(duì)頂點(diǎn)(i, j)，需要尋找從i到j(luò) 的最短路徑及從j 到i 的最短路徑。因此對(duì)于一個(gè)n 個(gè)頂點(diǎn)的圖來說，需尋找p =n(n-1) 條最短路徑。假定圖G中不含有長(zhǎng)度為負(fù)數(shù)的環(huán)路，只有在這種假設(shè)下才可保證G中每對(duì)頂點(diǎn)(i, j) 之間總有一條不含環(huán)路的最短路徑。當(dāng)有向圖中存在長(zhǎng)度小于0的環(huán)路時(shí)，可能得到長(zhǎng)度為－∞的更短路徑，因?yàn)榘摥h(huán)路的最短路徑往往可無限多次地加上此負(fù)長(zhǎng)度的環(huán)路。
設(shè)圖G中n 個(gè)頂點(diǎn)的編號(hào)為1到n。令c (i, j, k)表示從i 到j(luò) 的最短路徑的長(zhǎng)度，其中k 表示該路徑中的最大頂點(diǎn)。因此，如果G中包含邊<i, j>，則c(i, j, 0) =邊<i, j> 的長(zhǎng)度；若i= j ，則c(i,j, 0)=0；如果G中不包含邊<i, j>，則c (i, j, 0)= +∞。c(i, j, n) 則是從i 到j(luò) 的最短路徑的長(zhǎng)度。
例3-16 考察圖1 5 - 4。若k=0, 1, 2, 3，則c (1, 3, k)= ∞；c (1, 3, 4)= 2 8；若k = 5, 6, 7，則c (1, 3,k) = 1 0；若k=8, 9, 10，則c (1, 3, k) = 9。因此1到3的最短路徑長(zhǎng)度為9。對(duì)于任意k＞0，如何確定c (i, j, k) 呢？中間頂點(diǎn)不超過k 的i 到j(luò) 的最短路徑有兩種可能：該路徑含或不含中間頂點(diǎn)k。若不含，則該路徑長(zhǎng)度應(yīng)為c(i, j, k- 1 )，否則長(zhǎng)度為c(i, k, k- 1) +c (k, j, k- 1 )。c(i, j, k) 可取兩者中的最小值。因此可得到如下遞歸式：
c( i, j, k)= m i n {c(i, j, k-1), c (i, k, k- 1) +c (k, j, k- 1 ) }，k＞0
以上的遞歸公式將一個(gè)k 級(jí)運(yùn)算轉(zhuǎn)化為多個(gè)k-1 級(jí)運(yùn)算，而多個(gè)k-1 級(jí)運(yùn)算應(yīng)比一個(gè)k 級(jí)運(yùn)算簡(jiǎn)單。如果用遞歸方法求解上式，則計(jì)算最終結(jié)果的復(fù)雜性將無法估量。令t (k) 為遞歸求解c (i, j, k) 的時(shí)間。根據(jù)遞歸式可以看出t(k) = 2t(k- 1 ) +c。利用替代方法可得t(n) = ( 2n )。因此得到所有c (i, j, n) 的時(shí)間為(n2 2n )。
當(dāng)注意到某些c (i, j, k-1) 值可能被使用多次時(shí)，可以更高效地求解c (i, j, n)。利用避免重復(fù)計(jì)算c(i, j, k) 的方法，可將計(jì)算c 值的時(shí)間減少到(n3 )。這可通過遞歸方式（見程序1 5 - 7矩陣鏈問題）或迭代方式來實(shí)現(xiàn)。出迭代算法的偽代碼如圖1 5 - 5所示。
/ /尋找最短路徑的長(zhǎng)度
/ /初始化c（i，j，1）
for （int i=1； i < = n ; i + +）
for (int j=1; j<=n; j+ + )
c ( i ,j, 0 ) = a ( i ,j); // a 是長(zhǎng)度鄰接矩陣
/ /計(jì)算c ( i ,j, k ) ( 0 < k < = n )
for(int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j= 1 ;j< = n ;j+ + )
if (c(i,k,k-1)+c(k,j, k - 1 ) < c ( i ,j, k - 1 ) )
c ( i ,j, k ) = c ( i , k , k - 1 ) + c ( k ,j, k - 1 ) ;
else c(i,j, k ) = c ( i ,j, k - 1 ) ;
圖15-5 最短路徑算法的偽代碼
注意到對(duì)于任意i，c(i,k,k) =c(i,k,k- 1 )且c(k,i,k) =c(k,i,k- 1 )，因而，若用c(i,j)代替圖1 5 - 5的c(i,j,k)，最后所得的c(i,j) 之值將等于c(i,j,n) 值。此時(shí)圖1 5 - 5可改寫成程序1 5 - 9的C + +代碼。程序1 5 - 9中還利用了程序1 2 - 1中定義的AdjacencyWDigraph 類。函數(shù)AllPairs 在c 中返回最短路徑的長(zhǎng)度。若i 到j(luò) 無通路，則c [i] [j]被賦值為N o E d g e。函數(shù)AllPairs 同時(shí)計(jì)算了k a y [ i ] [ j ]，其中kay[i][j] 表示從i 到j(luò) 的最短路徑中最大的k 值。在后面將看到如何根據(jù)kay 值來推斷出從一個(gè)頂點(diǎn)到另一頂點(diǎn)的最短路徑（見程序1 5 - 1 0中的函數(shù)O u t p u t P a t h）。
程序1 5 - 9的時(shí)間復(fù)雜性為(n3 )，其中輸出一條最短路徑的實(shí)際時(shí)間為O (n)。
程序15-9 c 和kay 的計(jì)算
template<class T>
void AdjacencyWDigraph<T>::Allpairs(T **c, int **kay)
{ / /所有點(diǎn)對(duì)的最短路徑
/ /對(duì)于所有i和j，計(jì)算c [ i ] [ j ]和k a y [ i ] [ j ]
/ /初始化c [ i ] [ j ] = c（i，j，0）
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
c[i][j] = a[i][j];
kay[i][j] = 0;
}
for (i = 1; i <= n; i++)
c[i][i] = 0;
// 計(jì)算c[i][j] = c(i,j,k)
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
T t1 = c[i][k];
T t2 = c[k][j];
T t3 = c[i][j];
if (t1 != NoEdge && t2 != NoEdge && (t3 == NoEdge || t1 + t2 < t3)) {
c[i][j] = t1 + t2;
kay[i][j] = k;}
}
}
程序15-10 輸出最短路徑
void outputPath(int **kay, int i, int j)
{// 輸出i 到j(luò) 的路徑的實(shí)際代碼
if (i == j) return;
if (kay[i][j] == 0) cout << j << ' ';
else {outputPath(kay, i, kay[i][j]);
o u t p u t P a t h ( k a y, kay[i][j], j);}
}
template<class T>
void OutputPath(T **c, int **kay, T NoEdge, int i, int j)
{// 輸出從i 到j(luò)的最短路徑
if (c[i][j] == NoEdge) {
cout << "There is no path from " << i << " to " << j << endl;
r e t u r n ; }
cout << "The path is" << endl;
cout << i << ' ';
o u t p u t P a t h ( k a y, i , j ) ;
cout << endl;
}
例3-17 圖15-6a 給出某圖的長(zhǎng)度矩陣a，15-6b 給出由程序1 5 - 9所計(jì)算出的c 矩陣，15-6c 為對(duì)應(yīng)的k a y值。根據(jù)15-6c 中的kay 值，可知從1到5的最短路徑是從1到k a y [ 1 ] [ 5 ] = 4的最短路徑再加上從4到5的最短路徑，因?yàn)閗 a y [ 4 ] [ 5 ] = 0，所以從4到5的最短路徑無中間頂點(diǎn)。從1到4的最短路徑經(jīng)過k a y [ 1 ] [ 4 ] = 3。重復(fù)以上過程，最后可得1到5的最短路徑為：1，2，3，4，5。
3.2.5 網(wǎng)絡(luò)的無交叉子集
在11 . 5 . 3節(jié)的交叉分布問題中，給定一個(gè)每邊帶n 個(gè)針腳的布線通道和一個(gè)排列C。頂部的針腳i 與底部的針腳Ci 相連，其中1≤i≤n，數(shù)對(duì)(i, Ci ) 稱為網(wǎng)組。總共有n 個(gè)網(wǎng)組需連接或連通。假設(shè)有兩個(gè)或更多的布線層，其中有一個(gè)為優(yōu)先層，在優(yōu)先層中可以使用更細(xì)的連線，其電阻也可能比其他層要小得多。布線時(shí)應(yīng)盡可能在優(yōu)先層中布設(shè)更多的網(wǎng)組。而剩下的其他網(wǎng)組將布設(shè)在其他層。當(dāng)且僅當(dāng)兩個(gè)網(wǎng)組之間不交叉時(shí)，它們可布設(shè)在同一層。我們的任務(wù)是尋找一個(gè)最大無交叉子集（Maximum Noncrossing Su b s e t，M N S )。在該集中，任意兩個(gè)網(wǎng)組都不交叉。因(i, Ci ) 完全由i 決定，因此可用i 來指定(i, Ci )。
例3-18 考察圖1 5 - 7（對(duì)應(yīng)于圖1 0 - 1 7）。( 1 , 8 )和( 2 , 7 )（也即1號(hào)網(wǎng)組和2號(hào)網(wǎng)組）交叉，因而不能布設(shè)在同一層中。而( 1 , 8 )，(7,9) 和(9,10) 未交叉，因此可布設(shè)在同一層。但這3個(gè)網(wǎng)組并不能構(gòu)成一個(gè)M N S，因?yàn)檫€有更大的不交叉子集。圖1 0 - 1 7中給出的例子中，集合｛ ( 4 , 2 ) ,( 5 , 5 ) , ( 7 , 9 ) , ( 9 , 1 0 )｝是一個(gè)含4個(gè)網(wǎng)組的M N S。
設(shè)M N S(i, j) 代表一個(gè)M N S，其中所有的(u, Cu ) 滿足u≤i，Cu≤j。令s i z e(i,j) 表示M N S(i,j)的大小(即網(wǎng)組的數(shù)目)。顯然M N S(n,n)是對(duì)應(yīng)于給定輸入的M N S，而s i z e(n,n)是它的大小。
例3-19 對(duì)于圖1 0 - 1 7中的例子，M N S( 1 0 , 1 0 )是我們要找的最終結(jié)果。如例3 - 1 8中所指出的，s i z e( 1 0 , 1 0 ) = 4，因?yàn)? 1 , 8 )，( 2 , 7 )，( 7 , 9 )，( 8 , 3 )，( 9 , 1 0 )和( 1 0 , 6 )中要么頂部針腳編號(hào)比7大，要么底部針腳編號(hào)比6大，因此它們都不屬于M N S( 7 , 6 )。因此只需考察剩下的4個(gè)網(wǎng)組是否屬于M N S( 7 , 6 )，如圖1 5 - 8所示。子集｛( 3 , 4 ) , ( 5 , 5 )｝是大小為2的無交叉子集。沒有大小為3的無交叉子集，因此s i z e( 7 , 6) = 2。
當(dāng)i= 1時(shí)，( 1 ,C1) 是M N S( 1 ,j) 的唯一候選。僅當(dāng)j≥C1 時(shí)，這個(gè)網(wǎng)組才會(huì)是M N S( 1 ,j) 的一個(gè)成員.
下一步，考慮i＞1時(shí)的情況。若j＜Ci，則(i,Ci ) 不可能是M N S( i,j) 的成員，所有屬于M N S(i,j) 的(u, Cu ) 都需滿足u＜i且Cu＜j，因此：s i z e(i,j) =s i z e(i- 1 ,j), j<Ci （1 5 - 7）
若j≥Ci，則(i,Ci ) 可能在也可能不在M N S(i,j) 內(nèi)。若(i,Ci ) 在M N S(i,j) 內(nèi)，則在M N S(i,j)中不會(huì)有這樣的(u,Cu )：u＜i且Cu＞Ci，因?yàn)檫@個(gè)網(wǎng)組必與(i, Ci ) 相交。因此M N S(i,j) 中的其他所有成員都必須滿足條件u＜i且Cu＜Ci。在M N S(i,j) 中這樣的網(wǎng)組共有Mi- 1 , Ci- 1 個(gè)。若(i,Ci ) 不在M N S(i,j)中，則M N S(i,j) 中的所有(u, Cu ) 必須滿足u＜i；因此s i z e(i,j)=s i z e(i- 1 ,j)。雖然不能確定(i, Ci )是否在M N S(i,j) 中，但我們可以根據(jù)獲取更大M N S的原則來作出選擇。因此：s i z e(i,j) = m a x {s i z e(i-1 ,j), s i z e(i- 1 ,Ci-1)+1}, j≥Ci （1 5 - 8）
雖然從（1 5 - 6）式到（ 1 5 - 8）式可用遞歸法求解，但從前面的例子可以看出，即使避免了重復(fù)計(jì)算，動(dòng)態(tài)規(guī)劃遞歸算法的效率也不夠高，因此只考慮迭代方法。在迭代過程中先用式（1 5 - 6）計(jì)算出s i ze ( 1 ,j)，然后再用式（1 5 - 7）和（1 5 - 8）按i=2, 3, ., n 的順序計(jì)算s i ze (i,j)，最后再用Traceback 來得到M N S(n, n) 中的所有網(wǎng)組。
例3-20 圖1 5 - 9給出了圖1 5 - 7對(duì)應(yīng)的s i z e(i,j) 值。因s i z e( 1 0 , 1 0) = 4，可知M N S含4個(gè)網(wǎng)組。為求得這4個(gè)網(wǎng)組，先從s i ze ( 1 0 , 1 0 )入手。可用（1 5 - 8）式算出s i z e( 1 0 , 1 0 )。根據(jù)式（1 5 - 8）時(shí)的產(chǎn)生原因可知s i ze ( 1 0 , 1 0)=s i z e( 9 , 1 0 )，因此現(xiàn)在要求M NS ( 9 , 1 0 )。由于M NS ( 1 0 , 1 0 )≠s i z e( 8 , 1 0 )，因此M NS (9,10) 中必包含9號(hào)網(wǎng)組。M N S(9,10) 中剩下的網(wǎng)組組成M NS ( 8 , C9- 1)=M N S( 8 , 9 )。由M N S( 8 , 9 ) =M NS (7,9) 知，8號(hào)網(wǎng)組可以被排除。接下來要求M N S( 7 , 9 )，因?yàn)閟 i z e( 7 , 9 )≠s i z e( 6 , 9 )，所以M N S中必含7號(hào)網(wǎng)組。M NS (7,9) 中余下的網(wǎng)組組成M NS ( 6 , C7- 1 ) =M N S( 6 , 8 )。根據(jù)s i z e( 6 , 8 ) =s i z e( 5 , 8 )可排除6號(hào)網(wǎng)組。按同樣的方法， 5號(hào)網(wǎng)組，3號(hào)網(wǎng)組加入M N S中，而4號(hào)網(wǎng)組等其他網(wǎng)組被排除。因此回溯過程所得到的大小為4的M N S為{ 3 , 5 , 7 , 9 }。
注意到在回溯過程中未用到s i z e( 1 0 ,j) (j≠1 0 )，因此不必計(jì)算這些值。
程序1 5 - 11給出了計(jì)算s i z e ( i , j ) 的迭代代碼和輸出M N S的代碼。函數(shù)M N S用來計(jì)算s i ze (i,j) 的值，計(jì)算結(jié)果用一個(gè)二維數(shù)組M N來存儲(chǔ)。size[i][j] 表示s i z e(i,j)，其中i=j= n 或1≤i＜n，0≤j≤n，計(jì)算過程的時(shí)間復(fù)雜性為(n2 )。函數(shù)Traceback 在N et［0 : m - 1］中輸出所得到的M N S，其時(shí)間復(fù)雜性為(n)。因此求解M M S問題的動(dòng)態(tài)規(guī)劃算法的總的時(shí)間復(fù)雜性
為(n2 )。
程序1 5 - 11 尋找最大無交叉子集
void MNS(int C[], int n, int **size)
{ / /對(duì)于所有的i 和j，計(jì)算s i z e [ i ] [ j ]
/ /初始化s i z e [ 1 ] [ * ]
for (int j = 0; j < C[1]; j++)
size[1][j] = 0;
for (j = C[1]; j <= n; j++)
size[1][j] = 1;
// 計(jì)算size[i][*], 1 < i < n
for (int i = 2; i < n; i++) {
for (int j = 0; j < C[i]; j++)
size[i][j] = size[i-1][j];
for (j = C[i]; j <= n; j++)
size[i][j] = max(size[i-1][j], size[i-1][C[i]-1]+1);
}
size[n][n] = max(size[n-1][n], size[n-1][C[n]-1]+1);
}
void Traceback(int C[], int **size, int n, int Net[], int& m)
{// 在N e t [ 0 : m - 1 ]中返回M M S
int j = n; // 所允許的底部最大針腳編號(hào)
m = 0; // 網(wǎng)組的游標(biāo)
for (int i = n; i > 1; i--)
// i 號(hào)n e t在M N S中?
if (size[i][j] != size[i-1][j]){// 在M N S中
Net[m++] = i;
j = C[i] - 1;}
// 1號(hào)網(wǎng)組在M N S中?
if (j >= C[1])
Net[m++] = 1; // 在M N S中
}
3.2.6 元件折疊
在設(shè)計(jì)電路的過程中，工程師們會(huì)采取多種不同的設(shè)計(jì)風(fēng)格。其中的兩種為位－片設(shè)計(jì)（bit-slice design）和標(biāo)準(zhǔn)單元設(shè)計(jì)（standard-cell design）。在前一種方法中，電路首先被設(shè)計(jì)為一個(gè)元件棧（如圖15-10a 所示）。每個(gè)元件Ci 寬為wi ，高為hi ，而元件寬度用片數(shù)來表示。圖15-10a 給出了一個(gè)四片的設(shè)計(jì)。線路是按片來連接各元件的，即連線可能連接元件Ci 的第j片到元件Ci+1 的第j 片。如果某些元件的寬度不足j 片，則這些元件之間不存在片j 的連線。當(dāng)圖1 5 -10a 的位－片設(shè)計(jì)作為某一大系統(tǒng)的一部分時(shí)，則在V L SI ( Very Large Scale Integrated) 芯片上為它分配一定數(shù)量的空間單元。分配是按空間寬度或高度的限制來完成的。現(xiàn)在的問題便是如何將元件棧折疊到分配空間中去，以便盡量減小未受限制的尺度（如，若高度限制為H時(shí)，必須折疊棧以盡量減小寬度W）。由于其他尺度不變，因此縮小一個(gè)尺度（如W）等價(jià)于縮小面積。可用折線方式來折疊元件棧，在每一折疊點(diǎn)，元件旋轉(zhuǎn)1 8 0°。在圖15-10b 的例子中，一個(gè)1 2元件的棧折疊成四個(gè)垂直棧，折疊點(diǎn)為C6 , C9 和C1 0。折疊棧的寬度是寬度最大的元件所需的片數(shù)。在圖15-10b 中，棧寬各為4，3，2和4。折疊棧的高度等于各棧所有元件高度之和的最大值。在圖15-10b 中棧1的元件高度之和最大，該棧的高度決定了包圍所有棧的矩形高度。
實(shí)際上，在元件折疊問題中，還需考慮連接兩個(gè)棧的線路所需的附加空間。如，在圖1 5 -10b 中C5 和C6 間的線路因C6 為折疊點(diǎn)而彎曲。這些線路要求在C5 和C6 之下留有垂直空間，以便能從棧1連到棧2。令ri 為Ci 是折疊點(diǎn)時(shí)所需的高度。棧1所需的高度為5 ?i =1hi +r6，棧2所需高度為8 ?i=6hi +r6+r9。
在標(biāo)準(zhǔn)單元設(shè)計(jì)中，電路首先被設(shè)計(jì)成為具有相同高度的符合線性順序的元件排列。假設(shè)此線性順序中的元件為C1，.，Cn，下一步元件被折疊成如圖1 5 - 11所示的相同寬度的行。在此圖中， 1 2個(gè)標(biāo)準(zhǔn)單元折疊成四個(gè)等寬行。折疊點(diǎn)是C4，C6 和C11。在相鄰標(biāo)準(zhǔn)單元行之間，使用布線通道來連接不同的行。折疊點(diǎn)決定了所需布線通道的高度。設(shè)li 表示當(dāng)Ci 為折疊點(diǎn)時(shí)所需的通道高度。在圖1 5 - 11的例子中，布線通道1的高度為l4，通道2的高度為l6，通道3的高度為l11。位－片棧折疊和標(biāo)準(zhǔn)單元折疊都會(huì)引出一系列的問題，這些問題可用動(dòng)態(tài)規(guī)劃方法來解決。
1. 等寬位－片元件折疊
定義r1 = rn+1 =0。由元件Ci 至Cj 構(gòu)成的棧的高度要求為j ?k= ilk+ ri+ rj + 1。設(shè)一個(gè)位－片設(shè)計(jì)中所有元件有相同寬度W。首先考察在折疊矩形的高度H給定的情況下，如何縮小其寬度。設(shè)Wi
為將元件Ci 到Cn 折疊到高為H的矩形時(shí)的最小寬度。若折疊不能實(shí)現(xiàn)（如當(dāng)ri +hi＞H時(shí)），取Wi =∞。注意到W1 可能是所有n 個(gè)元件的最佳折疊寬度。
當(dāng)折疊Ci 到Cn 時(shí)，需要確定折疊點(diǎn)。現(xiàn)假定折疊點(diǎn)是按棧左到棧右的順序來取定的。若第一點(diǎn)定為Ck+ 1，則Ci 到Ck 在第一個(gè)棧中。為了得到最小寬度，從Ck+1 到Cn 的折疊必須用最優(yōu)化方法，因此又將用到最優(yōu)原理，可用動(dòng)態(tài)規(guī)劃方法來解決此問題。當(dāng)?shù)谝粋€(gè)折疊點(diǎn)k+ 1已知時(shí)，可得到以下公式：
Wi =w+ Wk + 1 （1 5 - 9）
由于不知道第一個(gè)折疊點(diǎn)，因此需要嘗試所有可行的折疊點(diǎn)，并選擇滿足（ 1 5 - 9）式的折疊點(diǎn)。令h s u m(i,k)=k ?j = ihj。因k+ 1是一個(gè)可行的折疊點(diǎn)，因此h s u m(i, k) +ri +rk+1 一定不會(huì)超過H。
根據(jù)上述分析，可得到以下動(dòng)態(tài)規(guī)劃遞歸式：
這里Wn+1 =0，且在無最優(yōu)折疊點(diǎn)k+ 1時(shí)Wi 為∞。利用遞歸式（1 5 - 1 0），可通過遞歸計(jì)算Wn , Wn- 1., W2 , W1 來計(jì)算Wi。Wi 的計(jì)算需要至多檢查n-i+ 1個(gè)Wk+ 1，耗時(shí)為O (n-k)。因此計(jì)算所有Wi 的時(shí)間為O (n2 )。通過保留式（1 5 - 1 0）每次所得的k 值，可回溯地計(jì)算出各個(gè)最優(yōu)的折疊點(diǎn)，其時(shí)間耗費(fèi)為O (n)。
現(xiàn)在來考察另外一個(gè)有關(guān)等寬元件的折疊問題：折疊后矩形的寬度W已知，需要盡量減小其高度。因每個(gè)折疊矩形寬為w，因此折疊后棧的最大數(shù)量為s=W / w。令Hi, j 為Ci , ., Cn 折疊成一寬度為jw 的矩形后的最小高度， H1, s 則是所有元件折疊后的最小高度。當(dāng)j= 1時(shí)，不允許任何折疊，因此：Hi,1 =h s u m(i,n) +ri , 1≤i≤n
另外，當(dāng)i=n 時(shí)，僅有一個(gè)元件，也不可能折疊，因此：Hn ,j=hn+rn , 1≤j≤s
在其他情況下，都可以進(jìn)行元件折疊。如果第一個(gè)折疊點(diǎn)為k+ 1，則第一個(gè)棧的高度為
h s u m(i,k) +ri +rk+ 1。其他元件必須以至多(j- 1 ) *w 的寬度折疊。為保證該折疊的最優(yōu)性，其他元件也需以最小高度進(jìn)行折疊.
因?yàn)榈谝粋€(gè)折疊點(diǎn)未知，因此必須嘗試所有可能的折疊點(diǎn)，然后從中找出一個(gè)使式（1 5 - 11）的右側(cè)取最小值的點(diǎn)，該點(diǎn)成為第一個(gè)折疊點(diǎn)。
可用迭代法來求解Hi, j ( 1≤i≤n, 1≤j≤s)，求解的順序?yàn)椋合扔?jì)算j=2 時(shí)的H i, j，再算j= 3，.，以此類推。對(duì)應(yīng)每個(gè)j 的Hi, j 的計(jì)算時(shí)間為O (n2 )，所以計(jì)算所有H i, j 的時(shí)間為O(s n2 )。通過保存由（ 1 5 - 1 2）式計(jì)算出的每個(gè)k 值，可以采用復(fù)雜性為O (n) 的回溯過程來確定各個(gè)最優(yōu)的折疊點(diǎn)。
2. 變寬位－片元件的折疊
首先考察折疊矩形的高度H已定，欲求最小的折疊寬度的情況。令Wi 如式（1 5 - 1 0）所示，按照與（1 5 - 1 0）式相同的推導(dǎo)過程，可得：
Wi = m i n {w m i n(i, k) +Wk+1 | h s u m(i,k)+ ri +rk+ 1≤H, i≤k≤n} （1 5 - 1 3）
其中Wn+1=0且w m i n(i,k)= m ini≤j≤k{wj }。可用與（1 5 - 1 0）式一樣的方法求解（1 5 - 1 3）式，所需時(shí)間為O(n2 )。
當(dāng)折疊寬度W給定時(shí)，最小高度折疊可用折半搜索方法對(duì)超過O(n2 )個(gè)可能值進(jìn)行搜索來實(shí)現(xiàn)，可能的高度值為h(i,j)+ri +rj + 1。在檢測(cè)每個(gè)高度時(shí)，也可用（ 1 5 - 1 3）式來確定該折疊的寬度是否小于等于W。這種情況下總的時(shí)間消耗為O (n2 l o gn)。
3. 標(biāo)準(zhǔn)單元折疊
用wi 定義單元Ci 的寬度。每個(gè)單元的高度為h。當(dāng)標(biāo)準(zhǔn)單元行的寬度W 固定不變時(shí)，通過減少折疊高度，可以相應(yīng)地減少折疊面積。考察Ci 到Cn 的最小高度折疊。設(shè)第一個(gè)折疊點(diǎn)是Cs+ 1。從元件Cs+1 到Cn 的折疊必須使用最小高度，否則，可使用更小的高度來折疊Cs+1 到Cn，從而得到更小的折疊高度。所以這里仍可使用最優(yōu)原理和動(dòng)態(tài)規(guī)劃方法。
令Hi , s 為Ci 到Cn 折疊成寬為W的矩形時(shí)的最小高度，其中第一個(gè)折疊點(diǎn)為Cs+ 1。令w s u m(i, s)=s ?j = iwj。可假定沒有寬度超過W的元件，否則不可能進(jìn)行折疊。對(duì)于Hn,n 因?yàn)橹挥幸粋€(gè)元件，不存在連線問題，因此Hn, n =h。對(duì)于H i, s（1≤i＜s≤n）注意到如果w s u m(i, s )＞W(wǎng)，不可能實(shí)現(xiàn)折疊。若w s u m(i,s)≤W，元件Ci 和C j + 1 在相同的標(biāo)準(zhǔn)單元行中，該行下方布線通道的高度為ls+ 1（定義ln+1 = 0）。因而：Hi, s = Hi+1, k （1 5 - 1 4）
當(dāng)i=s＜n 時(shí)，第一個(gè)標(biāo)準(zhǔn)單元行只包含Ci 。該行的高度為h 且該行下方布線通道的高度為li+ 1。因Ci+ 1 到Cn 單元的折疊是最優(yōu)的.
為了尋找最小高度折疊，首先使用式（ 1 5 - 1 4）和（1 5 - 1 5）來確定Hi, s （1≤i≤s≤n）。最小高度折疊的高度為m in｛H1 , s｝。可以使用回溯過程來確定最小高度折疊中的折疊點(diǎn)。