只要這樣定義圖，根本不用在代碼中寫IF ELSE語句。
實際上基于圖的算法好處在于，只要你能定義好滿足題目要求的圖結構，遍歷的結果就是你要的結果，不用任何對遍歷結果做任何處理。包括本題中的：4不能在第三位置，3，5不能相連，唯一性要求，其實都可以在體現(xiàn)在構造的圖形結構里，然后直接遍歷圖取得自己要的結果。而不用再次處理結果集。只是說這里實際上對其它要求要體現(xiàn)在圖結構里有困難（理論上是可以的），但起碼3，5不能相接是很好構造的，就是上面的代碼段來解釋的。

關于圖形數(shù)據(jù)結構建議先看看數(shù)據(jù)結構的書，主要是將如何利用二維數(shù)組描述圖結構，再看看圖的深度遍歷實現(xiàn)原理。最后再應用到這個問題上來，自然就不難明白了。

（轉自：http://chinavery.100steps.net/chengxuyuan/4759.html）
動態(tài)規(guī)劃是本書介紹的五種算法設計方法中難度最大的一種，它建立在最優(yōu)原則的基礎上。采用動態(tài)規(guī)劃方法，可以優(yōu)雅而高效地解決許多用貪婪算法或分而治之算法無法解決的問題。在介紹動態(tài)規(guī)劃的原理之后，本章將分別考察動態(tài)規(guī)劃方法在解決背包問題、圖象壓縮、矩陣乘法鏈、最短路徑、無交叉子集和元件折疊等方面的應用。

3.1 算法思想

和貪婪算法一樣，在動態(tài)規(guī)劃中，可將一個問題的解決方案視為一系列決策的結果。不同的是，在貪婪算法中，每采用一次貪婪準則便做出一個不可撤回的決策，而在動態(tài)規(guī)劃中，還要考察每個最優(yōu)決策序列中是否包含一個最優(yōu)子序列。

例3-1 [最短路經] 考察圖1 2 - 2中的有向圖。假設要尋找一條從源節(jié)點s= 1到目的節(jié)點d= 5的最短路徑，即選擇此路徑所經過的各個節(jié)點。第一步可選擇節(jié)點2，3或4。假設選擇了節(jié)點3，則此時所要求解的問題變成：選擇一條從3到5的最短路徑。如果3到5的路徑不是最短的，則從1開始經過3和5的路徑也不會是最短的。例如，若選擇的子路徑（非最短路徑）是3，2，5 (耗費為9 )，則1到5的路徑為1，3，2，5 (耗費為11 )，這比選擇最短子路徑3，4，5而得到的1到5的路徑1，3，4，5 (耗費為9) 耗費更大。

所以在最短路徑問題中，假如在的第一次決策時到達了某個節(jié)點v，那么不管v 是怎樣確定的，此后選擇從v 到d 的路徑時，都必須采用最優(yōu)策略。

例3-2 [0/1背包問題] 考察1 3 . 4節(jié)的0 / 1背包問題。如前所述，在該問題中需要決定x1 .. xn的值。假設按i = 1，2，.，n 的次序來確定xi 的值。如果置x1 = 0，則問題轉變?yōu)橄鄬τ谄溆辔锲罚次锲?，3，.，n），背包容量仍為c 的背包問題。若置x1 = 1，問題就變?yōu)殛P于最大背包容量為c-w1 的問題。現(xiàn)設r?{c，c-w1 } 為剩余的背包容量。

在第一次決策之后，剩下的問題便是考慮背包容量為r 時的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之后的一個最優(yōu)方案，如果不是，則會有一個更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一個更好的方案。

假設n=3, w=[100,14,10], p=[20,18,15], c= 11 6。若設x1 = 1，則在本次決策之后，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因為[x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 并非最優(yōu)策略。即x= [ 1，0，1] 可改進為x= [ 1，1，0 ]。若設x1 = 0，則對于剩下的兩種物品而言，容量限制條件為11 6?？傊?，如果子問題的結果[x2，x3 ]不是剩余情況下的一個最優(yōu)解，則[x1，x2，x3 ]也不會是總體的最優(yōu)解。

例3-3 [航費] 某航線價格表為：從亞特蘭大到紐約或芝加哥，或從洛杉磯到亞特蘭大的費用為$ 1 0 0；從芝加哥到紐約票價$ 2 0；而對于路經亞特蘭大的旅客，從亞特蘭大到芝加哥的費用僅為$ 2 0。從洛杉磯到紐約的航線涉及到對中轉機場的選擇。如果問題狀態(tài)的形式為（起點，終點），那么在選擇從洛杉磯到亞特蘭大后，問題的狀態(tài)變?yōu)椋▉喬靥m大，紐約）。從亞特蘭大到紐約的最便宜航線是從亞特蘭大直飛紐約，票價$ 1 0 0。而使用直飛方式時，從洛杉磯到紐約的花費為$ 2 0 0。不過，從洛杉磯到紐約的最便宜航線為洛杉磯-亞特蘭大-芝加哥-紐約，其總花費為$ 1 4 0（在處理局部最優(yōu)路徑亞特蘭大到紐約過程中選擇了最低花費的路徑：亞特蘭大-芝加哥-紐約）。

如果用三維數(shù)組（t a g，起點，終點）表示問題狀態(tài)，其中t a g為0表示轉飛， t a g為1表示其他情形，那么在到達亞特蘭大后，狀態(tài)的三維數(shù)組將變?yōu)椋?0，亞特蘭大，紐約），它對應的最優(yōu)路徑是經由芝加哥的那條路徑。

當最優(yōu)決策序列中包含最優(yōu)決策子序列時，可建立動態(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)決策子序列組成。假設f (i,y) 表示例1 5 - 2中剩余容量為y，剩余物品為i，i + 1，.，n 時的最優(yōu)解的值，即：和利用最優(yōu)序列由最優(yōu)子序列構成的結論，可得到f 的遞歸式。f ( 1 ,c) 是初始時背包問題的最優(yōu)解。可使用（ 1 5 - 2）式通過遞歸或迭代來求解f ( 1 ,c)。從f (n, * )開始迭式， f (n, * )由（1 5 - 1）式得出，然后由（ 1 5 - 2）式遞歸計算f (i,*) ( i=n- 1，n- 2，.， 2 )，最后由（ 1 5 - 2）式得出f ( 1 ,c)。

對于例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)在計算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 計算x2 及x3，此時r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。

動態(tài)規(guī)劃方法采用最優(yōu)原則（ principle of optimality）來建立用于計算最優(yōu)解的遞歸式。所謂最優(yōu)原則即不管前面的策略如何，此后的決策必須是基于當前狀態(tài)（由上一次決策產生）的最優(yōu)決策。由于對于有些問題的某些遞歸式來說并不一定能保證最優(yōu)原則，因此在求解問題時有必要對它進行驗證。若不能保持最優(yōu)原則，則不可應用動態(tài)規(guī)劃方法。在得到最優(yōu)解的遞歸式之后，需要執(zhí)行回溯（t r a c e b a c k）以構造最優(yōu)解。

編寫一個簡單的遞歸程序來求解動態(tài)規(guī)劃遞歸方程是一件很誘人的事。然而，正如我們將在下文看到的，如果不努力地去避免重復計算，遞歸程序的復雜性將非常可觀。如果在遞歸程序設計中解決了重復計算問題時，復雜性將急劇下降。動態(tài)規(guī)劃遞歸方程也可用迭代方式來求解，這時很自然地避免了重復計算。盡管迭代程序與避免重復計算的遞歸程序有相同的復雜性，但迭代程序不需要附加的遞歸?？臻g，因此將比避免重復計算的遞歸程序更快。

3.2 應用

3.2.1 0/1背包問題

1. 遞歸策略

在例3 - 4中已建立了背包問題的動態(tài)規(guī)劃遞歸方程，求解遞歸式（ 1 5 - 2）的一個很自然的方法便是使用程序1 5 - 1中的遞歸算法。該模塊假設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的時間復雜性t (n)滿足：t ( 1 ) =a；t（n）≤2t（n- 1）+b（n＞1），其中a、b 為常數(shù)。通過求解可得t (n) =O( 2n)。

例3-5 設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 )，調用函數(shù)F ( 1 , 1 0 )。遞歸調用的關系如圖1 5 - 1的樹型結構所示。每個節(jié)點用y值來標記。對于第j層的節(jié)點有i=j，因此根節(jié)點表示F ( 1 , 1 0 )，而它有左孩子和右孩子，分別對應F ( 2 , 1 0 )和F ( 2 , 8 )?？偣矆?zhí)行了2 8次遞歸調用。但我們注意到，其中可能含有重復前面工作的節(jié)點，如f ( 3 , 8 )計算過兩次，相同情況的還有f ( 4 , 8 )、f ( 4 , 6 )、f ( 4 , 2 )、f ( 5 , 8 )、f ( 5 , 6 )、f ( 5 , 3 )、f (5,2) 和f ( 5 , 1 )。如果保留以前的計算結果，則可將節(jié)點數(shù)減至1 9，因為可以丟棄圖中的陰影節(jié)點。

正如在例3 - 5中所看到的，程序1 5 - 1做了一些不必要的工作。為了避免f (i,y)的重復計算，必須定義一個用于保留已被計算出的f (i,y)值的表格L，該表格的元素是三元組(i,y,f (i,y) )。在計算每一個f (i,y)之前，應檢查表L中是否已包含一個三元組(i,y, * )，其中*表示任意值。如果已包含，則從該表中取出f (i,y)的值，否則，對f (i,y)進行計算并將計算所得的三元組(i,y,f (i,y) )加入表L。L既可以用散列（見7 . 4節(jié)）的形式存儲，也可用二叉搜索樹(見11章)的形式存儲。

2. 權為整數(shù)的迭代方法

當權為整數(shù)時，可設計一個相當簡單的算法（見程序1 5 - 2）來求解f ( 1 ,c)。該算法基于例3 - 4所給出的策略，因此每個f (i,y) 只計算一次。程序1 5 - 2用二維數(shù)組f [ ][ ]來保存各f 的值。而回溯函數(shù)Tr a c e b a c k用于確定由程序1 5 - 2所產生的xi 值。函數(shù)K n a p s a c k的復雜性為( n c），而Tr a c e b a c k的復雜性為( n )。

程序15-2 f 和x 的迭代計算

template<class T>

void Knapsack(T p[], int w[], int c, int n, T** f)

{// 對于所有i和y計算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];

// 計算剩下的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[])

{// 計算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有兩個缺點：1) 要求權為整數(shù)；2) 當背包容量c 很大時，程序1 5 - 2的速度慢于程序1 5 - 1。一般情況下，若c＞2n，程序1 5 - 2的復雜性為W (n2n )?？衫迷M的方法來克服上述兩個缺點。在元組方法中，對于每個i，f (i, y) 都以數(shù)對(y, f (i, y)) 的形式按y的遞增次序存儲于表P(i)中。同時，由于f (i, y) 是y 的非遞減函數(shù)，因此P(i) 中各數(shù)對(y, f (i, y)) 也是按f (i, y) 的遞增次序排列的。

例3-6 條件同例3 - 5。對f 的計算如圖1 5 - 2所示。當i= 5時，f 由數(shù)對集合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ù)對( 6，9 ) )，因此f ( 1 , 1 0 ) = m a x｛11 , 1 5｝= 1 5?，F(xiàn)在來求xi 的值，因為f ( 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。

檢查每個P(i) 中的數(shù)對，可以發(fā)現(xiàn)每對(y,f (i,y)) 對應于變量xi , ., xn 的0/1 賦值的不同組合。設（a,b）和（c,d）是對應于兩組不同xi , ., xn 的0 / 1賦值，若a≥c且b＜d，則(a, b) 受(b, c) 支配。被支配者不必加入P(i)中。若在相同的數(shù)對中有兩個或更多的賦值，則只有一個放入P(i)。假設wn≤C，P(n)=[(0,0), (wn , pn ) ]，P（n）中對應于xn 的兩個數(shù)對分別等于0和1。對于每個i，P(i)可由P(i+ 1 )得出。首先，要計算數(shù)對的有序集合Q，使得當且僅當wi≤s≤c且(s-wi , t-pi )為P(i+1) 中的一個數(shù)對時，（s,t）為Q中的一個數(shù)對。現(xiàn)在Q中包含xi = 1時的數(shù)對集，而P(i+ 1 )對應于xi = 0的數(shù)對集。接下來，合并Q和P(i+ 1 )并刪除受支配者和重復值即可得到P(i)。

例3-7 各數(shù)據(jù)同例1 5 - 6。P(5)=[(0,0),(4,6)], 因此Q= [ ( 5 , 4 ) , ( 9 , 1 0 ) ]?，F(xiàn)在要將P( 5 )和Q合并得到P( 4 )。因( 5 , 4 )受( 4 , 6 )支配，可刪除( 5 , 4 )，所以P（4）=[(0,0), (4,6), (9,10)]。接著計算P( 3 )，首先由P( 4 )得Q=[(6,5), (10,11 ) ]，然后又由合并方法得P(3)=[(0,0), (4,6), (9,10), (10,11 ) ]。最后計算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 ) ]。因為每個P(i) 中的數(shù)對對應于xi , ., xn 的不同0 / 1賦值，因此P(i) 中的數(shù)對不會超過2n-i+ 1個。計算P(i) 時，計算Q需消耗( |P(i+ 1 ) |）的時間，合并P(i+1) 和Q同樣需要( |P(i+ 1 ) | )的時間。計算所有P(i) 時所需要的總時間為： (n ?i=2|P(i + 1)|= O ( 2n )。當權為整數(shù)時，|P(i) |≤c+1, 此時復雜性為O ( m i n {n c, 2n } )。

如6 . 4 . 3節(jié)定義的，數(shù)字化圖像是m×m的像素陣列。假定每個像素有一個0 ~ 2 5 5的灰度值。因此存儲一個像素至多需8位。若每個像素存儲都用最大位8位，則總的存儲空間為8m2 位。為了減少存儲空間，我們將采用變長模式（ variable bit scheme），即不同像素用不同位數(shù)來存儲。像素值為0和1時只需1位存儲空間；值2、3各需2位；值4，5，6和7各需3位；以此類推，使用變長模式的步驟如下：

1) 圖像線性化根據(jù)圖15-3a 中的折線將m×m維圖像轉換為1×m2 維矩陣。

2) 分段將像素組分成若干個段，分段原則是：每段中的像素位數(shù)相同。每個段是相鄰像素的集合且每段最多含2 5 6個像素，因此，若相同位數(shù)的像素超過2 5 6個的話，則用兩個以上的段表示。

3) 創(chuàng)建文件創(chuàng)建三個文件：S e g m e n t L e n g t h, BitsPerPixel 和P i x e l s。第一個文件包含在2 )中所建的段的長度(減1 )，文件中各項均為8位長。文件BitsPerPixel 給出了各段中每個像素的存儲位數(shù)（減1），文件中各項均為3位。文件Pixels 則是以變長格式存儲的像素的二進制串。

4) 壓縮文件壓縮在3) 中所建立的文件，以減少空間需求。

上述壓縮方法的效率（用所得壓縮率表示）很大程度上取決于長段的出現(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，按等長的條件將像素分段，可以得到4個段[ 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 的內容為3，5，3，7；文件P i x e l s包含了按蛇形行主次序排列的1 6個灰度值，其中頭三個各用4位存儲，接下來三個各用6位，再接下來的七個各用4位，最后三個各用8位存儲。因此存儲單元中前3 0位存儲了前六個像素：

1010 1001 1100 111000 110010 100011

這三個文件需要的存儲空間分別為：文件SegmentLength 需3 2位；BitsPerSegment 需1 2位；Pixels 需8 2位，共需1 2 6位。而如果每個像素都用8位存儲，則存儲空間需8×1 6 = 1 2 8位，因而在本例圖像中，節(jié)省了2位的空間。

假設在2) 之后，產生了n 個段。段標題（segment header）用于存儲段的長度以及該段中每個像素所占用的位數(shù)。每個段標題需11位。現(xiàn)假設li 和bi 分別表示第i 段的段長和該段每個像素的長度，則存儲第i 段像素所需要的空間為li *bi 。在2) 中所得的三個文件的總存儲空間為11 n+n ?i = 1li bi。可通過將某些相鄰段合并的方式來減少空間消耗。如當段i 和i+ 1被合并時，合并后的段長應為li +li + 1。此時每個像素的存儲位數(shù)為m a x {bi，bi +1 } 位。盡管這種技術增加了文件P i x e l s的空間消耗，但同時也減少了一個段標題的空間。

例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位存儲的是合并后的第一段：001010 001001 001100 111000 110010 100011其余的像素（例1 5 - 8第3段）沒有改變。因為減少了1個段標題，文件S e g m e n t L e n g t h和BitsPerPixel 的空間消耗共減少了11位，而文件Pixels 的空間增加6位，因此總共節(jié)約的空間為5位，空間總消耗為1 2 1位。

我們希望能設計一種算法，使得在產生n 個段之后，能對相鄰段進行合并，以便產生一個具有最小空間需求的新的段集合。在合并相鄰段之后，可利用諸如L Z W法（見7 . 5節(jié)）和霍夫曼編碼（見9 . 5 . 3節(jié)）等其他技術來進一步壓縮這三個文件。

令sq 為前q 個段的最優(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)合并，那么需要對合并進行修改，以使其具有更小的空間需求。因此還必須對段1到段i-r 進行最優(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 (因為段長限制在2 5 6之內)。盡管我們不知道如何選擇r，但我們知道，由于C具有最小的空間需求，因此在所有選擇中， r 必須產生最小的空間需求。

假定k a yi 表示取得最小值時k 的值，sn 為n 段的最優(yōu)合并所需要的空間，因而一個最優(yōu)合并可用kay 的值構造出來。

例3-10 假定在2) 中得到五個段，它們的長度為[ 6，3，1 0，2，3 ]，像素位數(shù)為[ 1，2，3，2，1 ]，要用公式（1 5 - 3）計算sn，必須先求出sn-1，.，s0 的值。s0 為0，現(xiàn)計算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 ]。因為s5 = 8 2，所以最優(yōu)空間合并需8 2位的空間。可由k a y5 導出本合并的方式，過程如下：因為k a y5 = 4，所以s5 是由公式（1 5 - 3）在k=4 時取得的，因而最優(yōu)合并包括：段1到段( 5 - 4 ) = 1的最優(yōu)合并以及段2，3，4和5的合并。最后僅剩下兩個段：段1以及段2到段5的合并段。

1. 遞歸方法

用遞歸式（1 5 - 3）可以遞歸地算出si 和k a yi。程序1 5 - 3為遞歸式的計算代碼。l，b，和k a y是一維的全局整型數(shù)組，L是段長限制（ 2 5 6），h e a d e r為段標題所需的空間( 11 )。調用S ( n )返回sn 的值且同時得出k a y值。調用Tr a c e b a c k ( k a y, n )可得到最優(yōu)合并。

現(xiàn)討論程序1 5 - 3的復雜性。t( 0 ) =c（c 為一個常數(shù)）： （n＞0），因此利用遞歸的方法可得t (n) = O ( 2n )。Tr a c e b a c k的復雜性為(n)。

程序15-3 遞歸計算s , k a y及最優(yōu)合并

int S(int i)

{ / /返回S ( i )并計算k a y [ i ]

if (i == 0 ) return 0;

//k = 1時, 根據(jù)公式（ 1 5 - 3）計算最小值

int lsum = l[i],bmax = b[i];

int s = S(i-1) + lsum * bmax;

kay[i] = 1;

/ /對其余的k計算最小值并求取最小值

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. 無重復計算的遞歸方法

通過避免重復計算si，可將函數(shù)S的復雜性減少到(n)。注意這里只有n個不同的si。

例3 - 11 再考察例1 5 - 1 0中五個段的例子。當計算s5 時，先通過遞歸調用來計算s4，.，s0。計算s4 時，通過遞歸調用計算s3，.，s0，因此s4 只計算了一次，而s3 計算了兩次，每一次計算s3要計算一次s2，因此s2 共計算了四次，而s1 重復計算了1 6次！可利用一個數(shù)組s 來保存先前計算過的si 以避免重復計算。改進后的代碼見程序1 5 - 4，其中s為初值為0的全局整型數(shù)組。

程序15-4 避免重復計算的遞歸算法

int S(int i)

{ / /計算S ( i )和k a y [ i ]

/ /避免重復計算

if (i == 0) return 0;

if (s[i] > 0) return s[i]; //已計算完

/ /計算s [ i ]

/ /首先根據(jù)公式（1 5 - 3）計算k = 1時最小值

int lsum = l[i], bmax = b[i];

s[i] =S(i-1) + lsum * bmax;

kay[i] = 1;

/ /對其余的k計算最小值并更新

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的時間復雜性，我們將使用分期計算模式（ amortization scheme）。在該模式中，總時間被分解為若干個不同項，通過計算各項的時間然后求和來獲得總時間。當計算si 時，若sj 還未算出，則把調用S(j) 的消耗計入sj ；若sj 已算出，則把S(j) 的消耗計入si (這里sj依次把計算新sq 的消耗轉移至每個sq )。程序1 5 - 4的其他消耗也被計入si。因為L是2 5 6之內的常數(shù)且每個li 至少為1，所以程序1 5 - 4的其他消耗為( 1 )，即計入每個si 的量是一個常數(shù)，且si 數(shù)目為n，因而總工作量為(n)。

3. 迭代方法

倘若用式（1 5 - 3）依序計算s1 , ., sn，便可得到一個復雜性為(n)的迭代方法。在該方法中，在si 計算之前， sj 必須已計算好。該方法的代碼見程序1 5 - 5，其中仍利用函數(shù)Tr a c e b a c k（見程序1 5 - 3）來獲得最優(yōu)合并。

程序15-5 迭代計算s和k a y

void Vbits (int l[], int b[], int n, int s[], int kay[])

{ / /計算s [ i ]和k a y [ i ]

int L = 256, header = 11 ;

s[0] = 0;

/ /根據(jù)式（1 5 - 3）計算s [ i ]

for (int i = 1; i <= n; i++) {

// k = 1時,計算最小值

int lsum = l,

bmax = b[i];

s[i] = s[i-1] + lsum * bmax;

kay[i] = 1;

/ /對其余的k計算最小值并更新

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相乘需耗費(m n p)的時間（見第2章練習1 6）。我們把m n p作為兩個矩陣相乘所需時間的測量值?，F(xiàn)假定要計算三個矩陣A、B和C的乘積，有兩種方式計算此乘積。在第一種方式中，先用A乘以B得到矩陣D，然后D乘以C得到最終結果，這種乘法的順序可寫為(A*B) *C。第二種方式寫為A* (B*C) ,道理同上。盡管這兩種不同的計算順序所得的結果相同，但時間消耗會有很大的差距。

例3-12 假定A為1 0 0×1矩陣，B為1×1 0 0矩陣，C為1 0 0×1矩陣，則A*B的時間耗費為10 0 0 0，得到的結果D為1 0 0×1 0 0矩陣，再與C相乘所需的時間耗費為1 000 000，因此計算(A*B) *C的總時間為1 010 000。B*C的時間耗費為10 000，得到的中間矩陣為1×1矩陣，再與A相乘的時間消耗為1 0 0，因而計算A*（B*C）的時間耗費竟只有10 100！而且，計算（ A*B）*C時，還需10 000個單元來存儲A*B，而A*（B*C）計算過程中，只需用1個單元來存儲B*C。

下面舉一個得益于選擇合適秩序計算A*B*C矩陣的實例：考慮兩個3維圖像的匹配。圖像匹配問題的要求是，確定一個圖像需旋轉、平移和縮放多少次才能逼近另一個圖像。實現(xiàn)匹配的方法之一便是執(zhí)行約1 0 0次迭代計算，每次迭代需計算1 2×1個向量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) 為矩陣中向量的坐標。設t 表示計算A(x , y, z) *B(x , y, z) *C(x , y, z)的計算量。假定此圖像含2 5 6×2 5 6×2 5 6個向量，在此條件中，這1 0 0個迭代所需的總計算量近似為1 0 0 * 2 5 63 * t≈1 . 7 * 1 09 t。若三個矩陣是按由左向右的順序相乘的，則t = 1 2 * 3 * 3 + 1 2 * 3 *1= 1 4 4；但如果從右向左相乘， t = 3 * 3 * 1 + 1 2 * 3 * 1 = 4 5。由左至右計算約需2 . 4 * 1 011個操作，而由右至左計算大概只需7 . 5 * 1 01 0個操作。假如使用一個每秒可執(zhí)行1億次操作的計算機，由左至右需4 0分鐘，而由右至左只需1 2 . 5分鐘。

在計算矩陣運算A*B*C時，僅有兩種乘法順序（由左至右或由右至左），所以可以很容易算出每種順序所需要的操作數(shù)，并選擇操作數(shù)比較少的那種乘法順序。但對于更多矩陣相乘來說，情況要復雜得多。如計算矩陣乘積M1×M2×.×Mq，其中Mi 是一個ri×ri + 1 矩陣( 1≤i≤q)。不妨考慮q=4 的情況，此時矩陣運算A*B*C*D可按以下方式（順序）計算：

A* ( (B*C) *D) A* (B* (C*D)) (A*B) * (C*D) (A* (B*C) ) *D

不難看出計算的方法數(shù)會隨q 以指數(shù)級增加。因此，對于很大的q 來說，考慮每一種計算順序并選擇最優(yōu)者已是不切實際的。

現(xiàn)在要介紹一種采用動態(tài)規(guī)劃方法獲得矩陣乘法次序的最優(yōu)策略。這種方法可將算法的時間消耗降為(q3 )。用Mi j 表示鏈Mi×.×Mj （i≤j）的乘積。設c(i,j) 為用最優(yōu)法計算Mi j 的消耗，k a y(i, j) 為用最優(yōu)法計算Mi j 的最后一步Mi k×Mk+1, j 的消耗。因此Mij 的最優(yōu)算法包括如何用最優(yōu)算法計算Mik 和Mkj 以及計算Mik×Mkj 。根據(jù)最優(yōu)原理，可得到如下的動態(tài)規(guī)劃遞歸式：k a y(i,i+s)= 獲得上述最小值的k. 以上求c 的遞歸式可用遞歸或迭代的方法來求解。c( 1，q) 為用最優(yōu)法計算矩陣鏈的消耗，k a y( 1 ,q) 為最后一步的消耗。其余的乘積可由k a y值來確定。

1. 遞歸方法

與求解0 / 1背包及圖像壓縮問題一樣，本遞歸方法也須避免重復計算c (i, j) 和k a y(i, j)，否則算法的復雜性將會非常高。

例3-13 設q= 5和r =（1 0 , 5 , 1 , 1 0 , 2 , 1 0），式中待求的c 中有四個c的s= 0或1，因此用動態(tài)規(guī)劃方法可立即求得它們的值： c( 1 , 1 ) =c( 5 , 5 ) = 0 ;c(1,2)=50; c( 4 , 5 ) = 2 0 0。現(xiàn)計算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 。再用遞歸式計算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由以上計算還可得k a y( 3 , 5 ) = 4，k ay( 2 , 4 ) = 2。現(xiàn)在,計算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）計算c( 1 , 5 )，在此之前必須算出c( 3 , 5 )、c(1,3) 和c( 1 , 4 )。同上述過程，亦可計算出它們的值分別為4 0、1 5 0和9 0，相應的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)法計算而來。由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

計算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) (對于任何a , b)，其中c(a , b)在計算c(i,j) 時皆已算出。函數(shù)Traceback 利用函數(shù)C中已算出的k a y值來推導出最優(yōu)乘法算法的步驟。

設t(q)為函數(shù)C的復雜性，其中q=j-i+ 1（即Mij 是q個矩陣運算的結果）。當q為1或2時，t(q) =d，其中d 為一常數(shù)；而q> 2時，t (q)=2q-1?k = 1t (k ) +e q，其中e 是一個常量。因此當q＞2時，t(q)＞2t (q- 1 ) +e，所以t (q)= W ( 2q)。函數(shù)Traceback 的復雜性為(q)。

程序15-6 遞歸計算c (i, j) 和kay (i, j)

int C(int i, int j)

{ / /返回c(i,j) 且計算k(i,j) = kay[i][j]

if (i==j) return 0; //一個矩陣的情形

if (i == j-1) { //兩個矩陣的情形

kay[i][i+1] = i;

return r[i]*r[i+1]*r[r+2];}

/ /多于兩個矩陣的情形

/ /設u為k = i 時的最小值

int u = C(i,i) + C(i+1,j) + r[i]*r[i+1]*r[j+1];

kay[i][j] = i;

/ /計算其余的最小值并更新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)

{ / /輸出計算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. 無重復計算的遞歸方法

若避免再次計算前面已經計算過的c（及相應的k a y），可將復雜性降低到（q3）。而為了避免重復計算，需用一個全局數(shù)組c[ ][ ]存儲c(i, j) 值，該數(shù)組初始值為0。函數(shù)C的新代碼見程序1 5 - 7：

程序15-7 無重復計算的c (i, j) 計算方法

int C(int i,int j)

{ / /返回c(i,j) 并計算k a y ( i , j ) = k a y [ I ] [ j ]

/ /避免重復計算

/ /檢查是否已計算過

if （c[i][j] >） return c[i][j];

/ /若未計算,則進行計算

if(i==j) return 0; //一個矩陣的情形

i f ( i = = j - 1 ) { / /兩個矩陣的情形

kay[i][i+1]=i;

c [ i ] [ j ] = r [ i ] * r [ i + 1 ] * r [ i + 2 ] ;

return c[i][j];}

/ /多于兩個矩陣的情形

/ /設u為k = i 時的最小值

int u=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];

k a y [ i ] [ j ] = i ;

/ /計算其余的最小值并更新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;

}

為分析改進后函數(shù)C 的復雜性，再次使用分期計算方法。注意到調用C(1, q) 時每個c (i, j)（1≤i≤j≤q）僅被計算一次。要計算尚未計算過的c(a,b)，需附加的工作量s =j-i＞1。將s 計入第一次計算c (a, b) 時的工作量中。在依次計算c(a, b) 時，這個s 會轉計到每個c (a, b) 的第一次計算時間c 中，因此每個c (i, i) 均被計入s。對于每個s，有q-s+ 1個c(i, j) 需要計算，因此總的工作消耗為q-1 ?s=1(q-s+ 1) = (q3 )。

3. 迭代方法

c 的動態(tài)規(guī)劃遞歸式可用迭代的方法來求解。若按s = 2，3，.，q-1 的順序計算c (i, i+s)，每個c 和kay 僅需計算一次。

例3-14 考察例3 - 1 3中五個矩陣的情況。先初始化c (i, i) (0≤i≤5) 為0，然后對于i=1, ., 4分別計算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。相應的k ay 值分別為1，2，3和4。

當s= 2時，可得：

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，相應k a y值分別為2和3。

當s= 3時，需計算c(1,4) 和c( 2 , 5 )。計算c(2,5) 所需要的所有中間值均已知(見( 1 5 - 5 )式)，代入計算公式后可得c( 2 , 5 ) = 9 0，k a y( 2 , 5 ) = 2。c( 1 , 4 )可用同樣的公式計算。最后，當s= 4時，可直接用（1 5 - 4）式來計算c( 1 , 5 )，因為該式右邊所有項都已知。

計算c 和kay 的迭代程序見函數(shù)M a t r i x C h a i n（見程序1 5 - 8），該函數(shù)的復雜性為(q3 )。計算出kay 后同樣可用程序1 5 - 6中的Traceback 函數(shù)推算出相應的最優(yōu)乘法計算過程。

程序15-8 c 和kay 的迭代計算

void MatrixChain(int r[], int q, int **c, int **kay)

{// 為所有的Mij 計算耗費和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;

/ /計算余下的c和k a y

for (int s = 2; s < q; s++)

for (int i = 1; i <= q - s; i++) {

// k = i時的最小項

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;

// 余下的最小項

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]) {// 更小的最小項

c[i][i+s] = t;

kay[i][i+s] = k;}

}

}

}

3.2.4 最短路徑

假設G為有向圖，其中每條邊都有一個長度（或耗費），圖中每條有向路徑的長度等于該路徑中各邊的長度之和。對于每對頂點(i, j)，在頂點i 與j 之間可能有多條路徑，各路徑的長度可能各不相同。我們定義從i 到j 的所有路徑中，具有最小長度的路徑為從i 到j 的最短路徑。

例3-15 如圖1 5 - 4所示。從頂點1到頂點3的路徑有

1) 1,2,5,3

2) 1,4,3

3) 1,2,5,8,6,3

4) 1,4,6,3

由該圖可知,各路徑相應的長度為1 0、2 8、9、2 7，因而路徑3) 是該圖中頂點1到頂點3的最短路徑。

在所有點對最短路徑問題（ a l l - p a i r sshorest-paths problem）中，要尋找有向圖G中每對頂點之間的最短路徑。也就是說，對于每對頂點(i, j)，需要尋找從i到j 的最短路徑及從j 到i 的最短路徑。因此對于一個n 個頂點的圖來說，需尋找p =n(n-1) 條最短路徑。假定圖G中不含有長度為負數(shù)的環(huán)路，只有在這種假設下才可保證G中每對頂點(i, j) 之間總有一條不含環(huán)路的最短路徑。當有向圖中存在長度小于0的環(huán)路時，可能得到長度為－∞的更短路徑，因為包含該環(huán)路的最短路徑往往可無限多次地加上此負長度的環(huán)路。

設圖G中n 個頂點的編號為1到n。令c (i, j, k)表示從i 到j 的最短路徑的長度，其中k 表示該路徑中的最大頂點。因此，如果G中包含邊<i, j>，則c(i, j, 0) =邊<i, j> 的長度；若i= j ，則c(i,j, 0)=0；如果G中不包含邊<i, j>，則c (i, j, 0)= +∞。c(i, j, n) 則是從i 到j 的最短路徑的長度。

例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的最短路徑長度為9。對于任意k＞0，如何確定c (i, j, k) 呢？中間頂點不超過k 的i 到j 的最短路徑有兩種可能：該路徑含或不含中間頂點k。若不含，則該路徑長度應為c(i, j, k- 1 )，否則長度為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

以上的遞歸公式將一個k 級運算轉化為多個k-1 級運算，而多個k-1 級運算應比一個k 級運算簡單。如果用遞歸方法求解上式，則計算最終結果的復雜性將無法估量。令t (k) 為遞歸求解c (i, j, k) 的時間。根據(jù)遞歸式可以看出t(k) = 2t(k- 1 ) +c。利用替代方法可得t(n) = ( 2n )。因此得到所有c (i, j, n) 的時間為(n2 2n )。

當注意到某些c (i, j, k-1) 值可能被使用多次時，可以更高效地求解c (i, j, n)。利用避免重復計算c(i, j, k) 的方法，可將計算c 值的時間減少到(n3 )。這可通過遞歸方式（見程序1 5 - 7矩陣鏈問題）或迭代方式來實現(xiàn)。出迭代算法的偽代碼如圖1 5 - 5所示。

?

/ /尋找最短路徑的長度

/ /初始化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 是長度鄰接矩陣

/ /計算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 最短路徑算法的偽代碼

?

注意到對于任意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) 值。此時圖1 5 - 5可改寫成程序1 5 - 9的C + +代碼。程序1 5 - 9中還利用了程序1 2 - 1中定義的AdjacencyWDigraph 類。函數(shù)AllPairs 在c 中返回最短路徑的長度。若i 到j 無通路，則c [i] [j]被賦值為N o E d g e。函數(shù)AllPairs 同時計算了k a y [ i ] [ j ]，其中kay[i][j] 表示從i 到j 的最短路徑中最大的k 值。在后面將看到如何根據(jù)kay 值來推斷出從一個頂點到另一頂點的最短路徑（見程序1 5 - 1 0中的函數(shù)O u t p u t P a t h）。

程序1 5 - 9的時間復雜性為(n3 )，其中輸出一條最短路徑的實際時間為O (n)。

程序15-9 c 和kay 的計算

template<class T>

void AdjacencyWDigraph<T>::Allpairs(T **c, int **kay)

{ / /所有點對的最短路徑

/ /對于所有i和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;

// 計算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 的路徑的實際代碼

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的最短路徑

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 給出某圖的長度矩陣a，15-6b 給出由程序1 5 - 9所計算出的c 矩陣，15-6c 為對應的k a y值。根據(jù)15-6c 中的kay 值，可知從1到5的最短路徑是從1到k a y [ 1 ] [ 5 ] = 4的最短路徑再加上從4到5的最短路徑，因為k a y [ 4 ] [ 5 ] = 0，所以從4到5的最短路徑無中間頂點。從1到4的最短路徑經過k a y [ 1 ] [ 4 ] = 3。重復以上過程，最后可得1到5的最短路徑為：1，2，3，4，5。

3.2.5 網絡的無交叉子集

在11 . 5 . 3節(jié)的交叉分布問題中，給定一個每邊帶n 個針腳的布線通道和一個排列C。頂部的針腳i 與底部的針腳Ci 相連，其中1≤i≤n，數(shù)對(i, Ci ) 稱為網組?？偣灿衝 個網組需連接或連通。假設有兩個或更多的布線層，其中有一個為優(yōu)先層，在優(yōu)先層中可以使用更細的連線，其電阻也可能比其他層要小得多。布線時應盡可能在優(yōu)先層中布設更多的網組。而剩下的其他網組將布設在其他層。當且僅當兩個網組之間不交叉時，它們可布設在同一層。我們的任務是尋找一個最大無交叉子集（Maximum Noncrossing Su b s e t，M N S )。在該集中，任意兩個網組都不交叉。因(i, Ci ) 完全由i 決定，因此可用i 來指定(i, Ci )。

例3-18 考察圖1 5 - 7（對應于圖1 0 - 1 7）。( 1 , 8 )和( 2 , 7 )（也即1號網組和2號網組）交叉，因而不能布設在同一層中。而( 1 , 8 )，(7,9) 和(9,10) 未交叉，因此可布設在同一層。但這3個網組并不能構成一個M N S，因為還有更大的不交叉子集。圖1 0 - 1 7中給出的例子中，集合｛ ( 4 , 2 ) ,( 5 , 5 ) , ( 7 , 9 ) , ( 9 , 1 0 )｝是一個含4個網組的M N S。

設M N S(i, j) 代表一個M N S，其中所有的(u, Cu ) 滿足u≤i，Cu≤j。令s i z e(i,j) 表示M N S(i,j)的大小(即網組的數(shù)目)。顯然M N S(n,n)是對應于給定輸入的M N S，而s i z e(n,n)是它的大小。

例3-19 對于圖1 0 - 1 7中的例子，M N S( 1 0 , 1 0 )是我們要找的最終結果。如例3 - 1 8中所指出的，s i z e( 1 0 , 1 0 ) = 4，因為( 1 , 8 )，( 2 , 7 )，( 7 , 9 )，( 8 , 3 )，( 9 , 1 0 )和( 1 0 , 6 )中要么頂部針腳編號比7大，要么底部針腳編號比6大，因此它們都不屬于M N S( 7 , 6 )。因此只需考察剩下的4個網組是否屬于M N S( 7 , 6 )，如圖1 5 - 8所示。子集｛( 3 , 4 ) , ( 5 , 5 )｝是大小為2的無交叉子集。沒有大小為3的無交叉子集，因此s i z e( 7 , 6) = 2。

當i= 1時，( 1 ,C1) 是M N S( 1 ,j) 的唯一候選。僅當j≥C1 時，這個網組才會是M N S( 1 ,j) 的一個成員.

下一步，考慮i＞1時的情況。若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) 內。若(i,Ci ) 在M N S(i,j) 內，則在M N S(i,j)中不會有這樣的(u,Cu )：u＜i且Cu＞Ci，因為這個網組必與(i, Ci ) 相交。因此M N S(i,j) 中的其他所有成員都必須滿足條件u＜i且Cu＜Ci。在M N S(i,j) 中這樣的網組共有Mi- 1 , Ci- 1 個。若(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）式可用遞歸法求解，但從前面的例子可以看出，即使避免了重復計算，動態(tài)規(guī)劃遞歸算法的效率也不夠高，因此只考慮迭代方法。在迭代過程中先用式（1 5 - 6）計算出s i ze ( 1 ,j)，然后再用式（1 5 - 7）和（1 5 - 8）按i=2, 3, ., n 的順序計算s i ze (i,j)，最后再用Traceback 來得到M N S(n, n) 中的所有網組。

例3-20 圖1 5 - 9給出了圖1 5 - 7對應的s i z e(i,j) 值。因s i z e( 1 0 , 1 0) = 4，可知M N S含4個網組。為求得這4個網組，先從s i ze ( 1 0 , 1 0 )入手。可用（1 5 - 8）式算出s i z e( 1 0 , 1 0 )。根據(jù)式（1 5 - 8）時的產生原因可知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號網組。M N S(9,10) 中剩下的網組組成M NS ( 8 , C9- 1)=M N S( 8 , 9 )。由M N S( 8 , 9 ) =M NS (7,9) 知，8號網組可以被排除。接下來要求M N S( 7 , 9 )，因為s i z e( 7 , 9 )≠s i z e( 6 , 9 )，所以M N S中必含7號網組。M NS (7,9) 中余下的網組組成M NS ( 6 , C7- 1 ) =M N S( 6 , 8 )。根據(jù)s i z e( 6 , 8 ) =s i z e( 5 , 8 )可排除6號網組。按同樣的方法， 5號網組，3號網組加入M N S中，而4號網組等其他網組被排除。因此回溯過程所得到的大小為4的M N S為{ 3 , 5 , 7 , 9 }。

注意到在回溯過程中未用到s i z e( 1 0 ,j) (j≠1 0 )，因此不必計算這些值。

程序1 5 - 11給出了計算s i z e ( i , j ) 的迭代代碼和輸出M N S的代碼。函數(shù)M N S用來計算s i ze (i,j) 的值，計算結果用一個二維數(shù)組M N來存儲。size[i][j] 表示s i z e(i,j)，其中i=j= n 或1≤i＜n，0≤j≤n，計算過程的時間復雜性為(n2 )。函數(shù)Traceback 在N et［0 : m - 1］中輸出所得到的M N S，其時間復雜性為(n)。因此求解M M S問題的動態(tài)規(guī)劃算法的總的時間復雜性

為(n2 )。

程序1 5 - 11 尋找最大無交叉子集

void MNS(int C[], int n, int **size)

{ / /對于所有的i 和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;

// 計算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; // 所允許的底部最大針腳編號

m = 0; // 網組的游標

for (int i = n; i > 1; i--)

// i 號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號網組在M N S中?

if (j >= C[1])

Net[m++] = 1; // 在M N S中

}

3.2.6 元件折疊

在設計電路的過程中，工程師們會采取多種不同的設計風格。其中的兩種為位－片設計（bit-slice design）和標準單元設計（standard-cell design）。在前一種方法中，電路首先被設計為一個元件棧（如圖15-10a 所示）。每個元件Ci 寬為wi ，高為hi ，而元件寬度用片數(shù)來表示。圖15-10a 給出了一個四片的設計。線路是按片來連接各元件的，即連線可能連接元件Ci 的第j片到元件Ci+1 的第j 片。如果某些元件的寬度不足j 片，則這些元件之間不存在片j 的連線。當圖1 5 -10a 的位－片設計作為某一大系統(tǒng)的一部分時，則在V L SI ( Very Large Scale Integrated) 芯片上為它分配一定數(shù)量的空間單元。分配是按空間寬度或高度的限制來完成的?，F(xiàn)在的問題便是如何將元件棧折疊到分配空間中去，以便盡量減小未受限制的尺度（如，若高度限制為H時，必須折疊棧以盡量減小寬度W）。由于其他尺度不變，因此縮小一個尺度（如W）等價于縮小面積?？捎谜劬€方式來折疊元件棧，在每一折疊點，元件旋轉1 8 0°。在圖15-10b 的例子中，一個1 2元件的棧折疊成四個垂直棧，折疊點為C6 , C9 和C1 0。折疊棧的寬度是寬度最大的元件所需的片數(shù)。在圖15-10b 中，棧寬各為4，3，2和4。折疊棧的高度等于各棧所有元件高度之和的最大值。在圖15-10b 中棧1的元件高度之和最大，該棧的高度決定了包圍所有棧的矩形高度。

實際上，在元件折疊問題中，還需考慮連接兩個棧的線路所需的附加空間。如，在圖1 5 -10b 中C5 和C6 間的線路因C6 為折疊點而彎曲。這些線路要求在C5 和C6 之下留有垂直空間，以便能從棧1連到棧2。令ri 為Ci 是折疊點時所需的高度。棧1所需的高度為5 ?i =1hi +r6，棧2所需高度為8 ?i=6hi +r6+r9。

在標準單元設計中，電路首先被設計成為具有相同高度的符合線性順序的元件排列。假設此線性順序中的元件為C1，.，Cn，下一步元件被折疊成如圖1 5 - 11所示的相同寬度的行。在此圖中， 1 2個標準單元折疊成四個等寬行。折疊點是C4，C6 和C11。在相鄰標準單元行之間，使用布線通道來連接不同的行。折疊點決定了所需布線通道的高度。設li 表示當Ci 為折疊點時所需的通道高度。在圖1 5 - 11的例子中，布線通道1的高度為l4，通道2的高度為l6，通道3的高度為l11。位－片棧折疊和標準單元折疊都會引出一系列的問題，這些問題可用動態(tài)規(guī)劃方法來解決。

1. 等寬位－片元件折疊

定義r1 = rn+1 =0。由元件Ci 至Cj 構成的棧的高度要求為j ?k= ilk+ ri+ rj + 1。設一個位－片設計中所有元件有相同寬度W。首先考察在折疊矩形的高度H給定的情況下，如何縮小其寬度。設Wi

為將元件Ci 到Cn 折疊到高為H的矩形時的最小寬度。若折疊不能實現(xiàn)（如當ri +hi＞H時），取Wi =∞。注意到W1 可能是所有n 個元件的最佳折疊寬度。

當折疊Ci 到Cn 時，需要確定折疊點?，F(xiàn)假定折疊點是按棧左到棧右的順序來取定的。若第一點定為Ck+ 1，則Ci 到Ck 在第一個棧中。為了得到最小寬度，從Ck+1 到Cn 的折疊必須用最優(yōu)化方法，因此又將用到最優(yōu)原理，可用動態(tài)規(guī)劃方法來解決此問題。當?shù)谝粋€折疊點k+ 1已知時，可得到以下公式：

Wi =w+ Wk + 1 （1 5 - 9）

由于不知道第一個折疊點，因此需要嘗試所有可行的折疊點，并選擇滿足（ 1 5 - 9）式的折疊點。令h s u m(i,k)=k ?j = ihj。因k+ 1是一個可行的折疊點，因此h s u m(i, k) +ri +rk+1 一定不會超過H。

根據(jù)上述分析，可得到以下動態(tài)規(guī)劃遞歸式：

這里Wn+1 =0，且在無最優(yōu)折疊點k+ 1時Wi 為∞。利用遞歸式（1 5 - 1 0），可通過遞歸計算Wn , Wn- 1., W2 , W1 來計算Wi。Wi 的計算需要至多檢查n-i+ 1個Wk+ 1，耗時為O (n-k)。因此計算所有Wi 的時間為O (n2 )。通過保留式（1 5 - 1 0）每次所得的k 值，可回溯地計算出各個最優(yōu)的折疊點，其時間耗費為O (n)。

現(xiàn)在來考察另外一個有關等寬元件的折疊問題：折疊后矩形的寬度W已知，需要盡量減小其高度。因每個折疊矩形寬為w，因此折疊后棧的最大數(shù)量為s=W / w。令Hi, j 為Ci , ., Cn 折疊成一寬度為jw 的矩形后的最小高度， H1, s 則是所有元件折疊后的最小高度。當j= 1時，不允許任何折疊，因此：Hi,1 =h s u m(i,n) +ri , 1≤i≤n

另外，當i=n 時，僅有一個元件，也不可能折疊，因此：Hn ,j=hn+rn , 1≤j≤s

在其他情況下，都可以進行元件折疊。如果第一個折疊點為k+ 1，則第一個棧的高度為

h s u m(i,k) +ri +rk+ 1。其他元件必須以至多(j- 1 ) *w 的寬度折疊。為保證該折疊的最優(yōu)性，其他元件也需以最小高度進行折疊.

因為第一個折疊點未知，因此必須嘗試所有可能的折疊點，然后從中找出一個使式（1 5 - 11）的右側取最小值的點，該點成為第一個折疊點。

可用迭代法來求解Hi, j ( 1≤i≤n, 1≤j≤s)，求解的順序為：先計算j=2 時的H i, j，再算j= 3，.，以此類推。對應每個j 的Hi, j 的計算時間為O (n2 )，所以計算所有H i, j 的時間為O(s n2 )。通過保存由（ 1 5 - 1 2）式計算出的每個k 值，可以采用復雜性為O (n) 的回溯過程來確定各個最優(yōu)的折疊點。

2. 變寬位－片元件的折疊

首先考察折疊矩形的高度H已定，欲求最小的折疊寬度的情況。令Wi 如式（1 5 - 1 0）所示，按照與（1 5 - 1 0）式相同的推導過程，可得：

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）式，所需時間為O(n2 )。

當折疊寬度W給定時，最小高度折疊可用折半搜索方法對超過O(n2 )個可能值進行搜索來實現(xiàn)，可能的高度值為h(i,j)+ri +rj + 1。在檢測每個高度時，也可用（ 1 5 - 1 3）式來確定該折疊的寬度是否小于等于W。這種情況下總的時間消耗為O (n2 l o gn)。

3. 標準單元折疊

用wi 定義單元Ci 的寬度。每個單元的高度為h。當標準單元行的寬度W 固定不變時，通過減少折疊高度，可以相應地減少折疊面積?？疾霤i 到Cn 的最小高度折疊。設第一個折疊點是Cs+ 1。從元件Cs+1 到Cn 的折疊必須使用最小高度，否則，可使用更小的高度來折疊Cs+1 到Cn，從而得到更小的折疊高度。所以這里仍可使用最優(yōu)原理和動態(tài)規(guī)劃方法。

令Hi , s 為Ci 到Cn 折疊成寬為W的矩形時的最小高度，其中第一個折疊點為Cs+ 1。令w s u m(i, s)=s ?j = iwj?？杉俣]有寬度超過W的元件，否則不可能進行折疊。對于Hn,n 因為只有一個元件，不存在連線問題，因此Hn, n =h。對于H i, s（1≤i＜s≤n）注意到如果w s u m(i, s )＞W，不可能實現(xiàn)折疊。若w s u m(i,s)≤W，元件Ci 和C j + 1 在相同的標準單元行中，該行下方布線通道的高度為ls+ 1（定義ln+1 = 0）。因而：Hi, s = Hi+1, k （1 5 - 1 4）

當i=s＜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｝。可以使用回溯過程來確定最小高度折疊中的折疊點。

講解：一個尋找關鍵字－－searchkey
另一個是插入一個結點：insertTree
另外這是一個完全的先序遍歷二叉樹的語法。先根結點，再左結點，如無再右結點，如些加歸至搜索完畢。??

10, 增加eclipse內存：
更改ECLIPSE文件夾下的ECLIPSE.INI文件內容如下：
-vmargs
-Xms128m
-Xmx512m
-XX:PermSize=128m
-XX:MaxPermSize=256m

或者：

在eclipse目錄下建個批處理文件eclipse.bat,用文本編輯器打開,寫入如下內容:
eclipse.exe -vmargs -Xms128m -Xmx512m -XX:PermSize=128m -XX:PermSize=256m

然后保存.以后運行eclipse的時候就執(zhí)行這個批處理就行了.
解釋下參數(shù)的意思:
-vmargs                                   說明后面的參數(shù)都是java虛擬機(vm)的參數(shù)
-Xms128m                               虛擬機占用系統(tǒng)的最小內存
-Xmx512m                               虛擬機占用系統(tǒng)的最大內存
-XX:PermSize=64m              最小堆大小.一般報內存不足時,都是說這個太小,堆空間剩余小于5%                             就會警告,建議把這個稍微設大一點,不過要視自己機器內存大小來設置

-XX:PermSize=128m             最大堆大小.這個也適當變大些

在快捷方式中設置也可:
eclipse.exe -vmargs -Xverify:none -XX:+UseParallelGC -XX:PermSize=20M -Xms64M -Xmx512M

9,代碼風格設置
可以通過Window->Perferences->Java->Code Style->Code Formatter來設定代碼的編寫格式，然后只要用快捷鍵Ctrl+Shift+F就可以將不標準的代碼自動轉化成所設定的標準格式。

8,顯示行號，顯示限制列的線（默認80列）

window -> Preferences -> General -> Editors -> Text Editors: Show line numbers; Show print margin

7.打包成jar文件時，需要根據(jù)自定義的文件生成MANIFEST.MF，其中每行的冒號后面都有一個空格，否則出錯。例：Manifest-Version: 1.0(1.0前有空格，其他行也是如此)

6.由數(shù)據(jù)庫中的表自動建立.java和.hbm.xml文件
a.建立項目：打開帶HibernateTools插件的eclipse，建立一個名為“test”的java project,內部新建一個名字為src的source folder。
b.建立hibernate配置文件：新建“hibernate configuration file”，輸出路徑選擇“test項目的src目錄”，然后的對話框填寫配置文件（包括database dialect,driver class,connection url,username,password,creat a console configuration），下一個對話框先填寫name（即console configuration name），再點“add external jars”，選擇數(shù)據(jù)庫驅動的jar文件，看到src中有“hibernate.cfg.xml”就是配置文件建立成功。
c.建立目標文件：點工具欄hibernate圖標，選擇“hibernate code generation...”,在彈出的對話框中點擊左側“新建”，把名字改為“test”，console configuration選剛才建立的console configuration name，package填想生成的包結構，點reveng.xml的“setup”，接下來對話框選擇test的src目錄，然后導入需要的數(shù)據(jù)庫表（有關聯(lián)的就要導入，即外鍵的表也要導入），然后點“finish”；選擇main右邊的exporters，選中generate domain code,generate mappings三項，run，刷新項目，看到包中生成的.java和.hbm.xml文件，成功，把它們拷入myeclipse的相應項目里。
d.刪除Console Configuration：打開Hibernate Console的透視圖（perspective），在左側Hibernate Configuration的視圖（view）中右鍵單擊，就可以刪除。
刪除Hivernate Code Generation：點擊工具欄Hibernate圖標，左側即可刪除。

5.*.service.spring包中的*ServiceImpl.java文件中有dao對象屬性，必須包括這個對象的get/set方法，否則出錯。

4.從一個.jsp文件轉到另一個包含有form表單.jsp文件時，出錯信息為form表單的action找不到mapping，在兩個頁面之間加一個action即可找到。

3.eclipse與tomcat代碼不同步的問題
搜索tomcat中有此項目名的所有文件，全部刪除。在實驗應該會成功。

2.字符集框手動輸入
我把“eclipse 的window-->prefrences -->general -->content type”設為了UTF8，是為了不讓每個項目再選一遍UTF8，結果單個項目選擇時就沒有GBK選項了。解決辦法就是在單個項目讓你選字符集的地方手動輸入GBK，就ok了?。?！

1.debug工具條灰色
debug模式下，eclipse用debug透視圖打開斷點頁面，但debug工具條卻顯示灰色，應該轉到其他透視圖在轉會來就可以了。比如debug -> java -> debug

 

?　　可以【方法一】簡單地把plugin放到eclipse SDK本身的features和plugins目錄下來進行plugin的安裝，但是這種方法并不利于plugin的管理：
-1 subversion開發(fā)
subclipse: http://subclipse.tigris.org/update_1.2.x
按照提示安裝完畢后，我們就可以打開Subversion的資源庫了。選擇Eclipse菜單Window->Show View->Other…，選擇SVN->SVN Repository，然后添加一個新的資源庫，例如http://livebookstore.googlecode.com/svn/trunk

0  python開發(fā)
pydev：http://www.fabioz.com/pydev/updates

1  Eclipse下載
EMF,GEF - Graphical Editor Framework,UML2,VE - Visual Editor都在這里下載
http://www.eclipse.org/downloads/index.php

2  lomboz J2EE插件,開發(fā)JSP,EJB
http://forge.objectweb.org/projects/lomboz

3  MyEclipse J2EE開發(fā)插件，支持SERVLET/JSP/EJB/數(shù)據(jù)庫操縱等
http://www.myeclipseide.com/

4  Properties Editor  編輯java的屬性文件，并可以自動存盤為Unicode格式
http://propedit.sourceforge.jp/index_en.html

5  Colorer Take  為上百種類型的文件按語法著色
http://colorer.sourceforge.net/

6  XMLBuddy 編輯xml文件
http://www.xmlbuddy.com/

7  Code Folding  加入多種代碼折疊功能（比eclipse自帶的更多）
http://www.coffee-bytes.com/servlet/PlatformSupport

8  Easy Explorer  從eclipse中訪問選定文件、目錄所在的文件夾
http://easystruts.sourceforge.net/

9  Fat Jar 打包插件，可以方便的完成各種打包任務，可以包含外部的包等
http://fjep.sourceforge.net/

10  RegEx Test 測試正則表達式
http://brosinski.com/stephan/archives/000028.php

11  JasperAssistant 報表插件(要錢的哦～)
http://www.jasperassistant.com/

12  Jigloo GUI Builder JAVA的GUI編輯插件
http://cloudgarden.com/jigloo/

13  Profiler 性能跟蹤、測量工具，能跟蹤、測量B/S程序
http://sourceforge.net/projects/eclipsecolorer/

14  AdvanQas 提供對if/else等條件語句的提示和快捷幫助(自動更改結構等)
http://eclipsecolorer.sourceforge.net/advanqas/index.html

15  Log4E Log4j插件，提供各種和Log4j相關的任務，如為方法、類添加一個logger等
http://log4e.jayefem.de/index.php/Main_Page

16  VSSPlugin VSS插件
http://sourceforge.net/projects/vssplugin

17  Implementors 提供跳轉到一個方法的實現(xiàn)類，而不是接口的功能（實用!）
http://eclipse-tools.sourceforge.net/implementors/

18  Call Hierarchy 顯示一個方法的調用層次（被哪些方法調，調了哪些方法）
http://eclipse-tools.sourceforge.net/call-hierarchy/index.html

19  EclipseTidy 檢查和格式化HTML/XML文件
http://eclipsetidy.sourceforge.net/

20  Checkclipse 檢查代碼的風格、寫法是否符合規(guī)范
http://www.mvmsoft.de/content/plugins/checkclipse/checkclipse.htm

21  Hibernate Synchronizer Hibernate插件，自動映射等
http://www.binamics.com/hibernatesync/

22  VeloEclipse  Velocity插件
http://propsorter.sourceforge.net/ 
 
23  EditorList 方便的列出所有打開的Editor
http://editorlist.sourceforge.net/ 
 
24  MemoryManager 內存占用率的監(jiān)視
http://cloudgarden.com/memorymanager/ 
 
25  swt-designer java的GUI插件
http://www.swt-designer.com/
 
26  TomcatPlugin 支持Tomcat插件
http://www.sysdeo.com/eclipse/tomcatPlugin.html
 
27  XML Viewer
http://tabaquismo.freehosting.net/ignacio/eclipse/xmlview/index.html
 
28  quantum 數(shù)據(jù)庫插件
http://quantum.sourceforge.net/
 
29  Dbedit 數(shù)據(jù)庫插件
http://sourceforge.net/projects/dbedit
 
30  clay.core 可視化的數(shù)據(jù)庫插件
http://www.azzurri.jp/en/software/index.jsp
http://www.azzurri.jp/eclipse/plugins
 
31  hiberclipse hibernate插件
http://hiberclipse.sourceforge.net/
http://www.binamics.com/hibernatesync
 
32  struts-console Struts插件
http://www.jamesholmes.com/struts/console/
 
33  easystruts Struts插件
http://easystruts.sourceforge.net/ 
 
34  veloedit Velocity插件
http://veloedit.sourceforge.net/
 
35  jalopy 代碼整理插件
http://jalopy.sourceforge.net/
 
36  JDepend 包關系分析
http://andrei.gmxhome.de/jdepend4eclipse/links.html
 
37  Spring IDE Spring插件
http://springide-eclip.sourceforge.net/updatesite/
 
38  doclipse 可以產生xdoclet 的代碼提示
http://beust.com/doclipse/

39  SQLExplorer,在Eclipse 中連接各種數(shù)據(jù)庫進行操作使用
http://dev2dev.bea.com.cn/bbs/thread.jspa?forumID=124&threadID=31124

===========================================================\

以下為7月13日轉貼更新

JSEclipse

eclipseME
  http://eclipseme.org/updates/

Eclipse加速插件KeepResident
http://suif.stanford.edu/pub/keepresident/
 
MyEclipse  J2EE開發(fā)插件，支持SERVLET/JSP/EJB/數(shù)據(jù)庫操縱等
www.myeclipseide.com
 
Properties Editor  編輯java的屬性文件，并可以自動存盤為Unicode格式
http://propedit.sourceforge.jp/index_en.html
http://propedit.sourceforge.jp/eclipse/updates/
 
Colorer Take  為上百種類型的文件按語法著色
http://colorer.sourceforge.net/
 
XMLBuddy 編輯xml文件
www.xmlbuddy.com
 
Code Folding  加入多種代碼折疊功能（比eclipse自帶的更多）
http://www.coffee-bytes.com/servlet/PlatformSupport
 
Easy Explorer  從eclipse中訪問選定文件、目錄所在的文件夾
http://easystruts.sourceforge.net/
 
Fat Jar 打包插件，可以方便的完成各種打包任務，可以包含外部的包等
http://fjep.sourceforge.net/
 
RegEx Test 測試正則表達式
http://brosinski.com/stephan/archives/000028.php
 
JasperAssistant 報表插件（強，要錢的）
http://www.jasperassistant.com/
 
Jigloo GUI Builder ＪＡＶＡ的ＧＵＩ編輯插件
http://cloudgarden.com/jigloo/
 
Profiler 性能跟蹤、測量工具，能跟蹤、測量ＢＳ程序
http://sourceforge.net/projects/eclipsecolorer/
 
AdvanQas 提供對if/else等條件語句的提示和快捷幫助（自動更改結構等）
http://eclipsecolorer.sourceforge.net/advanqas/index.html
 
Log4E     Log4j插件，提供各種和Log4j相關的任務，如為方法、類添加一個logger等
http://log4e.jayefem.de/index.php/Main_Page
 
VSSPlugin VSS插件
http://sourceforge.net/projects/vssplugin
 
Implementors   提供跳轉到一個方法的實現(xiàn)類，而不是接中的功能（實用!）
http://eclipse-tools.sourceforge.net/implementors/
 
Call Hierarchy 顯示一個方法的調用層次（被哪些方法調，調了哪些方法）
http://eclipse-tools.sourceforge.net/call-hierarchy/index.html
 
EclipseTidy 檢查和格式化HTML/XML文件
http://eclipsetidy.sourceforge.net/
 
Checkclipse 檢查代碼的風格、寫法是否符合規(guī)范
http://www.mvmsoft.de/content/plugins/checkclipse/checkclipse.htm
 
Hibernate Synchronizer Hibernate插件，自動映射等
http://www.binamics.com/hibernatesync/
 
spring updatesite 插件
http://springide.org/updatesite/

VeloEclipse  Velocity插件
http://propsorter.sourceforge.net/
 
EditorList   方便的列出所有打開的Editor
http://editorlist.sourceforge.net/
 
MemoryManager 內存占用率的監(jiān)視
http://cloudgarden.com/memorymanager/

Eclipse的游戲插件
http://eclipse-games.sourceforge.net/

JBoss-IDE
http://jboss.sourceforge.net/jbosside/updates/

自動反編譯class，安裝后要設定class文件缺省關聯(lián)到jode
http://www.technoetic.com/eclipse/update

jigloo swing/sw設計工具，里面自帶的form/anchor布局很好用！
http://cloudgarden.soft-gems.net/update-site/

jinto的資源文件編輯工具，同時編輯多種語言，而且自動轉換成iso8859-1編碼。很好用！
http://www.guh-software.de/eclipse/

?一、exe4j

說明：exe4j可以將Jar文件制作成exe文件，但需jre支持，也可將Jar文件放在外面。

軟件性質：共享軟件

下載地址：http://www.ej-technologies.com/products/exe4j/overview.html

二、JBuilder

說明：新版本的JBuilder可以直接把工程制作成各系統(tǒng)的可執(zhí)行文件，包括Windows系統(tǒng)。

軟件性質：商業(yè)軟件

下載地址：略。我是從eMule下載的。

三、NativeJ

說明：與exe4j功能類似。

軟件性質：共享軟件

下載地址：http://www.dobysoft.com/products/nativej/download.html

四、Excelsior JET

說明：可以直接將Java類文件制作成exe文件，除AWT和Swing及第三方圖形接口外可不需jre支持（Java5.0不行）。

軟件性質：共享軟件

下載地址：http://excelsior-usa.com/home.html

五、jshrink

說明：可將Jar文件打包進exe文件。同時具有混淆功能（這才是它的主要功能）。

軟件性質：共享軟件

下載地址：http://www.e-t.com/jshrink.html

六、InstallAnywhere

說明：打包工具，對Java打包最好用?？纱虬筛鞑僮飨到y(tǒng)運行包。包括Windows系統(tǒng)。

軟件性質：商業(yè)軟件。

下載地址：http://www.zerog.com/

七、InstallShieldX

說明：與InstallAnywhere類似，但比InstallAnywhere功能強大。相對的，比較復雜，不易上手，我現(xiàn)在還沒學會。

一、代碼轉換工具：
native2ascii -encoding gb2312 application_temp.properties application_zh_CN.properties
注釋：-encoding gb2312 表示讀application_temp.properties 的編碼方式，application_temp.properties 存的是中文資源文件，application_zh_CN.properties
存的是轉成ascii碼后的資源文件。

二、反編譯工具jad.exe：
?以下假設jad.exe在c:\java目錄下
1、基本用法
Usage:??? jad [option(s)] <filename(s)>
直接輸入類文件名，且支持通配符，如下所示。
c:\java\>jad example1.class
c:\java\>jad *.class
結果是將example1.class反編譯為example1.jad。將example1.jad改為example1.java即得源文件。
2、Option -o
不提示，覆蓋源文件
3、Option -s
c:\java\>jad -sjava example1.class
反編譯結果以.java為擴展名。
4、Option -p
將反編譯結果輸出到屏幕
c:\java\>jad -p example1.class
將反編譯結果重定向到文件
c:\java\>jad -p example1.class>example1.java
5、Option -d
指定反編譯的輸出文件目錄
c:\java\>jad -o -dtest -sjava *.class

三、文檔生成工具javadoc.exe
? 大家都知道，J2SE5中的Javadoc.exe的命令行可選參數(shù)多達五十余個，其復雜性可想而知，是不是看著頭都大了呢？但通常情況下，我們不想那么麻煩！
假設源代碼在 C:\src 目錄下，其中 com.liigo 是主包，其下可能有數(shù)十個子包，數(shù)百（千）個Java文件。目錄結構大約是這樣的：
- C:\
????? | src\
????????? | com\
????????????? | liigo\
????????????????? | ***
怎么才能以最簡捷的方式生成所有的API文檔呢？
c:\>
c:\>cd src
c:\src>javadoc -d doc -subpackages com.liigo
這樣就搞定了，最終生成的API文檔位于 c:\src\doc 目錄（該目錄是由javadoc.exe自動生成的）。
上面的用法利用了“當前目錄”和“相對路徑”，當然也可以用絕對路徑：
...>javadoc -d c:\doc -sourcepath c:\src -subpackages com.liigo
最終生成的API文檔位于 c:\doc 目錄（該目錄同樣是由javadoc.exe自動生成的）。

總結一下：
我們只用到了javadoc的三個參數(shù)： -d，-subpackages，-sourcepath，其中：
?參數(shù)? 說明?
?-d? 指定API文檔的輸出目錄，默認是當前目錄。建議總是指定該參數(shù)。
?-sourcepath 指定源代碼路徑，默認是當前目錄。 此參數(shù)通常是必須的。
?-subpackages? 以遞歸的方式處理各子包。關鍵參數(shù)！如果不使用本參數(shù)，每次只能處理一個子包（或需手工列出所有子包）。

四、運行jvm時改變內存或堆的大小
-Xms<size>???????????????? set?? initial?? Java?? heap?? size??
-Xmx<size>???????????????? set?? maximum?? Java?? heap?? size??
-Xss<size>???????????????? set?? java?? thread?? stack?? size??
???
比如:java?? -Xmx512M? HelloWorld.class,讓jvm使用512Mheap內存.

???作者：江南白衣，原文出處： http://blog.csdn.net/calvinxiu/archive/2007/01/27/1495778.aspx，轉載請保留出處。

??? Unix系統(tǒng)永遠只會越來越多，開發(fā)人員就沒必要特意學習它們的安裝、配置和管理了，就全部交給集成人員吧。
??? 但開發(fā)人員行走于Unix之間，依然有四樣東西要熟練。

??? 一、VI

??? 雖然Unix上的文本編輯器已經越來越好用，但不在Console前面，網速也不夠連XWindows的時候，還是要依賴VI。
??? 回想VI的時代背景，發(fā)現(xiàn)VI對開發(fā)人員已經周到得離譜了，熱鍵多到你雙手不離鍵盤就能完成大半編輯工作。
??? 建議自己制作一張自己認為有用，但又經常忘記的命令的sheet，拿出考試的力氣把它背熟。

??? 二、文本處理

?? ??? 開發(fā)人員在Unix下干得最多的除了Make和除Bug外，大概就是處理日志文件、業(yè)務文件進行查錯和統(tǒng)計了。
???? 只會more和grep是不夠的，開發(fā)老手會把awk,sed,grep,sort,uniq,wc,head,tail這些文本處理命令，通過管道玩具式的拆卸拼裝，最后完成一件原本以為非編寫大段代碼不可的工作。周到的參數(shù)設定，讓人再一次感嘆那個簡單的年代，這樣復雜到極致的設計.......怪不得《Unix 編程藝術》的作者有那么驕傲的自覺。

???? 比如車東的每月訪問TOP10 統(tǒng)計腳本：

• awk -F '\t' 將2004_2.txt訪問紀錄文件，用TAB分割，打印第4列
• grep chedong.com/tech 只列出chedong.com/tech筆記目錄下的文檔
• uniq -c 匯總計數(shù)
• sort -rn 按數(shù)值排序
• head -10 TOP 10
  

??? 三、Bash Shell 編程

??? 編程是開發(fā)人員的天賦本能，不論什么語言，看看參考手冊應該就能上手。

??? 見Bash新手指南中文版，一份寫給新手看的包含很多老手知識的指南。

??? 四、Make與AutoMake

??? 用過Java的Ant后，想起Make就覺得很煩，很厭倦?？倸w還是會的，見GNU Make 3.8.0 中文手冊????

???? 不過即使make已經精通到變態(tài)，每個人寫出來的MakeFile還是千奇百怪，再看看開源項目們個個都是automake+autoconf了，我們自己也長進一點吧。手工編寫MakeFile.am，讓auotomake變成MakeFile.in，再讓用戶./configure 生成最終的MakeFile。
????
??? 生成的MakeFile既能跨越平臺，又是標準的寫法，最重要的是，編寫MakeFile.am的工作量比MakeFile少多了，只要簡單的定義目標文件，先要處理的子目錄，需要的源文件，頭文件與庫文件就可以了。如果看完下面兩篇還是不懂，直接看ACE里的Makefile.am就懂了。

????入門文章：使用AutoMake輕松生成Makefile?
??? 進階文章：IBM DW:例解 autoconf 和 automake 生成 Makefile 文件
??? 完整的免費電子書：?GNU Autoconf, Automake and Libtool

?? ?另外，ACE里還貢獻了一個更厲害的MPC(Makefile, Project, and Workspace Creator )，??自動的生成了MakeFile.am或者VC的項目文件。

??? 附錄A：我的VI易忘命令手冊

??? 上下左右：
??? ctrl+u/d 上下半屏，ctrl+f/b,上下一屏
??? H/G屏幕頭/文章末 ，0/$ 行首行末
???
??? 增刪改：
??? yy/dd 復制/刪除 一行，p/P：將yy/dd的內容paste出來
??? I/A 在行首/末添加， o/O 開新行，d0/d$ 刪除到行首，行末
??? u:undo

??? 查：
??? ? 向前查找， n/N 重復上一次查找

附錄B: 文本處理命令小結

?? awk：處理結構化的文本(每行以固定符號分成若干列)，提取打印某些字段，如：
??? ls -l|awk '{print $1}'? --將ls-l結果的第一列打印出來
??? awk -F":" '{print $1"? "$6}' /etc/passwd ，將以:分割的/etc/passwd文件的第1，6列打印出來，中間以空格分開
??? 詳見IBM DW中國的AWK實例(共3篇) 或 Bash新手指南中文版第6章。

??? grep：過濾，大家用得最多的命令，支持正則表達式。參數(shù)有：
??? -i忽略大小寫，-n顯示line number，-c 統(tǒng)計在每個文件的出現(xiàn)次數(shù)，-l只顯示符合的文件的名字。

??? sed：流編輯器，主要用于替換，如：
??? sed -e '1,10s/foo/bar/g' myfile2.txt 將1到10行的文本中的foo 替換成bar,s代表替換,g代表全局替換
??? 支持正則的替換字符串，可以只替換某個范圍內的內容。
??? 用法不算簡單,詳見IBM DW中國的Sed實例(共3篇)或 Bash新手指南中文版第5章。
????
??? sort：排序，參數(shù)有：
??? -r逆序, -n 數(shù)字比較 , -M 日歷比較 Feb,Dec, -f 忽略大小寫
??? 同樣支持結構化文件，如
??? sort -t : -k 1,1 /etc/passwd，以: 分割,只按第1列排序
??? sort -t : -k 1,1 -k2.2,3.4 /etc/passwd ，以:分割,先按第1列排序,再按第2列的第二個字符到第3列的第4個字符排序。

??? uniq：去除重復行。
??? 除了正常用法外，還有-c統(tǒng)計重復次數(shù)，和-u （唯一）和 -d （重復）兩個參數(shù),只顯示唯一的和重復的行。

??? wc： 統(tǒng)計。
??? -l 行,-m 字符,-w 單詞