計算機算法設(shè)計與分析第2版4貪心算法-文庫吧資料
2025-01-10 01:36本頁面
【正文】 的同一個連通分支中，就直接再查看第 k+1條邊。 用這個辦法實現(xiàn)的 Prim算法所需的 計算時間 為 )( 2nO39 最小生成樹 Kruskal算法 Kruskal算法構(gòu)造 G的最小生成樹的 基本思想 是，首先將 G的 n個頂點看成 n個孤立的連通分支。實現(xiàn)這個目的的較簡單的辦法是設(shè)置 2個數(shù)組 closest和lowcost。 例如 ，對于右圖中的帶權(quán)圖，按 Prim算法 選取邊的過程如下頁圖所示。 36 最小生成樹 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的 邊集合 T始終包含 G的某棵最小生成樹中的邊 。這個過程一直進行到 S=V時為止。 35 最小生成樹 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的生成樹。 )(nO)( 2nO)( 2nO33 最小生成樹 設(shè) G =(V,E)是無向連通帶權(quán)圖，即一個 網(wǎng)絡(luò) 。這個循環(huán)需要執(zhí)行 n1次，所以完成循環(huán)需要 時間。 30 單源最短路徑 例如 ，對右圖中的有向圖，應(yīng)用 Dijkstra算法計算從源頂點 1到其它頂點間最短路徑的過程列在下頁的表中。 Dijkstra算法每次從 VS中取出具有最短特殊路長度的頂點 u，將 u添加到 S中，同時對數(shù)組 dist作必要的修改。 初始時， S中僅含有源。 29 單源最短路徑 其 基本思想 是，設(shè)置頂點集合 S并不斷地作 貪心選擇來擴充這個集合。這個問題通常稱為 單源最短路徑問題 ?，F(xiàn)在要計算從源到所有其它各頂點的 最短路長度 。 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì) 28 單源最短路徑 給定帶權(quán)有向圖 G =(V,E)，其中每條邊的權(quán)是非負實數(shù)。因此，關(guān)于 n個字符的哈夫曼算法的 計算時間 為 O(nlogn) 。 算法 huffmanTree用最小堆實現(xiàn)優(yōu)先隊列 Q。一旦 2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的 2棵樹的頻率之和，并將新樹插入優(yōu)先隊列 Q。 26 哈夫曼編碼 在書上給出的算法 huffmanTree中，編碼字符集中每一字符 c的頻率是 f(c)。 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹 T。 平均碼長 定義為： 使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集 C的 最優(yōu)前綴碼 。 24 哈夫曼編碼 編碼的前綴性質(zhì)可以使譯碼方法非常簡單。 前綴碼 對每一個字符規(guī)定一個 0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用 0， 1串表示各字符的最優(yōu)表示方式。 23 哈夫曼編碼 哈夫曼編碼 是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。 由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法 loading的正確性。} } 22 最優(yōu)裝載 貪心選擇性質(zhì) 可以證明最優(yōu)裝載問題具有貪心選擇性質(zhì) 。 i++) {x[t[i]] = 1。amp。 for (int i = 1。 i = n。 Sort(w, t, n)。具體算法描述如下頁。 算法描述 最優(yōu)裝載問題可用貪心算法求解。其中集裝箱 i的重量為 Wi。 實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解 01背包問題。由此就導(dǎo)出許多互相重疊的子問題。 19 貪心算法的基本要素 對于 01背包問題 ，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。因此，算法的計算時間上界為 O（ nlogn）。 } if (i=n) x[i]=c/w[i]。 x[i]=1。i=n。 float c=M。i=n。 int i。依此策略一直地進行下去，直到背包裝滿為止。 17 貪心算法的基本要素 首先計算每種物品單位重量的價值 Vi/Wi，然后，依貪心選擇策略，將盡可能多的 單位重量價值最高 的物品裝入背包。 16 貪心算法的基本要素 背包問題： 與 01背包問題類似，所不同的是在選擇物品 i裝入背包時， 可以選擇物品 i的一部分 ，而不一定要全部裝入背包， 1≤i≤n 。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大 ? 在選擇裝入背包的物品時，對每種物品 i只有 2種選擇，即裝入背包或不裝入背包。 貪心算法與動態(tài)規(guī)劃算法的差異 15 貪心算法的基本要素 01背包問題： 給定 n種物品和一個背包。 最優(yōu)子結(jié)構(gòu)性質(zhì) 14 貪心算法的基本要素 貪心算法和動態(tài)規(guī)劃算
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1