一、單源最短路徑

??給定帶權(quán)有向圖G =(V,E)，其中每條邊的權(quán)是非負實數(shù)。另外，還給定V中的一個頂點，稱為源。現(xiàn)在 要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。

1.1 算法基本思想

??Dijkstra算法是解單源最短路徑問題的貪心算法。
??Dijkstra算法有關(guān)概念：
??X∈S←→x∈V且從s到x的最短路徑已經(jīng)找到
??初始：S={s},S=V時算法結(jié)束
??從s到u相對于S的最短路徑：從s到u且經(jīng)過S中頂點的最短路徑
??dist[u]：從s到u相對S最短路徑的長度
??short[u]：從s到u的最短路徑的長度
??dist[u]>=short[u]

1.2 算法設(shè)計思想

??輸入：有向圖G=(V,E)，V={1,2,…,n},s=1
??輸出：從s到每個頂點的最短路徑
??1.初始S={1}
??2.對于i∈V-S，計算1到i的相對S的最短路，長度dist[i]，沒有路可記為∞或maxint
??3.選擇V-S中dist值最小的j，將j加入S，修改V-S中頂點的dist值
??4.繼續(xù)上述過程，直到S=V為止

??其基本思想是，設(shè)置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。
??初始時，S中僅含有源。設(shè)u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。

??例如，對 右圖中的有向圖，應(yīng)用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中。

??Dijkstra算法的迭代過程：

1.3 算法的正確性和計算復(fù)雜性

??(1)貪心選擇性質(zhì)
??(2)最優(yōu)子結(jié)構(gòu)性質(zhì)
??(3)計算復(fù)雜性
??對于具有n個頂點和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體 需要時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時間。算法的其余部分所需要時間不超過。

1.4 歸納證明思路

??命題：當算法進行到第k步時，對于S中每個結(jié)點i，dist[i]=short[i]
??歸納基礎(chǔ)
??k=1,S={s},dist[s]=short[s]=0
??歸納步驟
??證明：假設(shè)命題對k為真，則對k+1命題也為真

1.5 歸納步驟證明

??假設(shè)命題對k為真，考慮k+1步算法選擇頂點v（邊<u,v>）。需要證明dist[v]=short[v]
若存在另一條s-v路徑L，最后一次出S的頂點為x，經(jīng)過V-s的第一個頂點y，再由y經(jīng)過一段在V-S中的路徑到達v

二、最小生成樹

??設(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)濟的方案。

2.1 最小生成樹性質(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?V-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。

2.1.1 生成樹的性質(zhì)

??設(shè)G是n階連通圖，那么
??T是G的生成樹，當且僅當T無圈且有n-1條邊。
??如果T是G的生成樹，e不屬于T那么T∪{e}含有一個圈C（回路）。
??去掉圈C的任意一條邊，就得到G的另一棵生成樹T’。

2.1.2 生成樹性質(zhì)的應(yīng)用

??算法步驟：選擇邊
??約束條件：不形成回路
??截止條件：邊數(shù)達到n-1
??改進生成樹T的方法：
??在T中加一條非樹邊e，形成回路C，在C中去掉一條樹邊ei，形成一顆新的生成樹T’
??W(T’)-W(T)=W(e)-W(ei)
??若W(e)<=W(ei)，則 W(T’)<=W(T)

2.2 Prim算法

??設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。
??構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件i?S，j?V-S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。
??在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。

??利用最小生成樹性質(zhì)和數(shù)學歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹中的邊。因此，在算法結(jié)束時，T中的所有邊構(gòu)成G的一棵最小生成樹。
??例如，對于右圖中的帶權(quán)圖，按Prim算法選取邊的過程如下頁圖所示。

2.2.1 正確性證明

??命題：對于任意k<n，存在一棵最小生成樹包含算法前k步選擇的邊。
??歸納基礎(chǔ)：k=1，存在一棵最小生成樹T包含邊e={1,i}，其中 {1,i}是所有關(guān)聯(lián)1的邊中權(quán)最小的。
??歸納步驟：假設(shè)算法前k步選擇的邊構(gòu)成一棵最小生成樹的邊，則算法前k+1步選擇的邊也構(gòu)成一棵最小生成樹的邊。

2.2.2 歸納基礎(chǔ)

??證明：存在一棵最小生成樹T包含關(guān)聯(lián)結(jié)點1的最小權(quán)的邊e={1,i}
??證：設(shè)T為一棵最小生成樹，假設(shè)T不包含{1,i}，則T∪ {1,i}含有一條回路，回路中關(guān)聯(lián)1的另一條邊{1,j}。用{1,i} 替換{1,j}得到樹T’，則T’也是生成樹，且W(T’)<=W(T)

2.2.3 歸納步驟

??假設(shè)算法進行了k步，生成樹的邊為e1,e2,…ek，這些邊的端點構(gòu)成集合S。由歸納假設(shè)存在G的一棵最小生成樹T包含這些邊
??算法第k+1步選擇頂點ik+1，則ik+1到S中頂點邊權(quán)最小，設(shè)此邊ek+1={ik+1,il}，若ek+1∈T，算法k+1步顯然正確

??假設(shè)T不含有ek+1，則將ek+1加到T中形成一條回路。這條回路有另外一條中頂點的邊e連接S與V-S中頂點的邊e，
??令T*=(T-{e})∪{ek+1}則T是G的一棵生成樹，包含e1,e2,…ek+1，且W(T)<=W(T)算法到k+1步仍得到最小生成樹

??在上述Prim算法中，還應(yīng)當考慮如何有效地找出滿足條件i?S,j?V-S，且權(quán)c最小的邊(i,j)。實現(xiàn)這個目的的較簡單的辦法是設(shè)置2個數(shù)組closest和lowcost。
??在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，最后將j添加到S中，并對closest和lowcost作必要的修改。
用這個辦法實現(xiàn)的Prim算法所需的計算時間為。

2.3 Kruskal算法

??Kruskal算法構(gòu)造G的最小生成樹的基本思想是，首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止。
??例如，對前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。

??命題：對于任意n，算法對n階圖找到一棵最小生成樹。

2.3.1 證明思路

??歸納基礎(chǔ) 證明：n=2，算法正確。G只有一條邊，最小生成樹就是G
??歸納步驟 證明：假設(shè)算法對于n階圖是正確的，其中n>1，則對于任何n+1階圖算法也得到一棵最小生成樹
??短接操作：任意給n+1個頂點的圖G，G中最小邊的權(quán)e={i,j}，從G中合并i和j，得到圖G’

2.3.2 歸納步驟證明

??對于任意n+1階圖G短接最短邊e，得到n階圖G’
??根據(jù)歸納假設(shè)算法得到G’的最小生成樹T’
??將被短接的邊e“拉伸”回到原來長度，得到樹T
??證明T是G的最小生成樹

2.3.3 T是G的最小生成樹

??T=T’∪{e}是關(guān)于G的最小生成樹
??否則存在G的含邊e的最小生成樹
??T*，W(T*)<W(T)。（如果e不屬于T*，在T中加邊e，形成回路。去掉回路中任意別的邊??所得生成樹的權(quán)仍舊最?。┰赥短接e得到G’的生成樹T*-{e}，
??W(T*-{e})=W(T*)-w(e)<W(T)-w(e)=W(T’)，與T’的最優(yōu)性矛盾

??關(guān)于集合的一些基本運算可用于實現(xiàn)Kruskal算法。
??按權(quán)的遞增順序查看等價于對優(yōu)先隊列執(zhí)行removeMin運算。可以用堆實現(xiàn)這個優(yōu)先隊列。
??對一個由連通分支組成的集合不斷進行修改，需要用到抽象數(shù)據(jù)類型并查集UnionFind所支持的基本運算。
??當圖的邊數(shù)為e時，Kruskal算法所需的計算時間是： 。當 時，Kruskal算法比Prim算法差，但當 時，Kruskal算法卻比Prim算法好得多。

2.4 應(yīng)用：數(shù)據(jù)分組問題

??一組數(shù)據(jù)（照片、文件等）要把它們按照相關(guān)性進行分類
??用相似度函數(shù)或者“距離”來描述個體之間的差異
??分成幾類？使得每類內(nèi)部的個體盡可能相近，不同類之間的個體盡可能地“遠離”。如何劃分？

2.5 單鏈聚類

??類似于Kruskal算法。
??按照邊長從小到大對邊排序
??依次考察當前最短邊e，如果e與已經(jīng)選中的邊不構(gòu)成回路，則把e加入集合，否則跳過e。記數(shù)圖的連通分支個數(shù)
??直到保留了k個連通分支為止

三、多機調(diào)度問題

??多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。
??約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。
這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時可以設(shè)計出較好的近似算法。
采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計出解多機調(diào)度問題的較好的近似算法。
??按此策略，當 時，只要將機器i的[0, ti]時間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時間。
??當 時，首先將n個作業(yè)依其所需的處理時間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機。算法所需的計算時間為O(nlogn)。

??例如，設(shè)7個獨立作業(yè){1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時間為17。

四、小結(jié)

??貪心算法 通常用來求最優(yōu)解
??總是在當前情況下選擇局部最優(yōu)解，依次進行下去得到整體最優(yōu)解。
??當前最佳選擇通常是很容易找到的
??貪心算法必須進行正確性證明，一般使用數(shù)學歸納法
??第一步是顯然的
??歸納步驟通常使用反證法證明，舉反例證偽。文章來源地址http://www.zghlxwxcb.cn/news/detail-714692.html

到了這里，關(guān)于【算法分析與設(shè)計】貪心算法（下）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！