現在考慮k = 1時的貪婪啟發法。最初的子集為{ 1 } , { 2 } , { 3 } , { 4 }。子集{ 1 } , { 2 }產生與k= 0時相同的結果，考慮子集{ 3 }，置x3 為1。此時還剩5個單位的容量，按價值密度非遞增順序來考慮如何利用這5個單位的容量。首先考慮物品1，它適合，因此取x1 為1，這時僅剩下3個單位容量了，且剩余物品沒有能夠加入背包中的物品。通過子集{ 3 }開始求解得結果為x = [ 1 , 0 , 1 , 0 ]，獲得的價值為1 8。若從子集{ 4 }開始，產生的解為x = [ 1 , 0 , 0 , 1 ]，獲得的價值為1 9。考慮子集大小為0和1時獲得的最優解為[ 1 , 0 , 0 , 1 ]。這個解是通過k= 1的貪婪啟發式算法得到的。

若k= 2，除了考慮k< 2的子集，還必需考慮子集{ 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 }和{ 3 , 4 }。首先從最后一個子集開始，它是不可行的，故將其拋棄，剩下的子集經求解分別得到如下結果：[ 1 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 0 ] , [ 1 , 0 , 0 , 1 ] , [ 0 , 1 , 1 , 0 ]和[ 0 , 1 , 0 , 1 ]，這些結果中最后一個價值為2 3，它的值比k= 0和k= 1時獲得的解要高，這個答案即為啟發式方法產生的結果。

這種修改后的貪婪啟發方法稱為k階優化方法（k - o p t i m a l）。也就是，若從答案中取出k 件物品，并放入另外k 件，獲得的結果不會比原來的好，而且用這種方式獲得的值在最優值的( 1 0 0 / (k + 1 ) ) %以內。當k= 1時，保證最終結果在最佳值的5 0 %以內；當k= 2時，則在3 3 . 3 3 %以內等等，這種啟發式方法的執行時間隨k 的增大而增加，需要測試的子集數目為O (nk )，每一個子集所需時間為O (n)，因此當k >0時總的時間開銷為O (nk+1 )。實際觀察到的性能要好得多。

 

1.3.3 拓撲排序

一個復雜的工程通常可以分解成一組小任務的集合，完成這些小任務意味著整個工程的完成。例如，汽車裝配工程可分解為以下任務：將底盤放上裝配線，裝軸，將座位裝在底盤上，上漆，裝剎車，裝門等等。任務之間具有先后關系，例如在裝軸之前必須先將底板放上裝配線。任務的先后順序可用有向圖表示——稱為頂點活動（ Activity On Vertex, AOV）網絡。有向圖的頂點代表任務，有向邊(i, j) 表示先后關系：任務j 開始前任務i 必須完成。圖1  - 4顯示了六個任務的工程，邊（ 1 , 4）表示任務1在任務4開始前完成，同樣邊（ 4 , 6）表示任務4在任務6開始前完成，邊（1 , 4）與（4 , 6）合起來可知任務1在任務6開始前完成，即前后關系是傳遞的。由此可知，邊（1 , 4）是多余的，因為邊（1 , 3）和（3 , 4）已暗示了這種關系。

在很多條件下，任務的執行是連續進行的，例如汽車裝配問題或平時購買的標有“需要裝配”的消費品（自行車、小孩的秋千裝置，割草機等等）。我們可根據所建議的順序來裝配。在由任務建立的有向圖中，邊（ i, j）表示在裝配序列中任務i 在任務j 的前面，具有這種性質的序列稱為拓撲序列（topological orders或topological sequences)。根據任務的有向圖建立拓撲序列的過程稱為拓撲排序（topological sorting）。圖1 - 4的任務有向圖有多種拓撲序列，其中的三種為1 2 3 4 5 6，1 3 2 4 5 6和2 1 5 3 4 6，序列1 4 2 3 5 6就不是拓撲序列，因為在這個序列中任務4在3的前面，而任務有向圖中的邊為（ 3 , 4），這種序列與邊（ 3 , 4）及其他邊所指示的序列相矛盾。可用貪婪算法來建立拓撲序列。算法按從左到右的步驟構造拓撲序列，每一步在排好的序列中加入一個頂點。利用如下貪婪準則來選擇頂點：從剩下的頂點中，選擇頂點w，使得w 不存在這樣的入邊（ v,w），其中頂點v 不在已排好的序列結構中出現。注意到如果加入的頂點w違背了這個準則（即有向圖中存在邊（ v,w）且v 不在已構造的序列中），則無法完成拓撲排序，因為頂點v 必須跟隨在頂點w 之后。貪婪算法的偽代碼如圖1 3 - 5所示。while 循環的每次迭代代表貪婪算法的一個步驟。

現在用貪婪算法來求解圖1 - 4的有向圖。首先從一個空序列V開始，第一步選擇V的第一個頂點。此時，在有向圖中有兩個候選頂點1和2，若選擇頂點2，則序列V = 2，第一步完成。第二步選擇V的第二個頂點，根據貪婪準則可知候選頂點為1和5，若選擇5，則V = 2 5。下一步，頂點1是唯一的候選，因此V = 2 5 1。第四步，頂點3是唯一的候選，因此把頂點3加入V

得到V = 2 5 1 3。在最后兩步分別加入頂點4和6 ，得V = 2 5 1 3 4 6。

1. 貪婪算法的正確性

為保證貪婪算法算的正確性，需要證明： 1) 當算法失敗時，有向圖沒有拓撲序列； 2) 若

算法沒有失敗，V即是拓撲序列。2) 即是用貪婪準則來選取下一個頂點的直接結果， 1) 的證明見定理1 3 - 2，它證明了若算法失敗，則有向圖中有環路。若有向圖中包含環qj qj + 1.qk qj , 則它沒有拓撲序列，因為該序列暗示了qj 一定要在qj 開始前完成。

定理1-2 如果圖1 3 - 5算法失敗，則有向圖含有環路。

證明注意到當失敗時| V |<n, 且沒有候選頂點能加入V中，因此至少有一個頂點q1 不在V中，有向圖中必包含邊（ q2 , q1）且q2 不在V中，否則， q1 是可加入V的候選頂點。同樣，必有邊（q3 , q2）使得q3 不在V中，若q3 = q1 則q1 q2 q3 是有向圖中的一個環路；若q3 ≠q1，則必存在q4 使（q4 , q3）是有向圖的邊且q4 不在V中，否則，q3 便是V的一個候選頂點。若q4 為q1 , q2 , q3 中的任何一個，則又可知有向圖含有環，因為有向圖具有有限個頂點數n，繼續利用上述方法，最后總能找到一個環路。

2. 數據結構的選擇

為將圖1 - 5用C + +代碼來實現，必須考慮序列V的描述方法，以及如何找出可加入V的候選頂點。一種高效的實現方法是將序列V用一維數組v 來描述的，用一個棧來保存可加入V的候選頂點。另有一個一維數組I n D e g r e e，I n D e g r e e[ j ]表示與頂點j相連的節點i 的數目，其中頂點i不是V中的成員，它們之間的有向圖的邊表示為（ i, j）。當I n D e g r e e[ j ]變為0時表示j 成為一個候選節點。序列V初始時為空。I n D e g r e e[ j ]為頂點j 的入度。每次向V中加入一個頂點時，所有與新加入頂點鄰接的頂點j，其I n D e g r e e[ j ]減1。對于有向圖1 - 4，開始時I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 3 , 1 , 3 ]。由于頂點1和2的I n D e g r e e值為0，因此它們是可加入V的候選頂點，由此，頂點1和2首先入棧。每一步，從棧中取出一個頂點將其加入V，同時減去與其鄰接的頂點的I n D e g r e e值。若在第一步時從棧中取出頂點2并將其加入V，便得到了v [ 0 ] = 2，和I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 2 , 0 , 3 ]。由于I n D e g r e e [ 5 ]剛剛變為0，因此將頂點5入棧。

程序1 3 - 2給出了相應的C + +代碼，這個代碼被定義為N e t w o r k的一個成員函數。而且，它對于有無加權的有向圖均適用。但若用于無向圖（不論其有無加權）將會得到錯誤的結果，因為拓撲排序是針對有向圖來定義的。為解決這個問題，利用同樣的模板來定義成員函數AdjacencyGraph, AdjacencyWGraph，L i n k e d G r a p h和L i n k e d W G r a p h。這些函數可重載N e t w o r k中的函數并可輸出錯誤信息。如果找到拓撲序列，則Topological 函數返回t r u e；若輸入的有向圖無拓撲序列則返回f a l s e。當找到拓撲序列時，將其返回到v [ 0 :n- 1 ]中。

3. Network:Topological 的復雜性

第一和第三個f o r循環的時間開銷為(n )。若使用（耗費）鄰接矩陣,則第二個for 循環所用的時間為(n2 )；若使用鄰接鏈表,則所用時間為(n+e)。在兩個嵌套的while 循環中，外層循環需執行n次，每次將頂點w 加入到v 中，并初始化內層while 循環。使用鄰接矩陣時，內層w h i l e循環對于每個頂點w 需花費(n)的時間；若利用鄰接鏈表，則這個循環需花費dwout 的時間，因此，內層while 循環的時間開銷為(n2 )或(n+e)。所以，若利用鄰接矩陣，程序1 3 - 2的時間復雜性為(n2 )，若利用鄰接鏈表則為(n+e)。

程序13-2 拓撲排序

bool Network::Topological(int v[])

{// 計算有向圖中頂點的拓撲次序

// 如果找到了一個拓撲次序，則返回t r u e，此時，在v [ 0 : n - 1 ]中記錄拓撲次序

// 如果不存在拓撲次序，則返回f a l s e

int n = Ve r t i c e s ( ) ;

// 計算入度

int *InDegree = new int [n+1];

InitializePos(); // 圖遍歷器數組

for (int i = 1; i <= n; i++) // 初始化

InDegree[i] = 0;

for (i = 1; i <= n; i++) {// 從i 出發的邊

int u = Begin(i);

while (u) {

I n D e g r e e [ u ] + + ;

u = NextVe r t e x ( i ) ; }

}

// 把入度為０的頂點壓入堆棧

LinkedStack<int> S;

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

if (!InDegree[i]) S.Add(i);

// 產生拓撲次序

i = 0; // 數組v 的游標

while (!S.IsEmpty()) {// 從堆棧中選擇

int w; // 下一個頂點

S . D e l e t e ( w ) ;

v[i++] = w;

int u = Begin(w);

while (u) {// 修改入度

I n D e g r e e [ u ] - - ;

if (!InDegree[u]) S.Add(u);

u = NextVe r t e x ( w ) ; }

}

D e a c t i v a t e P o s ( ) ;

delete [] InDegree;

return (i == n);

}

 

1.3.4 二分覆蓋

二分圖是一個無向圖，它的n 個頂點可二分為集合A和集合B，且同一集合中的任意兩個頂點在圖中無邊相連（即任何一條邊都是一個頂點在集合A中，另一個在集合B中）。當且僅當B中的每個頂點至少與A中一個頂點相連時，A的一個子集A' 覆蓋集合B（或簡單地說，A' 是一個覆蓋）。覆蓋A' 的大小即為A' 中的頂點數目。當且僅當A' 是覆蓋B的子集中最小的時，A' 為最小覆蓋。

例1-10 考察如圖1 - 6所示的具有1 7個頂點的二分圖，A={1, 2, 3, 16, 17}和B={4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15}，子集A' = { 1 , 1 6 , 1 7 }是B的最小覆蓋。在二分圖中尋找最小覆蓋的問題為二分覆蓋（ b i p a r t i t e - c o v e r）問題。在例1 2 - 3中說明了最小覆蓋是很有用的，因為它能解決“在會議中使用最少的翻譯人員進行翻譯”這一類的問題。

二分覆蓋問題類似于集合覆蓋（ s e t - c o v e r）問題。在集合覆蓋問題中給出了k 個集合S= {S1 , S2 ,., Sk }，每個集合Si 中的元素均是全集U中的成員。當且僅當èi S'Si =U時，S的子集S' 覆蓋U，S '中的集合數目即為覆蓋的大小。當且僅當沒有能覆蓋U的更小的集合時，稱S' 為最小覆蓋。可以將集合覆蓋問題轉化為二分覆蓋問題（反之亦然），即用A的頂點來表示S1 , ., Sk ，B中的頂點代表U中的元素。當且僅當S的相應集合中包含U中的對應元素時，在A與B的頂點之間存在一條邊。

例1 - 11 令S= {S1，. . .，S5 }, U= { 4，5，. . .，15}, S1 = { 4，6，7，8，9，1 3 }，S2 = { 4，5，6，8 }，S3 = { 8，1 0，1 2，1 4，1 5 }，S4 = { 5，6，8，1 2，1 4，1 5 }，S5 = { 4，9，1 0，11 }。S ' = {S1，S4，S5 }是一個大小為3的覆蓋，沒有更小的覆蓋， S' 即為最小覆蓋。這個集合覆蓋問題可映射為圖1-6的二分圖，即用頂點1，2，3，1 6和1 7分別表示集合S1，S2，S3，S4 和S5，頂點j 表示集合中的元素j，4≤j≤1 5。

集合覆蓋問題為N P-復雜問題。由于集合覆蓋與二分覆蓋是同一類問題，二分覆蓋問題也是N P-復雜問題。因此可能無法找到一個快速的算法來解決它，但是可以利用貪婪算法尋找一種快速啟發式方法。一種可能是分步建立覆蓋A' ，每一步選擇A中的一個頂點加入覆蓋。頂點的選擇利用貪婪準則：從A中選取能覆蓋B中還未被覆蓋的元素數目最多的頂點。

例1-12 考察圖1 - 6所示的二分圖，初始化A' = 且B中沒有頂點被覆蓋，頂點1和1 6均能覆蓋B中的六個頂點，頂點3覆蓋五個，頂點2和1 7分別覆蓋四個。因此，在第一步往A' 中加入頂點1或1 6，若加入頂點1 6，則它覆蓋的頂點為{ 5 , 6 , 8 , 1 2 , 1 4 , 1 5 }，未覆蓋的頂點為{ 4 , 7 , 9 , 1 0 , 11 , 1 3 }。頂點1能覆蓋其中四個頂點（ { 4 , 7 , 9 , 1 3 }），頂點2 覆蓋一個( { 4 } )，頂點3覆蓋一個（{ 1 0 }），頂點1 6覆蓋零個，頂點1 7覆蓋四個{ 4 , 9 , 1 0 , 11 }。下一步可選擇1或1 7加入A' 。若選擇頂點1，則頂點{ 1 0 , 11} 仍然未被覆蓋，此時頂點1，2，1 6不覆蓋其中任意一個，頂點3覆蓋一個，頂點1 7覆蓋兩個，因此選擇頂點1 7，至此所有頂點已被覆蓋，得A' = { 1 6 , 1 , 1 7 }。

圖1 - 7給出了貪婪覆蓋啟發式方法的偽代碼，可以證明： 1) 當且僅當初始的二分圖沒有覆蓋時，算法找不到覆蓋；2) 啟發式方法可能找不到二分圖的最小覆蓋。

1. 數據結構的選取及復雜性分析

為實現圖13 - 7的算法，需要選擇A' 的描述方法及考慮如何記錄A中節點所能覆蓋的B中未覆蓋節點的數目。由于對集合A' 僅使用加法運算，則可用一維整型數組C來描述A '，用m 來記錄A' 中元素個數。將A' 中的成員記錄在C[ 0 :m-1] 中。對于A中頂點i，令N e wi 為i 所能覆蓋的B中未覆蓋的頂點數目。逐步選擇N e wi 值最大的頂點。由于一些原來未被覆蓋的頂點現在被覆蓋了，因此還要修改各N e wi 值。在這種更新中，檢查B中最近一次被V覆蓋的頂點，令j 為這樣的一個頂點，則A中所有覆蓋j 的頂點的N e wi 值均減1。

例1-13 考察圖1 - 6，初始時(N e w1 , N e w2 , N e w3 , N e w16 , N e w17 ) = ( 6 , 4 , 5 , 6 , 4 )。假設在例1 - 1 2中，第一步選擇頂點1 6，為更新N e wi 的值檢查B中所有最近被覆蓋的頂點，這些頂點為5 , 6 , 8 , 1 2 , 1 4和1 5。當檢查頂點5時，將頂點2和1 6的N e wi 值分別減1，因為頂點5不再是被頂點2和1 6覆蓋的未覆蓋節點；當檢查頂點6時，頂點1 , 2 ,和1 6的相應值分別減1；同樣，檢查頂點8時，1，2，3和1 6的值分別減1；當檢查完所有最近被覆蓋的頂點，得到的N e wi 值為（4，1，0，4）。下一步選擇頂點1，最新被覆蓋的頂點為4，7，9和1 3；檢查頂點4時，N e w1 , N e w2, 和N e w1 7 的值減1；檢查頂點7時，N e w1 的值減1，因為頂點1是覆蓋7的唯一頂點。

為了實現頂點選取的過程，需要知道N e wi 的值及已被覆蓋的頂點。可利用一個二維數組來達到這個目的，N e w是一個整型數組，New[i] 即等于N e wi，且c o v為一個布爾數組。若頂點i未被覆蓋則c o v [ i ]等于f a l s e，否則c o v [ i ]為t r u e。現將圖1 - 7的偽代碼進行細化得到圖1 - 8。

m=0; //當前覆蓋的大小

對于A中的所有i，New[i]=Degree[i]

對于B中的所有i，C o v [ i ] = f a l s e

while (對于A中的某些i,New[i]>0) {

設v是具有最大的N e w [ i ]的頂點；

C [ m + + ] = v ;

for ( 所有鄰接于v的頂點j) {

if (!Cov[j]) {

Cov[j]= true;

對于所有鄰接于j的頂點，使其N e w [ k ]減1

} } }

if (有些頂點未被覆蓋) 失敗

else 找到一個覆蓋

圖1-8  圖1-7的細化

更新N e w的時間為O (e)，其中e 為二分圖中邊的數目。若使用鄰接矩陣，則需花(n2 ) 的時間來尋找圖中的邊，若用鄰接鏈表，則需(n+e) 的時間。實際更新時間根據描述方法的不同為O (n2 ) 或O (n+e)。逐步選擇頂點所需時間為(S i z e O f A)，其中S i z e O f A=| A |。因為A的所有頂點都有可能被選擇，因此所需步驟數為O ( S i z e O f A )，覆蓋算法總的復雜性為O ( S i z e O f A 2+n2) = O ( n2)或O (S i z e Of A2+n + e)。

2. 降低復雜性

通過使用有序數組N e wi、最大堆或最大選擇樹（max selection tree）可將每步選取頂點v的復雜性降為( 1 )。但利用有序數組，在每步的最后需對N e wi 值進行重新排序。若使用箱子排序，則這種排序所需時間為(S i z e O f B ) ( S i z e O fB =|B| ) （見3 . 8 . 1節箱子排序）。由于一般S i z e O f B比S i z e O f A大得多，因此有序數組并不總能提高性能。

如果利用最大堆，則每一步都需要重建堆來記錄N e w值的變化，可以在每次N e w值減1時進行重建。這種減法操作可引起被減的N e w值最多在堆中向下移一層，因此這種重建對于每次N e w值減1需( 1 )的時間，總共的減操作數目為O (e)。因此在算法的所有步驟中，維持最大堆僅需O (e)的時間，因而利用最大堆時覆蓋算法的總復雜性為O (n2 )或O (n+e)。

若利用最大選擇樹，每次更新N e w值時需要重建選擇樹，所需時間為(log S i z e O f A)。重建的最好時機是在每步結束時，而不是在每次N e w值減1時，需要重建的次數為O (e)，因此總的重建時間為O (e log S i z e OfA)，這個時間比最大堆的重建時間長一些。然而，通過維持具有相同N e w值的頂點箱子，也可獲得和利用最大堆時相同的時間限制。由于N e w的取值范圍為0到S i z e O f B，需要S i z e O f B+ 1個箱子，箱子i 是一個雙向鏈表，鏈接所有N e w值為i 的頂點。在某一步結束時，假如N e w [ 6 ]從1 2變到4，則需要將它從第1 2個箱子移到第4個箱子。利用模擬指針及一個節點數組n o d e（其中n o d e [ i ]代表頂點i，n o d e [ i ] . l e f t和n o d e [ i ] . r i g h t為雙向鏈表指針），可將頂點6從第1 2個箱子移到第4個箱子，從第1 2個箱子中刪除n o d e [ 0 ]并將其插入第4個箱子。利用這種箱子模式，可得覆蓋啟發式算法的復雜性為O (n2 )或O(n+e)。（取決于利用鄰接矩陣還是線性表來描述圖）。

3. 雙向鏈接箱子的實現

為了實現上述雙向鏈接箱子，圖1 - 9定義了類U n d i r e c t e d的私有成員。N o d e Ty p e是一個具有私有整型成員l e f t和r i g h t的類，它的數據類型是雙向鏈表節點，程序1 3 - 3給出了U n d i r e c t e d的私有成員的代碼。

 

void CreateBins (int b, int n)

創建b個空箱子和n個節點

void DestroyBins() { delete [] node;