《貪心方法》課件

1、第4章 貪心方法從本章開始介紹一些與數(shù)據(jù)結構中不同的算法設計方法：貪心法，動態(tài)規(guī)劃，分枝限界法。其它的方法還有：線性規(guī)劃，整數(shù)規(guī)劃，遺傳算法，模擬退火算法等等。設計一個好的算法就像一門藝術。但仍然存在一些行之有效的能夠用于解決許多問題的算法設計方法，可以使用這些方法來設計算法。在許多情況下，為了獲得較好的性能，必須對這些算法進行細致的調整。但在某些情況下，算法經(jīng)過調整之后仍然無法達到要求，這時就必須尋求另外的方法來求解該問題。4.1 最優(yōu)化問題1. 問題的一般特征 問題有n個輸入，問題的解是由這n個輸入的某個子集組成，這個子集必須滿足某些事先給定的條件。約束條件：子集必須滿足的條件；可行解：滿

2、足約束條件的子集；可行解可能不唯一；目標函數(shù)：用來衡量可行解優(yōu)劣的標準，一般以函數(shù)的形式給出；最優(yōu)解：能夠使目標函數(shù)取極值（極大或極?。┑目尚薪狻?例1 渴嬰問題 有一個非?？实?、聰明的小嬰兒，她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類的果汁、許多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到n種不同的飲料。根據(jù)以前關于這n種飲料的不同體驗，此嬰兒知道這其中某些飲料更合自己的胃口，因此，嬰兒采取如下方法為每一種飲料賦予一個滿意度值：飲用1盎司第i種飲料，對它作出相對評價，將一個數(shù)值si作為滿意度賦予第i種飲料。 通常，這個嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴地需要

3、，但是不幸地是：具有最大滿意度值地飲料有時并沒有足夠地量來滿足此嬰兒解渴地需要。設ai是第i種飲料地總量，而此嬰兒需要t盎司的飲料來解渴，那么，需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢？上述問題可形式描述如下：輸入：n,t,si,ai(其中1in,n為整數(shù)，t、si、ai為正實數(shù))。輸出：實數(shù)xi(1in)，使 最大，且 。如果 ，則輸出適當?shù)腻e誤信息。限制條件為 優(yōu)化函數(shù)為 任何滿足限制條件的一組實數(shù)xi都是可行解，而使 最大的可行解是最優(yōu)解。 例2 裝箱問題 有一艘大船準備用來裝載貨物。所有待裝載貨物都裝在貨箱中，且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設第i種貨箱的

4、重量為wi(1in )，而貨船的最大載重量為c，我們的目標是在貨船上裝入最多的貨物。這個問題可以作為最優(yōu)化問題進行描述：設存在一組標量xi ,其可能取值為0或1。如果xi 為0，則貨箱i不被裝上船；如xi 為1，則貨箱i將被裝上船。我們的目的是找到一組xi ，使它滿足限制條件：相應的優(yōu)化函數(shù)是：滿足限制條件的每一組xi 都是可行解，能使取得最大值的方案是最優(yōu)解。例3 找零錢問題 一個小孩買了價值少于1元的糖，并將1元錢交給了售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設提供了數(shù)目不限的面值為50分、10分、5分、2分、1分的硬幣。 可以通過解不定方程來解決這一問題。也可以分步驟組成要找的零錢

5、數(shù)，每次加入一個硬幣。選擇硬幣時采用如下準則：每一次選擇應使零錢數(shù)盡量增大。為保證解的可行性，所選擇的硬幣不應使零錢總數(shù)超過最終所需的數(shù)目。 假設需要找給小孩88分，首先選1枚50分的硬幣，然后選3枚10分硬幣，再選1枚5分硬幣，1枚2分硬幣，1枚1分的硬幣。 問題：這樣得到的硬幣數(shù)目達到最少嗎？ 類似問題：工資發(fā)放。例4 最小代價通訊網(wǎng)絡 城市之間所有可能的通信連接可被視作一個無向圖，圖的每條邊都被賦予一個權值，權值表示建成由這條邊所表示的通信連接所要付出的代價。包含圖中所有頂點（城市）的連通子圖都是一個可行解。設所有權值都為負，則所有可能的可行解都可表示成無向圖的一組生成樹，而最優(yōu)解就是其

6、中具有最小代價的生成樹。 在這個問題中，需要選擇一個無向圖中的邊集合的子集，這個子集必須滿足如下限制條件：所有的邊構成一個生成樹。而優(yōu)化函數(shù)是子集中所有邊的權值之和。 例5 最短路徑問題 在有向圖中求一個頂點到另一個頂點的最短路徑。（如路由問題）例6 機器調度 現(xiàn)有n件任務和無限多臺機器，任務可以在機器上得到處理。每件任務的開始時間為si ，完成時間為fi ， si 0。 問題：采用怎樣的裝包方法才能使裝入背包的物品的總效益最大？ 如果所有物品的總重量不超過M，即 M，則把所有的物品都裝入背包中將獲得最大可能的效益值。 如果物品的總重量超過了M，則將有物品不能（全部）裝 入背包中。由于0 xi

7、1，所以可以把物品的一部分裝入背包，所以最終背包中可剛好裝入重量為M的若干物品（整個或一部分） 目標：使裝入背包的物品的總效益達到最大。 分析： 裝入背包的總重量不能超過M問題的形式描述 可 行 解： 滿足上述約束條件的任一集合(x1,x2,xn) 都是問題的一個可行解可行解可能有多個。 (x1,x2,xn)稱為問題的一個解向量最 優(yōu) 解：能夠使目標函數(shù)取最大值的可行解是問題的最優(yōu)解。 最優(yōu)解也可能有多個。 約束條件： 目標函數(shù)：例5.1 背包問題的實例 設，n=3，M=20， (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)。 可能的可行解如下

8、： (1/2,1/3,1/4) 16.5 24.25 /沒有放滿背包/ (1, 2/15, 0 ) 20 28.2 (0, 2/3, 1) 20 31 (0, 1, 1/2) 20 31.5 (x1,x2,x3) 2. 貪心策略求解 度量標準的選擇：三種不同的選擇1）以目標函數(shù)作為度量標準 即，每裝入一件物品，就使背包背包獲得最大可能的效益增量。 該度量標準下的 處理規(guī)則： 按效益值的非增次序將物品一件件地放入到背包； 如果正在考慮的物品放不進去，則只取其一部分裝滿背包：如果該物品的一部分不滿足獲得最大效益增量的度量標準，則在剩下的物品種選擇可以獲得最大效益增量的其它物品，將它或其一部分裝入背

9、包。 如：若M=2,背包外還剩兩件物品i,j，且有(pi 4，wi4) 和(pj 3，wj2)，則下一步應選擇j而非i放入背包： pi/2 = 2 pj 3實例分析（例4.1) p1p2 p3 首先將物品1放入背包，此時x11，背包獲得p125的效益增量，同時背包容量減少w118個單位，剩余空間M=2。 其次考慮物品2和3。就M=2而言有，只能選擇物品2或3的一部分裝入背包。 物品2： 若 x22/15， 則 p2 x216/53.2 物品3： 若 x32/10， 則 p3 x33 為使背包的效益有最大的增量，應選擇物品2的2/15裝包，即 x22/15 最后，背包裝滿， M=0，故物品3將不

10、能裝入背包，x30 。 背包最終可以獲得效益值 x1 p1 x2 p2x3 p3 28.2 (次優(yōu)解,非問題的最優(yōu)解)2）以容量作為度量標準 以目標函數(shù)作為度量標準所存在的問題：盡管背包的效益值每次得到了最大的增加，但背包容量也過快地被消耗掉了，從而不能裝入“更多”的物品。 改進：讓背包容量盡可能慢地消耗，從而可以盡量裝入“更多”的物品。 即，新的標準是：以容量作為度量標準 該度量標準下的處理規(guī)則： 按物品重量的非降次序將物品裝入到背包； 如果正在考慮的物品放不進去，則只取其一部分裝滿背包；實例分析（例4.1) w3w2 w1 首先將物品3放入背包，此時x31，背包容量減少w310個單位，剩余

11、空間M=10。同時，背包獲得p315的效益增量。 其次考慮物品1和2。就M=10而言有，也只能選擇物品1或2的一部分裝入背包。為使背包的按照“統(tǒng)一”的規(guī)則，下一步將放入物品2的10/15裝包，即 x210/152/3 最后，背包裝滿M=0，故物品1將不能裝入背包，x10 。 背包最終可以獲得效益值 x1 p1 x2 p2x3 p3 31 (次優(yōu)解,非問題的最優(yōu)解) 存在的問題：效益值沒有得到“最大”的增加3）最優(yōu)的度量標準 影響背包效益值的因素： 背包的容量M 放入背包中的物品的重量及其可能帶來的效益值 可能的策略是：在背包效益值的增長速率和背包容量消耗速率之間取得平衡，即每次裝入的物品應使它

12、所占用的每一單位容量能獲得當前最大的單位效益。 在這種策略下的量度是：已裝入的物品的累計效益值與所用容量之比。 故，新的量度標準是：每次裝入要使累計效益值與所用容量的比值有最多的增加和最小的減小。 此時，將按照物品的單位效益值：pi/wi 比值（密度）的非增次序考慮。實例分析（例4.1) p1/w1p3/w3 p2/w2 首先將物品2放入背包，此時x21，背包容量減少w215個單位，還剩余空間M=5。同時，背包獲得p224的效益增量。 其次考慮物品1和3。此時，應選擇物品3,且就M=5而言有，也只能放入物品3的一部分到背包中 。即 x35/101/2 最后，背包裝滿M=0，故物品1將不能裝入背

13、包，x10 。 背包最終可以獲得效益值 x1 p1 x2 p2x3 p3 31.5 (最優(yōu)解)93. 背包問題的貪心求解算法算法4.2 背包問題的貪心算法 procedure GREEDYKNAPSACK(P,W,M,X,n) /p(1:n)和w(1:n)分別含有按P(i)/W(i)P(i1)/W(i1)排序的n件物品的效益值和重量。M是背包的容量大小，而x(1:n)是解向量/ real P(1:n),W(1:n),X(1:n),M,cu; integer I,n X0 /將解向量初始化為空/ cuM /cu是背包的剩余容量/ for i1 to n do if W(i) cu then ex

14、it endif X(i) 1 cu cu-W(i) repeat if in then X(i) cu/W(i) endif end GREEDY-KNAPSACK4. 最優(yōu)解的證明 即證明：由第三種策略所得到的貪心解是問題的最優(yōu)解。 最優(yōu)解的含義：在滿足約束條件的情況下，可使目標函數(shù)取極（大或小）值的可行解。貪心解是可行解，故只需證明：貪心解可使目標函數(shù)取得極值。 證明的基本思想：將此貪心解與（假設中的）任一最優(yōu)解相比較。 如果這兩個解相同，則顯然貪心解就是最優(yōu)解。否則， 這兩個解不同，就去找開始不同的第一個分量位置i，然后設法用貪心解的這個xi去替換最優(yōu)解的那個xi ，并證明最優(yōu)解在分量

15、代換前后總的效益值沒有任何變化。 可反復進行代換，直到新產生的最優(yōu)解與貪心解完全一樣。這一代換過程中，最優(yōu)解的效益值沒有任何損失，從而證明貪心解的效益值與代換前后最優(yōu)解的效益值相同。即，貪心解如同最優(yōu)解一樣可取得目標函數(shù)的最大/最小值。 從而得證：該貪心解也即問題的最優(yōu)解。定理4.1 如果p1/w1 p2/w2 pn/wn,則算法GREEDY-KNAPSACK對于給定的背包問題實例生成一個最優(yōu)解。證明： 設X=(x1, x2, , xn)是GRDDDY-KNAPSACK所生成的貪心解。 如果所有的xi都等于1,則顯然X就是問題的最優(yōu)解。否則， 設j是使xi1的最小下標。由算法可知， xi=1

16、1ij, 0 xj1 xi=0 jin 若X不是問題的最優(yōu)解，則必定存在一個可行解 Y=(y1, y2, , yn),使得： 且應有： 設k是使得yk xk的最小下標，則有yk xk: a) 若k0,當且僅當作業(yè)i在其截至期限以前被完成時，則獲得pi0的效益。 問題：求這n個作業(yè)的一個子集J，其中的所有作業(yè)都可在其截至期限內完成。J是問題的一個可行解。 可行解J中的所有作業(yè)的效益之和是pi ，具有最大效益值的可行解是該問題的最優(yōu)解。 如果所有的作業(yè)都能在其期限之內完成則顯然可以獲得當前最大效益值；否則，將有作業(yè)無法完成決策應該執(zhí)行哪些作業(yè)，以獲得最大可能的效益值。 目標函數(shù)： 約束條件：所有的

17、作業(yè)都應在其期限之前完成 ti=q，將q位置之后的所有作業(yè)后移一位，作業(yè)i插入到位置q1處，從而得到一個包含k+1個作業(yè)的新的可行解。 若找不到這樣的q，作業(yè)i將被舍棄。 對i之后的其它作業(yè)重復上述過程直到n個作業(yè)處理完畢。最后J中所包含的作業(yè)集合是此時算法的貪心解，也是問題的最優(yōu)解。算法5.4 帶有限期和效益的單位時間的作業(yè)排序貪心算法 procedure JS(D,J,n,k) /D(1),D(n)是期限值。n1。作業(yè)已按p1p2pn的順序排序。J(i)是最優(yōu)解中的第i個作業(yè)，1ik。終止時， D(J(i)D(J(i1)， 1ik/ integer D(0:n),J(0:n),i,k,n,

18、r D(0)J(0)0 /初始化，設置崗哨/ k1;J(1)1 /計入作業(yè)1/ for i2 to n do /按p的非增次序考慮作業(yè)。找i的位置并檢查插入的可行性/ rk while D(J(r)D(i) and D(J(r) r do rr-1 repeat If D(J(r)D(i) and D(i)r then /把i插入到J中/ for ik to r+1 by -1 do J(i+1) J(i) /將插入點的作業(yè)后移一位/ repeat J(r+1) I;kk+1;K當前解中的作業(yè)數(shù) endif repeat end JS計算時間分析 for i2 to n do 將循環(huán)n-1次

19、rk while D(J(r)D(i) and D(J(r) r do 至多循環(huán)k次， k是當前計入J中的作業(yè)數(shù) rr-1 repeat If D(J(r)D(i) and D(i)r then for ik to r+1 by -1 do 循環(huán)k-r次，r是插入點的位置 J(i+1) J(i) repeat J(r+1) I;kk+1 endif repeat設s是最終計入J中的作業(yè)數(shù)，則算法JS所需要的總時間是O(sn)。sn，故最壞情況：TJS = (n2)，特例情況：pi=di=n-i+1,1in最好情況：TJS = (n)，特例情況：pi=di=i,1in6. 一種“更快”的作業(yè)排序

20、問題 使用不相交集合的 UNION和FIND算法（見1.4.3節(jié)），可以將JS的計算時間降低到數(shù)量級接近(n)。 前一種方法，納入序列J的作業(yè)存在向后移動問題，改進思想：將計入J的作業(yè)i盡量延遲處理，當然是在di之前。 時間片：-1,的單位時間稱為時間片對作業(yè)i分配處理時間時，分配盡量大的空時間片 。如果找不到一個空時間片，則拋棄i例5.3 n=5 p1-p5=20 15 10 5 1d1-d5=2 2 1 3 3J 已分配時間片 正考慮作業(yè) 動作 無 1 分配1,21 1,2 2 分配0,11,2 0,11,2 3 舍棄1,2 0,11,2 4 分配2,31,2,4 0,11,22,3 5

21、舍棄問題：如何確定最大的空時間片是多少？隨著作業(yè)的不斷加入，最大空時間片是變化的。如何動態(tài)改變作業(yè)的最大空時間片？基本思想1.用i表示時間片i-1,i,只需考慮這樣的時間片 i-1,i , 1i b, b=minn,maxdj2.將b個期限值分成一些集合:i:期限值,ni時間片對于任意一個期限值i,ni是使得nj i的最大整數(shù)且是空時間片。ni是i的最大空時間片，nj是j的最大空時間片當且僅當ni=nj時i和j在同一集合中即，具有相同最大空時間片的期限值在同一集合中3.用F(i)表示期限值i的當前最大空時間片 F(i)=niF(i)的值在每次處理完一個作業(yè)后，可能要更新。引入虛擬時間片0-1,

22、0避免極端情況產生b+1個期限值初始時為F(i)=i 0ib4. 用樹來表示集合P(i)0時 表示期限i的父親結點P(i)0時 表示期限i是根，且該集合中有|P(i)|個結點5.當前正考慮作業(yè)具有期限值d，則需要尋找期限值d所在集合，即尋找所在樹的根j若 F(j) =nj0即有空時間片，則這個作業(yè)分配時間片nj 并且 將這個集合與包含F(xiàn)(j)-1的集合合并（因為該集合中所有期限值的作業(yè)最大可分配時間片減少1）若 F(j)=0 則無空時間片，放棄此作業(yè)，處理下一個作業(yè)，直到處理完n個作業(yè)。初始值：F(i)=i 0 =i=b p(i)=-1;只包含一個期限值的樹算法4.5 作業(yè)排序的更快算法pro

23、c fjs（D,n,b,J,k）/假定作業(yè)按pi非增序排列，b=minn,maxdjfor i=1 to b do F(i)=i,P(i)=-1; repeatk=0;/J中的作業(yè)序號for i=1 to n do j=Find(min(n,D(i);/找期限值所屬集合的根j if F(j) 0 then k=k+1 ;J(k)=i/作業(yè)i計入解 l=Find(F(j)-1);Union(l,j); F(j)=F(l) endifrepeatend fjs例4.4 n=7, p1-p7=35,30,25,20,15,10,5d1-d7=4,2,4,3,4,8,3.利用fjs算法求最優(yōu)解解：考慮

24、 F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) J作業(yè)無 0 1 2 3 4 5 6 7 1 0 1 2 3 3 5 6 7 12 0 1 1 3 3 5 6 7 123 0 1 1 1 3 5 6 7 1234 0 0 1 1 3 5 6 7 12345 F(1)=0 舍棄 12346 0 0 1 1 3 5 6 6 123467 F(1)=0 舍棄 最優(yōu)解1,2,3,4,6-1-2 33 4-2 11 2-4 11 21 33 4-4 11 21 33 45.4 最優(yōu)歸并模式1. 問題的描述1）兩個文件的歸并問題 兩個已知文件的一次歸并所需的計算時間O(兩

25、個文件的元素總數(shù)) 例：n個記錄的文件 (n+m) 個記錄的文件 m個記錄的文件 (n+m)2）多個文件的歸并 已知n個文件，將之歸并成一個單一的文件 例：假定文件X1，X2， X3， X4，采用兩兩歸并的方式，可能的歸并模式有： X1+X2=Y1+X3= Y2+X4= Y3 X1+X2 = Y1 + Y3 X3+X4=Y2 二路歸并模式：每次僅作兩個文件的歸并；當有多個文件時，采用兩兩歸并的模式，最終得到一個完整的記錄文件。 二元歸并樹：二路歸并模式的歸并過程可以用一個二元樹的形式描述，稱之為二元歸并樹。如 6050302010X1Z1XX3X2歸并樹的構造 外結點：n個原始文件 內結點：一

26、次歸并后得到的文件 在兩路歸并模式下，每個內結點剛好有兩個兒子，代表把它的兩個兒子表示的文件歸并成其本身所代表的文件不同的歸并順序帶來的計算時間是不同的。 例4.5 已知X1,X2,X3是分別為30、20、10個記錄長度的已分類文件。將這3個文件歸并成長度為60的文件?？赡艿臍w并過程和相應的記錄移動次數(shù)如下： XX3X2X1移動50次移動60次XX1X2X3移動30次移動60次總移動次數(shù)：110次總移動次數(shù)：90次問題：采用怎樣的歸并順序才能使歸并過程中元素的移動次數(shù)最小（或執(zhí)行的速度最快）2. 貪心求解1) 度量標準的選擇 任意兩個文件的歸并所需的元素移動次數(shù)與這兩個文件的長度之和成正比；

27、度量標準：每次選擇需要移動次數(shù)最少的兩個集合進行歸并； 處理規(guī)則：每次選擇長度最小的兩個文件進行歸并。95355203060301510F4F3Z1Z2Z4Z3F1F5F2(F1,F2,F3,F4,F5) = (20,30,10,5,30)2) 目標函數(shù) 目標：元素移動的次數(shù)最少 實例：為得到歸并樹根結點表示的歸并文件，外部結點中每個文件記錄需要移動的次數(shù)該外部結點到根的距離，即根到該外部結點路徑的長度。如， F4 ： F4Z1Z2Z4最優(yōu)的二路歸并模式：與一棵具有最小外部帶權路徑長度的二元樹相對應。則F4中所有記錄在整個歸并過程中移動的總量|F4|*3 帶權外部路徑長度：記di是由根到代表文

28、件Fi的外部結點的距離，qi是Fi的長度，則這棵樹的代表的歸并過程的元素移動總量是：算法4.6 生成二元歸并樹的算法 procedure TREE(L,n) /L是n個單結點的二元樹表/ for i1 to n-1 do call GETNODE(T) /構造一顆新樹T/ LCHILD(T) LEAST(L) /從表L中選當前根WEIGHT最小的樹， 并從中刪除/ RCHILD(T) LEAST(L) WEIGHT(T) WEIGHT(LCHILD(T)+WEIGHT(RCHILD(T) call INSERT(L,T) /將歸并的樹T加入到表L中/ repeat return (LEAST(

29、L) /此時，L中的樹即為歸并的結果/ end TREE例5.6 已知六個初始文件，長度分別為：2,3,5,7,9,13。 采用算法TREE，各階段的工作狀態(tài)如圖所示：L迭代2357913023579131523579132510235791335101623579134510162323579135510162339時間分析 1) 循環(huán)體：n-1次 2) L以有序序列表示 LEAST(L): (1) INSERT(L,T): (n) 總時間： (n2) 3) L以min-堆表示 LEAST(L): (logn) INSERT(L,T): (logn) 總時間： (nlogn)3. 最優(yōu)解的證

30、明 定理3.4 若L最初包含n1個單結點的樹，這些樹有WEIGHT值為(q1,q2,qn)，則算法TREE對于具有這些長度的n個文件生成一棵最優(yōu)的二元歸并樹。證明：歸納法證明 當n=1時，返回一棵沒有內部結點的樹。定理得證。 假定算法對所有的(q1,q2,qm)，1mn,生成一棵最優(yōu)二元歸并樹。 對于n,假定q1q2qn,則q1和q2將是在for循環(huán)的第一次迭代中首先選出的具有最小WEIGHT值的兩棵樹（的WEIGHT值）；如圖所示，T是由這樣的兩棵樹構成的子樹：q1q2q1+q2T 設T是一棵對于(q1,q2,qn)的最優(yōu)二元歸并樹。 設P是T中距離根最遠的一個內部結點。 若P的兩棵子樹不是

31、q1和q2，則用q1和q2代換P當前的子樹而不會增加T的帶權外部路徑長度。 故，p應是最優(yōu)歸并樹中的子樹。 則在T中用一個權值為q1q2的外部結點代換T，得到的是一棵關于(q1q2,qn)最優(yōu)歸并樹T”。 而由歸納假設，在用權值為q1q2的外部結點代換了T之后，過程TREE將針對(q1q2,qn)得到一棵最優(yōu)歸并樹。將T帶入該樹，根據(jù)以上討論，將得到關于(q1,q2,qn)的最優(yōu)歸并樹。 故，TREE生成一棵關于(q1,q2,qn)的最優(yōu)歸并樹。5. k路歸并模式 每次同時歸并k個文件。 k元歸并樹：可能需要增加“虛”結點，以補充不足的外部結點度為0的結點。 如果一棵樹的所有內部結點的度都為k

32、，則外部結點數(shù)n滿足 n mod (k-1) = 1 對于滿足 n mod (k1) =1的整數(shù)n，存在一棵具有n個外部結點的k元樹T，且T中所有結點的度為k。 需要增加 最多k-2 個虛結點。 k路最優(yōu)歸并模式得貪心規(guī)則：每一步選取k棵具有最小長度的子樹歸并。4.5 最小生成樹1. 問題的描述 生成樹：設G=(V,E)是一個無向連通圖。如果G的生成子圖T=(V,E)是一棵樹，則稱T是G的一棵生成樹(spanning tree) G的邊賦予一個權值，表示成本、長度等。最小生成樹:具有最小成本的生成樹生成樹性質：1.無環(huán)2.包含所有節(jié)點3.各點連通 4.|V|=n，具有n-1條邊假定一個帶權無向

33、連通圖，希望選擇一組連線，連接所有的結點，并且具有最小的成本，即找最小生成樹。約束條件：cost(i,j)=wij (i,j) G無環(huán)目標函數(shù)：mincost(i,j) (i,j) T2. 貪心策略 度量標準：選擇能使迄今為止所計入的邊的成本和有最小增加的那條邊。 Prim算法 Kruskal算法 構成樹，最小的邊最小的邊，計入后無環(huán)146253103020452555405015353. Prim算法 策略：使得迄今所選擇的邊的集合A構成一棵樹；對將要計入到A中的下一條邊(u,v)，應是E中一條當前不在A中且使得A(u,v)也是一棵樹的最小成本邊。1462531030204525554050

34、153512162162316234邊(1,2)(2,6)(3,6)(6,4)成本102515201462531020251535(3,5)35V(TP) = 1,2,3,4,5,6E(TP) = (1,2),(2,6),(3,5),(4,6),(3,6) 算法思想1.將所有邊中的最小成本邊（K,L）計入數(shù)組T中，T是一個二維數(shù)組T(1.N-1，2)存儲n-1條邊的兩個端點。初始：T(1,1)=K T(1,2)=L2.要計入的邊(i,j)的特點:i是計入到樹的結點，j是不在樹中的結點cost(i,j)滿足上面要求的最小成本邊3.near(j)=0表示結點j已在樹中 near(j)0=i 表示結

35、點j不在樹中，結點i是與之相連的最小成本邊的結點。4.near(j)的值隨著結點不斷計入樹不斷可能更新計入樹的結點j，near(j)置0，不在樹中的結點j，near(j)=k，新計入樹的結點l，比較cost(j,k)和cost(j,l)，其中較小的一邊的另一個結點送near(j)5.邊的成本采用成本鄰接矩陣存放算法5.7 Prim最小生成樹算法 procedure PRIM(E,COST,n,T,mincost) /E是G的邊集.COST(n,n)是n結點圖G的成本鄰接矩陣，矩陣元素COST(i,j)是一個正實數(shù)，如果不存在邊(i,j)，則為。計算一棵最小生成樹并把它作為一個集合存放到數(shù)組T(

36、1:n-1,2)中(T(i,1),T(i,2)是最小成本生成樹的一條邊.最小成本生成樹的總成本最后賦給mincost/ real COST(n,n), mincost；integer NEAR(n), T(1:n-1,2) (k,l)具有最小成本的邊 mincostCOST(k,l) (T(1,1),T(1,2) (k,l) for i1 to n do /將NEAR置初值/ if COST(i,l) COST(i,k) then NEAR(i)l else NEAR(i) k endif repeat NEAR(k)NEAR(l)0 for i2 to n-1 do /找T的其余n-2條邊/

37、 設j是NEAR(j)0 且COST(j,NEAR(j)最小的下標 (T(i,1),T(i,2)(j,NEAR(j) mincostmincost+COST(j,NEAR(j) NEAR(j)0 for k1 to n do /修改NEAR/ if NEAR(k)0 and COST(k,NEAR(k)COST(k,j) then NEAR(k)j endif repeat repeat if mincost then print(no spanning tree) endif end PRIM計算復雜性：(n2) 找構成最小邊的結點j這個邊存入二維數(shù)組T修改near數(shù)組的值算法的改進從指定結

38、點開始建立生成樹，算法的3-9改為：mincost=0for i=1to n do near(i)=1repeatnear(1)=0for i=1 to n-1 do for k=1 to n do least=& if near(k)0 and cost(k,near(k)least then least=cost(k,near(k); j=k endif repeat T(i,1) T(i,2)=(j,near(j)near(j)=0其他不變4. Kruskal算法 （連通）圖的邊按成本的非降次序排列，下一條計入生成樹T中的邊是還沒有計入的邊中具有最小成本且和T中現(xiàn)有的邊不會構成環(huán)路的邊。

39、1462531030204525554050153512162162316234邊(1,2)(3,6)(4,6)(2,6)成本1015202516234563453454551462531020251535邊(3,5)成本35V(TK) = 1,2,3,4,5,6E(TK) = (1,2),(2,6),(3,5),(4,6),(3,6) 算法5.9 Kruskal算法 procedure KRUSKAL(E,COST,N,T,mincost) /G有n個結點，E是G的邊集。COST(u,v)是邊(u,v)的成本。T是最小成本生成樹的邊集，mincost是它的成本/ real mincost,

40、COST(1:n,1:n); integer PARENT(1:n), T(1:n-1,2),n 以邊成本為元素構造一個min堆 PARENT-1/每個結點都在不同的集合中/ imincost0 while in-1 and 堆非空 do 從堆中刪去最小成本邊(u,v)并重新構造堆 jFIND(u); kFIND(v) if(jk) then ii+1 T(i,1) u; T(i,2) v mincostmincost + COST(u,v) call UNION(j,k) endif repeat if in-1 then print(no spanning tree) endif retu

41、rn end KRUSKAL注： 邊集以min-堆的形式保存，一條當前最小成本邊可以在(loge)的時間內找到； 當且僅當圖G是不連通的，in-1；此時算法具有最壞的執(zhí)行時間； 算法的計算時間是(eloge)5. Sollin算法 Sollin算法每步選擇若干條邊。在每步開始時，選擇的邊及圖中的n個頂點形成一個生成樹的森林。在每一步中為森林中得每棵樹選擇一條邊，這條邊剛好有一個頂點在樹中且邊的代價最小。將所選擇的邊加入要創(chuàng)建的生成樹中。注意一個森林中的兩棵樹可以選擇同一條邊，因此必須多次復制同一條邊，在這種情況下，必須丟棄其中的一條邊。開始時，所選擇的邊的集合為空。若某一步結束時僅剩下一棵樹或

42、沒有剩余的邊可供選擇時算法終止。14625310302045255540501535146253對于前面的例子，初始狀態(tài)如圖(a)。圖（a）圖（b）146253圖（c）初始入選邊數(shù)為0時的情形如圖(b),森林中的每棵數(shù)均是單個頂點。頂點1，2，3，6所選擇的邊分別是(1,2),(2,1),(3,6),(4,6),(5,3),(6,3), 其中相同的邊有(3,6)與(6,3), (1,2)與(2,1)。這些邊加入到森林得到圖（C）。為森林中的樹選邊 （2,6）,構成樹。1462537281610142522241812146253714625371014221222146253716101425

43、12Sollin算法另一個示例。5.6 單源最短路徑1. 問題描述 最短路徑問題： 每對結點之間的路徑問題 特定線路下的最短路徑問題 單源最短路徑問題等 單源最短路徑問題 已知一個n結點有向圖G=(V,E)和邊的權函數(shù)c(e)，求由G中某指定結點v0到其它各結點的最短路徑。 假定邊的權值為正。例5.10 如圖所示。設v0是起始點，求v0到其它各結點的最短路徑。 路徑 長度(1) v0v2 10(2) v0v2v3 25(3) v0v2v3v1 45(4) v0v4 45注：路徑按照長度的非降次序給出v0v1v4v5v3v24545101520101533520302. 貪心策略求解1) 度量標

44、準 量度的選擇：迄今已生成的所有路徑長度之和為使之達到最小，其中任意一條路徑都應具有最小長度： 假定已經(jīng)構造了i條最短路徑，則下一條要構造的路徑應是下一條最短的路徑。 處理規(guī)則：按照路徑長度的非降次序依次生成從結點v0到其它各結點的最短路徑。 例： v0v2 v0v2v3 v0v2v3v1 v0v4 2) 貪心算法 設S是已經(jīng)對其生成了最短路徑的結點集合（包括v0)。 對于當前不在S中的結點w，記DIST(w)是從v0開始，只經(jīng)過S中的結點而在w結束的那條最短路徑的長度。則有，SW 如果下一條最短路徑是到結點u，則這條路徑是從結點v0出發(fā)在u處終止，且只經(jīng)過那些在S中的結點,即由v0至u的這條

45、最短路徑上的所有中間結點都是S中的結點: 設w是這條路徑上的任意中間結點，則從v0到u的路徑也包含了一條從v0到w的路徑，且其長度小于從v0到u的路徑長度。 v0,s1,s2,w,sm-1,u 均在S中 根據(jù)生成規(guī)則：最短路徑是按照路徑長度的非降次序生成的，因此從v0到w的最短路徑應該已經(jīng)生成。從而w也應該在S中。 故,不存在不在S中的中間結點。 所生成的下一條路徑的終點u必定是所有不在S內的結點中且具有最小距離DIST(u)的結點。SWu如果選出了這樣結點u并生成了從v0到u的最短路徑之后，結點u將成為S中的一個成員。此時，那些從v0出發(fā)，只經(jīng)過S中的結點并且在S外的結點w處結束的最短路徑可