第4章貪心算法(編輯修改稿)
2024-08-16 11:24 本頁面
【文章內(nèi)容簡介】 叉樹 T。 算法以 |C|個葉結(jié)點開始，執(zhí)行 |C|－ 1次的 “ 合并 ”運算后產(chǎn)生最終所要求的樹 T。 26 哈夫曼編碼 在書上給出的算法 huffmanTree中，編碼字符集中每一字符 c的頻率是 f(c)。 以 f為鍵值的優(yōu)先隊列 Q用在貪心選擇 時有效地確定算法當(dāng)前要合并的 2棵具有最小頻率的樹。一旦 2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的 2棵樹的頻率之和，并將新樹插入優(yōu)先隊列 Q。經(jīng)過 n－ 1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹 T。 算法 huffmanTree用最小堆實現(xiàn)優(yōu)先隊列 Q。初始化優(yōu)先隊列需要 O(n)計算時間，由于最小堆的removeMin和 put運算均需 O(logn)時間， n－ 1次的合并總共需要 O(nlogn)計算時間。因此，關(guān)于 n個字符的哈夫曼算法的 計算時間 為 O(nlogn) 。 27 哈夫曼編碼 哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有 貪心選擇性質(zhì) 和 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì) 28 單源最短路徑 給定帶權(quán)有向圖 G =(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定 V中的一個頂點，稱為 源 。現(xiàn)在要計算從源到所有其它各頂點的 最短路長度 。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為 單源最短路徑問題 。 算法基本思想 Dijkstra算法是解單源最短路徑問題的貪心算法。 29 單源最短路徑 其 基本思想 是，設(shè)置頂點集合 S并不斷地作 貪心選擇來擴(kuò)充這個集合。一個頂點屬于集合 S當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知。 初始時， S中僅含有源。設(shè) u是 G的某一個頂點，把從源到 u且中間只經(jīng)過 S中頂點的路稱為從源到 u的特殊路徑，并用數(shù)組 dist記錄當(dāng)前每個頂點所對應(yīng)的最短特殊路徑長度。 Dijkstra算法每次從 VS中取出具有最短特殊路長度的頂點 u，將 u添加到 S中，同時對數(shù)組 dist作必要的修改。一旦 S包含了所有 V中頂點， dist就記錄了從源到所有其它頂點之間的最短路徑長度。 30 單源最短路徑 例如 ，對右圖中的有向圖，應(yīng)用 Dijkstra算法計算從源頂點 1到其它頂點間最短路徑的過程列在下頁的表中。 31 單源最短路徑 迭代 S u dist[2] dist[3] dist[4] dist[5] 初始 {1} 10 maxint 30 100 1 {1,2} 2 10 60 30 100 2 {1,2,4} 4 10 50 30 90 3 {1,2,4,3} 3 10 50 30 60 4 {1,2,4,3,5} 5 10 50 30 60 Dijkstra算法的迭代過程： 32 單源最短路徑 算法的正確性和計算復(fù)雜性 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì) (3)計算復(fù)雜性 對于具有 n個頂點和 e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個圖，那么 Dijkstra算法的主循環(huán)體需要 時間。這個循環(huán)需要執(zhí)行 n1次，所以完成循環(huán)需要 時間。算法的其余部分所需要時間不超過 。 )(nO)( 2nO)( 2nO33 最小生成樹 設(shè) G =(V,E)是無向連通帶權(quán)圖，即一個 網(wǎng)絡(luò) 。 E中每條邊 (v,w)的權(quán)為 c[v][w]。如果 G的子圖 G’是一棵包含 G的所有頂點的樹，則稱 G’為 G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的 耗費 。在 G的所有生成樹中，耗費最小的生成樹稱為 G的 最小生成樹 。 網(wǎng)絡(luò)的最小生成樹在實際中有廣泛應(yīng)用。 例如 ，在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊 (v,w)的權(quán)c[v][w]表示建立城市 v和城市 w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。 34 最小生成樹 最小生成樹性質(zhì) 用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小生成樹的 Prim算法和 Kruskal算法 都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這 2個算法做貪心選擇的方式不同，它們都利用了下面的 最小生成樹性質(zhì) ： 設(shè) G=(V,E)是連通帶權(quán)圖， U是 V的真子集。如果(u,v)?E，且 u?U， v?VU，且在所有這樣的邊中，(u,v)的權(quán) c[u][v]最小，那么一定存在 G的一棵最小生成樹，它以 (u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì) 。 35 最小生成樹 Prim算法 設(shè) G=(V,E)是連通帶權(quán)圖， V={1,2,… ,n}。 構(gòu)造 G的最小生成樹的 Prim算法的 基本思想 是：首先置 S={1}，然后，只要 S是 V的真子集，就作如下的 貪心選擇 ： 選取滿足條件 i?S， j?VS，且 c[i][j]最小的邊，將頂點 j添加到 S中。這個過程一直進(jìn)行到 S=V時為止。 在這個過程中選取到的所有邊恰好構(gòu)成 G的一棵 最小生成樹 。 36 最小生成樹 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的 邊集合 T始終包含 G的某棵最小生成樹中的邊 。因此，在算法結(jié)束時， T中的所有邊構(gòu)成 G的一棵最小生成樹。 例如 ，對于右圖中的帶權(quán)圖，按 Prim算法 選取邊的過程如下頁圖所示。 37 最小生成樹 38 最小生成樹 在上述 Prim算法中，還應(yīng)當(dāng)考慮 如何有效地找出滿足條件 i?S,j?VS，且權(quán) c[i][j]最小的邊 (i,
化學(xué)相關(guān)推薦
鄂ICP備17016276號-1