【正文】 O(nlogn)。 當(dāng) 時，首先將 n個作業(yè)依其所需的處理時間從大到小排序。 41 例 7 多機調(diào)度問題 采用 最長處理時間作業(yè)優(yōu)先 的貪心選擇策略可以設(shè)計出解多機調(diào)度問題的較好的近似算法。 約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。 這個問題是 NP完全問題 ，到目前為止還沒有有效的解法。當(dāng) 時， Kruskal算法比 Prim算法差，但當(dāng) 時， Kruskal算法卻比 Prim算法好得多。 對一個由連通分支組成的集合不斷進行修改，需要用到抽象數(shù)據(jù)類型 并查集 UnionFind所支持的基本運算。 按權(quán)的遞增順序查看等價于對 優(yōu)先隊列 執(zhí)行removeMin運算。 38 例 7 最小生成樹 例如， 對前面的連通帶權(quán)圖，按 Kruskal算法順序得到的最小生成樹上的邊如下圖所示。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接 2個不同的連通分支：當(dāng)查看到第 k條邊 (v,w)時，如果端點 v和w分別是當(dāng)前 2個不同的連通分支 T1和 T2中的頂點時，就用邊 (v,w)將 T1和 T2連接成一個連通分支，然后繼續(xù)查看第 k+1條邊；如果端點 v和 w在當(dāng)前的同一個連通分支中，就直接再查看第 k+1條邊。 用這個辦法實現(xiàn)的 Prim算法所需的 計算時間 為 )( 2nO37 例 7 最小生成樹 Kruskal算法 Kruskal算法構(gòu)造 G的最小生成樹的 基本思想 是，首先將 G的 n個頂點看成 n個孤立的連通分支。實現(xiàn)這個目的的較簡單的辦法是設(shè)置 2個數(shù)組 closest和lowcost。 例如 ，對于右圖中的帶權(quán)圖，按 Prim算法 選取邊的過程如下頁圖所示。 34 例 7 最小生成樹 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的 邊集合 T始終包含 G的某棵最小生成樹中的邊 。這個過程一直進行到 S=V時為止。 33 例 7 最小生成樹 Prim算法 設(shè) G=(V,E)是連通帶權(quán)圖， V={1,2,?,n} 。如果(u,v)?E，且 u?U， v?VU，且在所有這樣的邊中，(u,v)的權(quán) c[u][v]最小，那么一定存在 G的一棵最小生成樹，它以 (u,v)為其中一條邊。本節(jié)介紹的構(gòu)造最小生成樹的 Prim算法和 Kruskal算法 都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。 例如 ，在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊 (v,w)的權(quán)c[v][w]表示建立城市 v和城市 w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟的方案。在 G的所有生成樹中，耗費最小的生成樹稱為 G的 最小生成樹 。如果 G的子圖 G’ 是一棵包含 G的所有頂點的樹，則稱 G’ 為 G的生成樹。 )(O )( 2nO )231 例 7 最小生成樹 設(shè) G =(V,E)是無向連通帶權(quán)圖，即一個 網(wǎng)絡(luò) 。這個循環(huán)需要執(zhí)行 n1次，所以完成循環(huán)需要 時間。 28 例 6 單源最短路徑 例如 ，對右圖中的有向圖，應(yīng)用 Dijkstra算法計算從源頂點 1到其它頂點間最短路徑的過程列在下頁的表中。 Dijkstra算法每次從 VS中取出具有最短特殊路長度的頂點 u，將 u添加到 S中，同時對數(shù)組 dist作必要的修改。 初始時， S中僅含有源。 27 例 6 單源最短路徑 其 基本思想 是，設(shè)置頂點集合 S并不斷地作 貪心選擇來擴充這個集合。這個問題通常稱為 單源最短路徑問題 ?，F(xiàn)在要計算從源到所有其它各頂點的 最短路長度 。 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì) 26 例 6 單源最短路徑 給定帶權(quán)有向圖 G =(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。 算法以 |C|個葉結(jié)點開始，執(zhí)行 |C|－ 1次的“合并”運算后產(chǎn)生最終所要求的樹 T。 )()()( cdcfTB TCc??? 24 構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為 哈夫曼編碼 。 表示 最優(yōu)前綴碼 的二叉樹總是一棵 嚴(yán)格二叉樹 ，即樹中任一結(jié)點都有 2個兒子結(jié)點。這種編碼稱為 前綴碼 。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。其壓縮率通常在 20%～ 90%之間。 算法 loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為 O(nlogn)。 最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 c = w[t[i]]。 i = n w[t[i]] = c。 i++) x[i] = 0。 for (int i = 1。 20 templateclass Type void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 19 例 4 最優(yōu)裝載 有一批集裝箱要裝上一艘載重量為 c的輪船。但對于活動安排問題，貪心算法 greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合 A的規(guī)模最大。 18 例 3 活動安排問題 若被檢查的活動 i的開始時間 Si小于最近選擇的活動 j的結(jié)束時間 fi，則不選擇活動 i，否則選擇活動 i加入集合A中。當(dāng)輸入的活動已按結(jié)束時間的非減序排列，算法只需 O(n)的時間安排 n個活動，使最多的活動能相容地使用公共資源。也就是說，該算法的貪心選擇的意義是 使剩余的可安排時間段極大化 ，以便安排盡可能多的相容活動。 ? } ? } 各活動的起始時間和結(jié)束時間存儲于數(shù)組s和 f中且按結(jié)束時間的非減序排列 17 例 3 活動安排問題 由于輸入的活動以其完成時間的 非減序 排列，所以算法 greedySelector每次總是選擇 具有最早完成時間 的相容活動加入集合 A中。 j=i。i=n。 ? int j=1。陰影長條表示的活動是已選入集合 A的活動，而空白長條表示的活動是