1[1].貪婪算法.doc

第 1 章 貪婪算法雖然設計一個好的求解算法更像是一門藝術，而不像是技術，但仍然存在一些行之有效的能夠用于解決許多問題的算法設計方法，你可以使用這些方法來設計算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進行細致的調整。但是在某些情況下，算法經(jīng)過調整之后性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。本章首先引入最優(yōu)化的概念，然后介紹一種直觀的問題求解方法：貪婪算法。最后，應用該算法給出貨箱裝船問題、背包問題、拓撲排序問題、二分覆蓋問題、最短路徑問題、最小代價生成樹等問題的求解方案。1.1 最優(yōu)化問題本章及后續(xù)章節(jié)中的許多例子都是最優(yōu)化問題（ optimization problem），每個最優(yōu)化問題都包含一組限制條件（ c o n s t r a i n t）和一個優(yōu)化函數(shù)（ optimization function），符合限制條件的問題求解方案稱為可行解（ feasible solution），使優(yōu)化函數(shù)取得最佳值的可行解稱為最優(yōu)解（optimal solution）。例1-1 渴嬰問題 有一個非?？实摹⒙斆鞯男雰?，她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類的果汁、許多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到n 種不同的飲料。根據(jù)以前關于這n 種飲料的不同體驗，此嬰兒知道這其中某些飲料更合自己的胃口，因此，嬰兒采取如下方法為每一種飲料賦予一個滿意度值：飲用1盎司第i 種飲料，對它作出相對評價，將一個數(shù)值si 作為滿意度賦予第i 種飲料。通常，這個嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴的需要，但是不幸的是：具有最大滿意度值的飲料有時并沒有足夠的量來滿足此嬰兒解渴的需要。設ai是第i 種飲料的總量（以盎司為單位），而此嬰兒需要t 盎司的飲料來解渴，那么，需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢？設各種飲料的滿意度已知。令xi 為嬰兒將要飲用的第i 種飲料的量，則需要解決的問題是：找到一組實數(shù)xi（1in），使n i = 1si xi 最大，并滿足：n i=1xi =t 及0xiai 。需要指出的是：如果n i = 1ai t，則不可能找到問題的求解方案，因為即使喝光所有的飲料也不能使嬰兒解渴。對上述問題精確的數(shù)學描述明確地指出了程序必須完成的工作，根據(jù)這些數(shù)學公式，可以對輸入/ 輸出作如下形式的描述：輸入：n，t，si ，ai（其中1in，n 為整數(shù)，t、si 、ai 為正實數(shù)）。輸出：實數(shù)xi（1in），使n i= 1si xi 最大且n i=1xi =t（0xiai）。如果n i = 1ai t，則輸出適當?shù)腻e誤信息。在這個問題中，限制條件是n i= 1xi =t 且0xiai，1in。而優(yōu)化函數(shù)是n i= 1si xi 。任何滿足限制條件的一組實數(shù)xi 都是可行解，而使n i= 1si xi 最大的可行解是最優(yōu)解。例1-2 裝載問題 有一艘大船準備用來裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設第i 個貨箱的重量為wi（1in），而貨船的最大載重量為c，我們的目的是在貨船上裝入最多的貨物。這個問題可以作為最優(yōu)化問題進行描述：設存在一組變量xi ，其可能取值為0或1。如xi 為0，則貨箱i 將不被裝上船；如xi 為1，則貨箱i 將被裝上船。我們的目的是找到一組xi ，使它滿足限制條件n i = 1wi xi c 且x i 0, 1, 1 in。相應的優(yōu)化函數(shù)是n i= 1xi 。滿足限制條件的每一組xi 都是一個可行解，能使n i= 1xi 取得最大值的方案是最優(yōu)解。例1-3 最小代價通訊網(wǎng)絡 城市及城市之間所有可能的通信連接可被視作一個無向圖，圖的每條邊都被賦予一個權值，權值表示建成由這條邊所表示的通信連接所要付出的代價。包含圖中所有頂點（城市）的連通子圖都是一個可行解。設所有的權值都非負，則所有可能的可行解都可表示成無向圖的一組生成樹，而最優(yōu)解是其中具有最小代價的生成樹。在這個問題中，需要選擇一個無向圖中的邊集合的子集，這個子集必須滿足如下限制條件：所有的邊構成一個生成樹。而優(yōu)化函數(shù)是子集中所有邊的權值之和。1.2 算法思想在貪婪算法（greedy method）中采用逐步構造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標準下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準則（greedy criterion）。例1-4 找零錢 一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設提供了數(shù)目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個硬幣。選擇硬幣時所采用的貪婪準則如下：每一次選擇應使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應使零錢總數(shù)超過最終所需的數(shù)目。假設需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數(shù)超過6 7美分），第三枚應選擇1 0美分的硬幣，然后是5美分的，最后加入兩個1美分的硬幣。貪婪算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目）?？梢宰C明采用上述貪婪算法找零錢時所用的硬幣數(shù)目的確最少（見練習1）。例1-5 機器調度 現(xiàn)有n 件任務和無限多臺的機器，任務可以在機器上得到處理。每件任務的開始時間為si，完成時間為fi ，si k。尋找 1 ,n范圍內(nèi)最小的整數(shù)j，使得xjyj 。若沒有這樣的j 存在，則n i= 1xi =n i = 1yi 。如果有這樣的j 存在，則jk，否則y 就不是一個可行解，因為xjyj ，xj = 1且yj = 0。令yj = 1，若結果得到的y 不是可行解，則在 j+ 1 ,n范圍內(nèi)必有一個l 使得yl = 1。令yl = 0，由于wjwl ，則得到的y 是可行的。而且，得到的新y 至少與原來的y 具有相同數(shù)目的1。經(jīng)過數(shù)次這種轉化，可將y 轉化為x。由于每次轉化產(chǎn)生的新y 至少與前一個y 具有相同數(shù)目的1，因此x 至少與初始的y 具有相同的數(shù)目1。貨箱裝載算法的C + +代碼實現(xiàn)見程序1 3 - 1。由于貪婪算法按貨箱重量遞增的順序裝載，程序1 3 - 1首先利用間接尋址排序函數(shù)I n d i r e c t S o r t對貨箱重量進行排序（見3 . 5節(jié)間接尋址的定義），隨后貨箱便可按重量遞增的順序裝載。由于間接尋址排序所需的時間為O (nl o gn)（也可利用9 . 5 . 1節(jié)的堆排序及第2章的歸并排序），算法其余部分所需時間為O (n)，因此程序1 3 - 1的總的復雜性為O (nl o gn)。程序13-1 貨箱裝船templatevoid ContainerLoading(int x, T w, T c, int n)/ 貨箱裝船問題的貪婪算法/ xi = 1 當且僅當貨箱i被裝載， 1=i=n/ c是船的容量, w 是貨箱的重量/ 對重量按間接尋址方式排序/ t 是間接尋址表int *t = new int n+1;I n d i r e c t S o r t ( w, t, n);/ 此時, wti = wti+1, 1=in/ 初始化xfor (int i = 1; i = n; i+)xi = 0;/ 按重量次序選擇物品for (i = 1; i = n & wti = c; i+) xti = 1;c -= wti; / 剩余容量delete t;1.3.2 0/1背包問題在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即n i=1pi xi 取得最大值。約束條件為n i =1wi xic 和xi 0 , 1 ( 1in)。在這個表達式中，需求出xt 的值。xi = 1表示物品i 裝入背包中，xi =0 表示物品i 不裝入背包。0 / 1背包問題是一個一般化的貨箱裝載問題，即每個貨箱所獲得的價值不同。貨箱裝載問題轉化為背包問題的形式為：船作為背包，貨箱作為可裝入背包的物品。例1-8 在雜貨店比賽中你獲得了第一名，獎品是一車免費雜貨。店中有n 種不同的貨物。規(guī)則規(guī)定從每種貨物中最多只能拿一件，車子的容量為c，物品i 需占用wi 的空間，價值為pi 。你的目標是使車中裝載的物品價值最大。當然，所裝貨物不能超過車的容量，且同一種物品不得拿走多件。這個問題可仿照0 / 1背包問題進行建模，其中車對應于背包，貨物對應于物品。0 / 1背包問題有好幾種貪婪策略，每個貪婪策略都采用多步過程來完成背包的裝入。在每一步過程中利用貪婪準則選擇一個物品裝入背包。一種貪婪準則為：從剩余的物品中，選出可以裝入背包的價值最大的物品，利用這種規(guī)則，價值最大的物品首先被裝入（假設有足夠容量），然后是下一個價值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。例如，考慮n=2, w=100,10,10, p =20,15,15, c = 1 0 5。當利用價值貪婪準則時，獲得的解為x= 1 , 0 , 0 ，這種方案的總價值為2 0。而最優(yōu)解為 0 , 1 , 1 ，其總價值為3 0。另一種方案是重量貪婪準則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規(guī)則對于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解?？紤]n= 2 ,w=10,20, p=5,100, c= 2 5。當利用重量貪婪策略時，獲得的解為x =1,0, 比最優(yōu)解 0 , 1 要差。還可以利用另一方案，價值密度pi /wi 貪婪算法，這種選擇準則為：從剩余物品中選擇可裝入包的pi /wi 值最大的物品，這種策略也不能保證得到最優(yōu)解。利用此策略試解n= 3 ,w=20,15,15, p=40,25,25, c=30 時的最優(yōu)解。我們不必因所考察的幾個貪婪算法都不能保證得到最優(yōu)解而沮喪， 0 / 1背包問題是一個N P-復雜問題。對于這類問題，也許根本就不可能找到具有多項式時間的算法。雖然按pi /wi 非遞（增）減的次序裝入物品不能保證得到最優(yōu)解，但它是一個直覺上近似的解。我們希望它是一個好的啟發(fā)式算法，且大多數(shù)時候能很好地接近最后算法。在6 0 0個隨機產(chǎn)生的背包問題中，用這種啟發(fā)式貪婪算法來解有2 3 9題為最優(yōu)解。有5 8 3個例子與最優(yōu)解相差1 0 %，所有6 0 0個答案與最優(yōu)解之差全在2 5 %以內(nèi)。該算法能在O (nl o gn)時間內(nèi)獲得如此好的性能。我們也許會問，是否存在一個x (x1 0 0 )，使得貪婪啟發(fā)法的結果與最優(yōu)值相差在x%以內(nèi)。答案是否定的。為說明這一點，考慮例子n =2, w = 1 ,y, p= 1 0 , 9y, 和c= y。貪婪算法結果為x=1,0, 這種方案的值為1 0。對于y1 0 / 9，最優(yōu)解的值為9 y。因此，貪婪算法的值與最優(yōu)解的差對最優(yōu)解的比例為( ( 9y - 1 0)/9y* 1 0 0 ) %，對于大的y，這個值趨近于1 0 0 %。但是可以建立貪婪啟發(fā)式方法來提供解，使解的結果與最優(yōu)解的值之差在最優(yōu)值的x% (x100) 之內(nèi)。首先將最多k 件物品放入背包，如果這k 件物品重量大于c，則放棄它。否則，剩余的容量用來考慮將剩余物品按pi /wi 遞減的順序裝入。通過考慮由啟發(fā)法產(chǎn)生的解法中最多為k 件物品的所有可能的子集來得到最優(yōu)解。例13-9 考慮n =4, w=2,4,6,7, p=6,10,12,13, c = 11。當k= 0時，背包按物品價值密度非遞減順序裝入，首先將物品1放入背包，然后是物品2，背包剩下的容量為5個單元，剩下的物品沒有一個合適的，因此解為x = 1 , 1 , 0 , 0 。此解獲得的價值為1 6?，F(xiàn)在考慮k = 1時的貪婪啟發(fā)法。最初的子集為 1 , 2 , 3 , 4 。子集 1 , 2 產(chǎn)生與k= 0時相同的結果，考慮子集 3 ，置x3 為1。此時還剩5個單位的容量，按價值密度非遞增順序來考慮如何利用這5個單位的容量。首先考慮物品1，它適合，因此取x1 為1，這時僅剩下3個單位容量了，且剩余物品沒有能夠加入背包中的物品。通過子集 3 開始求解得結果為x = 1 , 0 , 1 , 0 ，獲得的價值為1 8。若從子集 4 開始，產(chǎn)生的解為x = 1 , 0 , 0 , 1 ，獲得的價值為1 9?？紤]子集大小為0和1時獲得的最優(yōu)解為 1 , 0 , 0 , 1 。這個解是通過k= 1的貪婪啟發(fā)式算法得到的。若k= 2，除了考慮k0時總的時間開銷為O (nk+1 )。實際觀察到的性能要好得多。1.3.3 拓撲排序一個復雜的工程通?？梢苑纸獬梢唤M小任務的集合，完成這些小任務意味著整個工程的完成。例如，汽車裝配工程可分解為以下任務：將底盤放上裝配線，裝軸，將座位裝在底盤上，上漆，裝剎車，裝門等等。任務之間具有先后關系，例如在裝軸之前必須先將底板放上裝配線。任務的先后順序可用有向圖表示稱為頂點活動（ Activity On Vertex, AOV）網(wǎng)絡。有向圖的頂點代表任務，有向邊(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）已暗示了這種關系。在很多條件下，任務的執(zhí)行是連續(xù)進行的，例如汽車裝配問題或平時購買的標有“需要裝配”的消費品（自行車、小孩的秋千裝置，割草機等等）。我們可根據(jù)所建議的順序來裝配。在由任務建立的有向圖中，邊（ i, j）表示在裝配序列中任務i 在任務j 的前面，具有這種性質的序列稱為拓撲序列（topological orders或topological sequences)。根據(jù)任務的有向圖建立拓撲序列的過程稱為拓撲排序（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）及其他邊所指示的序列相矛盾?？捎秘澙匪惴▉斫⑼負湫蛄小Ｋ惴ò磸淖蟮接业牟襟E構造拓撲序列，每一步在排好的序列中加入一個頂點。利用如下貪婪準則來選擇頂點：從剩下的頂點中，選擇頂點w，使得w 不存在這樣的入邊（ v,w），其中頂點v 不在已排好的序列結構中出現(xiàn)。注意到如果加入的頂點w違背了這個準則（即有向圖中存在邊（ v,w）且v 不在已構造的序列中），則無法完成拓撲排序，因為頂點v 必須跟隨在頂點w 之后。貪婪算法的偽代碼如圖1 3 - 5所示。while 循環(huán)的每次迭代代表貪婪算法的一個步驟?，F(xiàn)在用貪婪算法來求解圖1 - 4的有向圖。首先從一個空序列V開始，第一步選擇V的第一個頂點。此時，在有向圖中有兩個候選頂點1和2，若選擇頂點2，則序列V = 2，第一步完成。第二步選擇V的第二個頂點，根據(jù)貪婪準則可知候選頂點為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，它證明了若算法失敗，則有向圖中有環(huán)路。若有向圖中包含環(huán)qj qj + 1.qk qj , 則它沒有拓撲序列，因為該序列暗示了qj 一定要在qj 開始前完成。定理1-2 如果圖1 3 - 5算法失敗，則有向圖含有環(huán)路。證明注意到當失敗時| V |n, 且沒有候選頂點能加入V中，因此至少有一個頂點q1 不在V中，有向圖中必包含邊（ q2 , q1）且q2 不在V中，否則， q1 是可加入V的候選頂點。同樣，必有邊（q3 , q2）使得q3 不在V中，若q3 = q1 則q1 q2 q3 是有向圖中的一個環(huán)路；若q3 q1，則必存在q4 使（q4 , q3）是有向圖的邊且q4 不在V中，否則，q3 便是V的一個候選頂點。若q4 為q1 , q2 , q3 中的任何一個，則又可知有向圖含有環(huán)，因為有向圖具有有限個頂點數(shù)n，繼續(xù)利用上述方法，最后總能找到一個環(huán)路。2. 數(shù)據(jù)結構的選擇為將圖1 - 5用C + +代碼來實現(xiàn)，必須考慮序列V的描述方法，以及如何找出可加入V的候選頂點。一種高效的實現(xiàn)方法是將序列V用一維數(shù)組v 來描述的，用一個棧來保存可加入V的候選頂點。另有一個一維數(shù)組I n D e g r e e，I n D e g r e e j 表示與頂點j相連的節(jié)點i 的數(shù)目，其中頂點i不是V中的成員，它們之間的有向圖的邊表示為（ i, j）。當I n D e g r e e j 變?yōu)?時表示j 成為一個候選節(jié)點。序列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 剛剛變?yōu)?，因此將頂點5入棧。程序1 3 - 2給出了相應的C + +代碼，這個代碼被定義為N e t w o r k的一個成員函數(shù)。而且，它對于有無加權的有向圖均適用。但若用于無向圖（不論其有無加權）將會得到錯誤的結果，因為拓撲排序是針對有向圖來定義的。為解決這個問題，利用同樣的模板來定義成員函數(shù)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。這些函數(shù)可重載N e t w o r k中的函數(shù)并可輸出錯誤信息。如果找到拓撲序列，則Topological 函數(shù)返回t r u e；若輸入的有向圖無拓撲序列則返回f a l s e。當找到拓撲序列時，將其返回到v 0 :n- 1 中。3. Network:Topological 的復雜性第一和第三個f o r循環(huán)的時間開銷為(n )。若使用（耗費）鄰接矩陣,則第二個for 循環(huán)所用的時間為(n2 )；若使用鄰接鏈表,則所用時間為(n+e)。在兩個嵌套的while 循環(huán)中，外層循環(huán)需執(zhí)行n次，每次將頂點w 加入到v 中，并初始化內(nèi)層while 循環(huán)。使用鄰接矩陣時，內(nèi)層w h i l e循環(huán)對于每個頂點w 需花費(n)的時間；若利用鄰接鏈表，則這個循環(huán)需花費dwout 的時間，因此，內(nèi)層while 循環(huán)的時間開銷為(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 eint n = Ve r t i c e s ( ) ;/ 計算入度int *InDegree = new int n+1;InitializePos(); / 圖遍歷器數(shù)組for (int i = 1; i = n; i+) / 初始化InDegreei = 0;for (i = 1; i = n; i+) / 從i 出發(fā)的邊int u = Begin(i);while (u) I n D e g r e e u + + ;u = NextVe r t e x ( i ) ; / 把入度為的頂點壓入堆棧LinkedStack S;for (i = 1; i 0) 設v是具有最大的N e w i 的頂點；C m + + = v ;for ( 所有鄰接于v的頂點j) if (!Covj) Covj= true;對于所有鄰接于j的頂點，使其N e w k 減1 if (有些頂點未被覆蓋) 失敗else 找到一個覆蓋圖1-8 圖1-7的細化更新N e w的時間為O (e)，其中e 為二分圖中邊的數(shù)目。若使用鄰接矩陣，則需花(n2 ) 的時間來尋找圖中的邊，若用鄰接鏈表，則需(n+e) 的時間。實際更新時間根據(jù)描述方法的不同為O (n2 ) 或O (n+e)。逐步選擇頂點所需時間為(S i z e O f A)，其中S i z e O f A=| A |。因為A的所有頂點都有可能被選擇，因此所需步驟數(shù)為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. 降低復雜性通過使用有序數(shù)組N e wi、最大堆或最大選擇樹（max selection tree）可將每步選取頂點v的復雜性降為( 1 )。但利用有序數(shù)組，在每步的最后需對N e wi 值進行重新排序。若使用箱子排序，則這種排序所需時間為(S i z e O f B ) ( S i z e O fB =|B| ) （見3 . 8 . 1節(jié)箱子排序）。由于一般S i z e O f B比S i z e O f A大得多，因此有序數(shù)組并不總能提高性能。如果利用最大堆，則每一步都需要重建堆來記錄N e w值的變化，可以在每次N e w值減1時進行重建。這種減法操作可引起被減的N e w值最多在堆中向下移一層，因此這種重建對于每次N e w值減1需( 1 )的時間，總共的減操作數(shù)目為O (e)。因此在算法的所有步驟中，維持最大堆僅需O (e)的時間，因而利用最大堆時覆蓋算法的總復雜性為O (n2 )或O (n+e)。若利用最大選擇樹，每次更新N e w值時需要重建選擇樹，所需時間為(log S i z e O f A)。重建的最好時機是在每步結束時，而不是在每次N e w值減1時，需要重建的次數(shù)為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個箱子。利用模擬指針及一個節(jié)點數(shù)組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個箱子。利用這種箱子模式，可得覆蓋啟發(fā)式算法的復雜性為O (n2 )或O(n+e)。（取決于利用鄰接矩陣還是線性表來描述圖）。3. 雙向鏈接箱子的實現(xiàn)為了實現(xiàn)上述雙向鏈接箱子，圖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的類，它的數(shù)據(jù)類型是雙向鏈表節(jié)點，程序1 3 - 3給出了U n d i r e c t e d的私有成員的代碼。void CreateBins (int b, int n)創(chuàng)建b個空箱子和n個節(jié)點void DestroyBins() delete node;delete bin;void InsertBins(int b, int v)在箱子b中添加頂點vvoid MoveBins(int bMax, int ToBin, int v)從當前箱子中移動頂點v到箱子To B i nint *bin;b i n i 指向代表該箱子的雙向鏈表的首節(jié)點N o d e Type *node;n o d e i 代表存儲頂點i的節(jié)點圖1-9 實現(xiàn)雙向鏈接箱子所需的U n d i r e c t e d私有成員程序13-3 箱子函數(shù)的定義void Undirected:CreateBins(int b, int n)/