4貪心算法與最優(yōu)策略(編輯修改稿)
2025-02-25 01:53 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 徑問(wèn)題 。 算法基本思想 Dijkstra算法是解單源最短路徑問(wèn)題的貪心算法。 27 例 6 單源最短路徑 其 基本思想 是，設(shè)置頂點(diǎn)集合 S并不斷地作 貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合 S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 初始時(shí)， S中僅含有源。設(shè) u是 G的某一個(gè)頂點(diǎn)，把從源到 u且中間只經(jīng)過(guò) S中頂點(diǎn)的路稱為從源到 u的特殊路徑，并用數(shù)組 dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。 Dijkstra算法每次從 VS中取出具有最短特殊路長(zhǎng)度的頂點(diǎn) u，將 u添加到 S中，同時(shí)對(duì)數(shù)組 dist作必要的修改。一旦 S包含了所有 V中頂點(diǎn)， dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。 28 例 6 單源最短路徑 例如 ，對(duì)右圖中的有向圖，應(yīng)用 Dijkstra算法計(jì)算從源頂點(diǎn) 1到其它頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。 29 例 6 單源最短路徑 迭代 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算法的迭代過(guò)程： 30 例 6 單源最短路徑 算法的正確性和計(jì)算復(fù)雜性 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì) (3)計(jì)算復(fù)雜性 對(duì)于具有 n個(gè)頂點(diǎn)和 e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么 Dijkstra算法的主循環(huán)體需要 時(shí)間。這個(gè)循環(huán)需要執(zhí)行 n1次，所以完成循環(huán)需要 時(shí)間。算法的其余部分所需要時(shí)間不超過(guò) 。 )(O )( 2nO )231 例 7 最小生成樹(shù) 設(shè) G =(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè) 網(wǎng)絡(luò) 。 E中每條邊 (v,w)的權(quán)為 c[v][w]。如果 G的子圖 G’ 是一棵包含 G的所有頂點(diǎn)的樹(shù)，則稱 G’ 為 G的生成樹(shù)。生成樹(shù)上各邊權(quán)的總和稱為該生成樹(shù)的 耗費(fèi) 。在 G的所有生成樹(shù)中，耗費(fèi)最小的生成樹(shù)稱為 G的 最小生成樹(shù) 。 網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。 例如 ，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊 (v,w)的權(quán)c[v][w]表示建立城市 v和城市 w之間的通信線路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。 32 例 7 最小生成樹(shù) 最小生成樹(shù)性質(zhì) 用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù)的有效算法。本節(jié)介紹的構(gòu)造最小生成樹(shù)的 Prim算法和 Kruskal算法 都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這 2個(gè)算法做貪心選擇的方式不同，它們都利用了下面的 最小生成樹(shù)性質(zhì) ： 設(shè) G=(V,E)是連通帶權(quán)圖， U是 V的真子集。如果(u,v)?E，且 u?U， v?VU，且在所有這樣的邊中，(u,v)的權(quán) c[u][v]最小，那么一定存在 G的一棵最小生成樹(shù)，它以 (u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì) 。 33 例 7 最小生成樹(shù) Prim算法 設(shè) G=(V,E)是連通帶權(quán)圖， V={1,2,?,n} 。 構(gòu)造 G的最小生成樹(shù)的 Prim算法的 基本思想 是：首先置 S={1}，然后，只要 S是 V的真子集，就作如下的 貪心選擇 ： 選取滿足條件 i?S， j?VS，且 c[i][j]最小的邊，將頂點(diǎn) j添加到 S中。這個(gè)過(guò)程一直進(jìn)行到 S=V時(shí)為止。 在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成 G的一棵 最小生成樹(shù) 。 34 例 7 最小生成樹(shù) 利用最小生成樹(shù)性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的 邊集合 T始終包含 G的某棵最小生成樹(shù)中的邊 。因此，在算法結(jié)束時(shí)， T中的所有邊構(gòu)成 G的一棵最小生成樹(shù)。 例如 ，對(duì)于右圖中的帶權(quán)圖，按 Prim算法 選取邊的過(guò)程如下頁(yè)圖所示。 35 例 7 最小生成樹(shù) 36 例 7 最小生成樹(shù) 在上述 Prim算法中，還應(yīng)當(dāng)考慮 如何有效地找出滿足條件 i?S,j?VS，且權(quán) c[i][j]最小的邊 (i,j)。實(shí)現(xiàn)這個(gè)目的的較簡(jiǎn)單的辦法是設(shè)置 2個(gè)數(shù)組 closest和lowcost。 在 Prim算法執(zhí)行過(guò)程中，先找出 VS中使 lowcost值最小的頂點(diǎn) j，然后根據(jù)數(shù)組 closest選取邊(j,closest[j］ )，最后將 j添加到 S中，并對(duì) closest和lowcost作必要的修改。 用這個(gè)辦法實(shí)現(xiàn)的 Prim算法所需的 計(jì)算時(shí)間 為 )( 2nO37 例 7 最小生成樹(shù) Kruskal算法 Kruskal算法構(gòu)造 G的最小生成樹(shù)的 基本思想 是，首先將 G的 n個(gè)頂點(diǎn)看成 n個(gè)孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接 2個(gè)不同的連通分支：當(dāng)查看到第 k條邊 (v,w)時(shí)，如果端點(diǎn) v和w分別是當(dāng)前 2個(gè)不同的連通分支 T1和 T2中的頂點(diǎn)時(shí)，就用邊 (v,w)將 T1和 T2連接成一個(gè)連通分支，然后繼續(xù)查看第 k+1條邊；如果端點(diǎn) v和 w在當(dāng)前的同一個(gè)連通分支中，就直接再查看第 k+1條邊。這個(gè)過(guò)程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。 38 例 7 最小生成樹(shù) 例如， 對(duì)前面的連通帶權(quán)圖，按 Kruskal算法順序得到的最小生成樹(shù)上的邊如下圖所示。 39 例 7 最小生成樹(shù) 關(guān)于 集合的一些基本運(yùn)算 可用于實(shí)現(xiàn) Kruskal算法。 按權(quán)的遞增順序查看等價(jià)于對(duì) 優(yōu)先隊(duì)列 執(zhí)行removeMin運(yùn)算。可以用 堆 實(shí)現(xiàn)這個(gè)優(yōu)先隊(duì)列。 對(duì)一個(gè)由連通分支組成的集合不斷進(jìn)行修改，需要用到抽象數(shù)據(jù)類型 并查集 UnionFind所支持的基本運(yùn)算。 當(dāng)圖的邊數(shù)為 e時(shí)， Kruskal算法所需的 計(jì)算時(shí)間是 。當(dāng) 時(shí)， Kruskal算法比 Prim算法差，但當(dāng) 時(shí)， Kruskal算法卻比 Prim算法好得多。 )log( eeO )( 2n?? )( 2noe ?40 例 8 多機(jī)調(diào)度問(wèn)題 多機(jī)調(diào)度問(wèn)題 要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由 m臺(tái)機(jī)器加工處理完成。 這個(gè)問(wèn)題是 NP完全問(wèn)題 ，到目前為止還沒(méi)有有效的解
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1