【正文】 , 1 0 ) , (b , h , 1 1 ) , (d , f , 1 4 )}E ={(g,I,6),(c,d,7),(a,h,8),(b,c,8), (d,e,9), (e,f,10), (b,h,11),(d,f,14)} E ={(a,h,8),(b,c,8), (d,e,9), (e,f,10), (b,h,11),(d,f,14)} 接受邊 (c,f) UNION(c,f) 森林由 4棵樹組成 選取邊（ g,I,6）但因為 g和 i在一個連通子圖中，即(g)和 (i)相同，所以拒絕邊 (g,i) 接受邊 (c,d) UNION(c,d) 森林由 3棵樹組成 圖 Kruskal算法的執(zhí)行過程 (續(xù) ) 94221478ahbig fc de( i )拒絕邊 (b , c ) , 接受邊 (d , e )U N I O N (d , e )森林由 1 棵樹組 成A ＝ {( h , g ) , (g , f ) , (c , i ) , (a , b ) , (c , f ) , (c , d ) , (a , h ) , (d , e )}E ＝ {( e , f , 1 0 ) , (b , h, 11 ) , (d , f , 1 4 )}4221478ahbig fc de( h )拒絕邊 (h , i ) , 接受邊 (a , h )U N I O N (a , h )森林由 2 棵樹組 成A ＝ {( h , g ) , (g , f ) , (c , i ) , (a , b ) , (c , f ) , (c , d ) , (a , h ) }E ＝ {( b , c , 8 ) , (d , e, 9 ) , (e , f , 1 0 ) , (b , h , 1 1 ) , (d , f , 1 4 )} 拒絕邊 (h,i) 接受邊 (a,h) UNION(a,h) 森林由 2棵樹組成 拒絕邊 (b,c) 接受邊 (d,e) UNION(d,e) 森林由 1棵樹組成 圖 Kruskal算法的執(zhí)行過程 (續(xù) ) 94221478ahbig fc de( j )E ＝邊 (e , f ) , (b , h ) , (d , f ) 均 被 拒 絕 集 合 E 變?yōu)榭誂 ＝ {( h , g ) , (g , f ) , (c , i ) , (a , b ) , (c , f ) , (c , d ) , (a , h ) , (d , e )}?正確性證明 需要證明以下兩點： 1) 只要存在生成樹， K r u s k a l算法總能產(chǎn)生一棵生成樹； 2) 產(chǎn)生的生成樹具有最小耗費。 證明 1： 令 G為任意加權(quán)無向圖（即 G是一個無向網(wǎng)絡(luò)）。從 1 2 . 11 . 3節(jié)可知當(dāng)且僅當(dāng)一個無向圖連通時它有生成樹。而且在 Kruskal 算法中被拒絕（丟棄）的邊是那些會產(chǎn)生環(huán)路的邊。刪除連通圖環(huán)路中的一條邊所形成的圖仍是連通圖，因此如果 G在開始時是連通的，則 T與 E中的邊總能形成一個連通圖。也就是若 G開始時是連通的，算法不會終止于 E= 和 | T | n 1。 證明 2： 現(xiàn)在來證明所建立的生成樹 T具有最小耗費。由于 G具有有限棵生成樹，所以它至少具有一棵最小生成樹。令 U為這樣的一棵最小生成樹， T與 U都剛好有 n 1條邊。如果 T=U, 則 T就具有最小耗費，那么不必再證明下去。因此假設(shè) T≠U，令 k(k 0) 為在 T中而不在 U中的邊的個數(shù)，當(dāng)然 k 也是在 U中而不在 T中的邊的數(shù)目。 通過把 U變換為 T來證明 U與 T具有相同的耗費，這種轉(zhuǎn)化可在 k 步內(nèi)完成。每一步使在 T而不在 U中的邊的數(shù)目剛好減 1。而且 U的耗費不會因為轉(zhuǎn)化而改變。經(jīng)過 k 步的轉(zhuǎn)化得到的 U將與原來的 U具有相同的耗費，且轉(zhuǎn)化后 U中的邊就是 T中的邊。由此可知， T具有最小耗費。 ? 算法分析 :當(dāng)圖的邊數(shù)為 e時，將其組成優(yōu)先隊列需要時間 O(e)。 ? while循環(huán)中 ,DeleteMin需要 O(loge)時間因此關(guān)于優(yōu)先隊列所作運算需時間 O(eloge)。 ? 實現(xiàn) UnionFind所需的時間為 O(eloge)。 ? 所以 Kruska的時間是 O(eloge),適合求邊數(shù)較少的最小生成樹。 反之，用 Prim算法 [最小代價通訊網(wǎng)絡(luò) ] 在 N城市之間架設(shè)通訊線路 ,要求造價最低 . 城市之間所有可能的通訊連接視作一個無向圖 G,G中每邊的權(quán)值表示建成這段線路的代價 . 問題轉(zhuǎn)化為求一棵最小生成樹 . 問題描述 : 輸入 :任一連通圖 G (該圖的邊集合 ) 可行解 :圖 G的生成樹 優(yōu)化函數(shù) :生成樹的各邊權(quán)值之和 最優(yōu)解 :使優(yōu)化函數(shù)達到最小值的生成樹 . 最優(yōu)化問題 (optimization problem): 問題可描述為 有 n個輸入 (x1,x2,...xn),一組約束條件 和一個優(yōu)化(目標(biāo) )函數(shù)。滿足約束條件的輸入稱為 可行解 ,它 是輸入的一個子集 .使優(yōu)化函數(shù)取得極值的可行解稱為 最優(yōu)解 . 算法設(shè)計與分析 貪心算法 例 1 *旅行商問題 (貨郎擔(dān)問題 ) 問題 : 設(shè)一個由 N個城市 v1,v2,…vn組成的網(wǎng)絡(luò) , ci,j 為從 vi 到 vj的代價不妨設(shè) ci,j = cj,i ,且 ci,i=? .一推銷員要從某城市出發(fā)經(jīng)過每城市一次且僅一次后返回出發(fā)地問如何選擇路線使代價最小 。 5 1 4 3 1 7 3 4 2 2 ? 1 2 7 51 ? 4 4 32 4 ? 1 27 4 1 ? 35 3 2 3 ?算法設(shè)計與分析 貪心算法 抽象描述 :將城市以及之間的道路抽象為一個無向圖 G, G中每邊的權(quán)值表示這段線路的代價 . 問題轉(zhuǎn)化為求一條最佳周游路線 :從一點出發(fā) ,經(jīng)過每點一次且僅一次并返回原點 ,且該路線的總代價最小 . v1 v5 v2 v4 v3 C= 輸入 :城市的數(shù)目 n,代價矩陣 c=c(1..n,1..n). 輸出 : 最小 代價 路線 1. tour:=0。 // tour 紀錄路線 / 2. cost:=0。 // cost 紀錄到目前為止的花費 / 3. v:=N。 // N為起點城市 , v為當(dāng)前出發(fā)城市 / 4. for k:=1 to N1 do 5. { tour:= tour+(v,w) //(v,w)為從 v到其余城市代價中值最小的邊 / 6. cost:= cost+c(v,w) 7 v:=w} 8 tour:= tour+(v,N) 9 cost:= cost+c(v,N) print tour, cost } 算法的最壞時間復(fù)雜性為 O(n2) *該算法不能求的最優(yōu)解 . 算法設(shè)計與分析 貪心算法 該問題為 NP難問題 . 算法設(shè)計與分析 貪心算法 問題 :設(shè)有 n個獨立的作業(yè) {1, 2, … , n}, 由 m臺相同的機器進行加工處理 . 作業(yè) i所需時間為 t i. 約定 :任何作業(yè)可以在任何一臺機器上加工處理 , 但未完工前不允許中斷處理 ,任何作業(yè)不能拆分成更小的子作業(yè) 。 要求給出一種作業(yè)調(diào)度方案 ， 使所給的 n 個作業(yè)在盡 可能短的時間內(nèi) 由 m臺機器加工處理完成 。 多機調(diào)度問題 該問題為 NP完全問題 . ? 調(diào)度問題是著名的 NP復(fù)雜問題（ NP表示nondeterministic polynornial) 中的一種。 NP復(fù)雜及 NP 完全問題是指尚未找到具有多項式時間復(fù)雜性算法的問題。 ? NP完全問題是一類判斷問題，也就是說，這類問題的答案為是或否。機器調(diào)度問題不是一個判斷題，因為它的答案是給出作業(yè)在機器間的分配方案（使完成時間最少）。 貪心近似算法 : 采用最長處理時間作業(yè)優(yōu)先的貪心策略 : 當(dāng) n≤m時 , 只要將機器 i的 [0, ti]時間區(qū)間分配給作業(yè) i即可。 當(dāng) nm時 , 將 n個作業(yè)依其所需的處理時間從大到小排序 ,然后依次 將作業(yè)分配給空閑的處理機 。 7個獨立作業(yè) {1, 2, 3, 4, 5, 6, 7} 由 M1,M2和 M3來加工處理 各作業(yè)所需時間間分別為 {2, 14, 4, 16, 6, 5, 3}。 16 14 6 5 4 2 3 圖給出了七個作業(yè)在三臺機器上進行調(diào)度的情形，七個作業(yè)所需時間分別為（ 2,14,4,16,6,5,3）。三臺機器分別被編號為 M M2 和 M3。每個陰影區(qū)代表作業(yè)的運行區(qū)間，陰影區(qū)的編號代表作業(yè)的索引號。 ? 作業(yè) 4在 0到 16 時刻被調(diào)度到機器 1（ M1）上運行，在這 16個時間單位中，機器 1完成了對作業(yè) 4的處理。作業(yè) 2在 0到 14時刻被調(diào)度到機器 2上處理，之后機器 2在 1 4到 17時刻處理作業(yè) 7。在機器 3上，作業(yè) 5在 0～ 6時刻內(nèi)完成，作業(yè) 6在 6～ 8時刻內(nèi)完成，作業(yè) 3在 11～ 1 5時刻內(nèi)完成，作業(yè) 1在 15～ 17時刻內(nèi)完成。注意到每個作業(yè)只能在一臺機器上 si 從時刻到 si+ti 時刻內(nèi)完成且任何機器在同一時刻僅能處理一個作業(yè)，完成所有作業(yè)的時刻為 17，因此完成時間或調(diào)度長度為 17。 算法設(shè)計與分析 貪心算法 class JobNode { friend void Greedy(JobNode * , int, int)。 friend void main(void)。 public: operator int () const {return time。 } private: int ID, time。 }。 class MachineNode { friend void Greedy(JobNode *, int, int)。 public: operator int( ) const { return avail。 } private: int ID, avail。 } 多機調(diào)度問題的 貪心近似算法 多機調(diào)度問題的 貪心近似算法 templateclass Type void Greedy(Type a[]， int n， int m) {if (n=m){ cont”為每個作業(yè)分配一臺機器 .“endl return； } Sort(a， n)； MinHeapMachineNodeH(m)； MachineNode x； for(int： i=1； i=m。 i++){ x． avail=0； x． ID=i。 H． Insert(x)； } for(inti： n； i=1； i){ H． DeleteMin(x)； cout”將機器” x． ID“從” x． avail到” (x． avail十 a[i]． time) ”的時間段分配給作業(yè)” a[i]. IDendl； x． avail+=a[i]． time； H． insert(x)； } }