摘 要：本文介紹了貪心算法的基本概念和解題思想，并通過兩個(gè)典型的實(shí)例，說明了在圖論中貪心算法的具體的應(yīng)用。

關(guān)鍵詞：貪心算法；最優(yōu)子結(jié)構(gòu)性質(zhì)；貪心準(zhǔn)則

中圖分類號(hào)：TP18

貪心算法是用來求解某些問題最優(yōu)解的一種有效算法，它可以簡單迅速的解決很多實(shí)際應(yīng)用的問題，在圖論領(lǐng)域也有著非常廣泛的應(yīng)用。

1 貪心算法概述

1.1 貪心算法定義

貪心算法是一種經(jīng)過改進(jìn)的分級(jí)處理的方法。貪心算法在進(jìn)行決策的時(shí)候總會(huì)做出對目前情況最好的選擇。和動(dòng)態(tài)規(guī)劃算法不同的是，貪心算法并不考慮問題的整體最優(yōu)，而只是選擇某種意義上的局部最優(yōu)。所以，貪心方法未必能針對所有問題求得整體的最優(yōu)解，但是對于許多問題而言，它卻能得到整體最優(yōu)解。在某些情況下，貪心算法雖然得不到整體最優(yōu)解，卻可以得到最優(yōu)解的很好的近似。

1.2 貪心算法的基本要素

對于一個(gè)具體問題，怎樣才能知道能否可以用貪心算法求解并得到最優(yōu)解呢？在實(shí)際應(yīng)用中人們總結(jié)出了兩個(gè)重要的性質(zhì)：

（1）貪心選擇性質(zhì)；（2）最優(yōu)子結(jié)構(gòu)性質(zhì)。

許多可以利用貪心方法求解的問題一般都具備這兩個(gè)性質(zhì)。

1.3 貪心算法的求解步驟

貪心算法求解問題首先要確定一個(gè)貪心準(zhǔn)則，每一步都是按這個(gè)準(zhǔn)則選取優(yōu)化方案。按照這種度量標(biāo)準(zhǔn)對此問題的n個(gè)輸入排序，并按序一次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中。因此貪心準(zhǔn)則的選取直接關(guān)系到可行解能否達(dá)到最優(yōu)。

2 貪心算法求解單源點(diǎn)最短路徑問題

圖論中有一個(gè)非常典型的問題：單源點(diǎn)最短路徑問題。問題描述如下：對于有向帶權(quán)圖G =（V，E），其中每條邊上的權(quán)值是一個(gè)非負(fù)實(shí)數(shù)。選定V中的一個(gè)頂點(diǎn)，稱之為源點(diǎn)。這個(gè)問題求解的是從源點(diǎn)到圖G中其他所有頂點(diǎn)的最短路徑的長度。所謂的長度是指經(jīng)過的各邊上的權(quán)值總和。

Dijkstra算法正是利用貪心算法求解此問題，用迄今已生成的所有路徑長度之和為最小作為貪心準(zhǔn)則，為此，每一條單獨(dú)的路徑都必須具有最小長度。此算法的實(shí)現(xiàn)步驟為：將頂點(diǎn)集合分為S和V-S這兩個(gè)子集。子集S中均為已求得最短路徑的頂點(diǎn)。初始時(shí)，集合S中只有源點(diǎn)，接下來不斷做貪心選擇來擴(kuò)充此集合。取G中的一個(gè)頂點(diǎn)v，把從源點(diǎn)到v點(diǎn)并且只經(jīng)過S中頂點(diǎn)的路徑稱為從源點(diǎn)到頂點(diǎn)v的特殊路徑，設(shè)置數(shù)組dist記錄每個(gè)頂點(diǎn)當(dāng)前所對應(yīng)的最短特殊路徑的長度。Dijkstra算法每次都從子集V-S中取出特殊路徑長度為最短的頂點(diǎn)，并把該頂點(diǎn)添加至子集S，隨后對數(shù)組dist進(jìn)行修改。一旦子集S等于頂點(diǎn)集V，算法結(jié)束。數(shù)組dist中記錄的就是源點(diǎn)到圖中其他各頂點(diǎn)的最短路徑的長度。

例如，下圖1中的有向帶權(quán)圖，采用Dijkstra算法，從源點(diǎn)1到圖中剩余各頂點(diǎn)間最短路徑的計(jì)算過程如下表1所示：

3 貪心算法求解最小生成樹問題

最小生成樹是非常具有實(shí)際應(yīng)用價(jià)值的圖論問題，具體描述如下：已知無向連通帶權(quán)圖G=（V，E）。E中每條邊（u，v）的權(quán)值設(shè)為c[u][v]。求圖G的生成樹G’，使得G’上各邊權(quán)值的總和是所有生成樹中各邊權(quán)值總和最小的。這個(gè)問題被稱為最小生成樹問題。最小生成樹的求解方法有多種，其中應(yīng)用比較廣泛的幾種算法，如Prim算法和Kruskal算法都是采用了貪心算法的策略。

3.1 Prim算法

Prim算法的基本思想為：首先選擇圖中任意頂點(diǎn)u，并將u置于頂點(diǎn)集合的子集S中。如果S是頂點(diǎn)集合V的真子集，就繼續(xù)選擇頂點(diǎn)j添加到子集S中，這里的j必須滿足條件i?S，j?V-S，且c[i][j]是權(quán)值最小的邊。按照同樣的步驟不斷進(jìn)行貪心選擇，直到子集S=V為止。此時(shí)，選取到的所有的邊就構(gòu)成了圖G的一棵最小生成樹。例如，對于圖2中的無向連通帶權(quán)圖，按照Prim算法求最小生成樹的過程如圖3所示。

3.2 Kruskal算法

Kruskal算法構(gòu)造最小生成樹的過程相比Prim算法更加簡單明了。首先將無向連通帶權(quán)圖G的n個(gè)頂點(diǎn)作為n個(gè)孤立的連通分支。并按照權(quán)值給所有的邊從小到大進(jìn)行排序。將第一條邊加入到連通分支，然后按權(quán)值遞增的順序依次查看剩下的每一條邊，如果這條邊加入構(gòu)成回路就拋棄，繼續(xù)考察下一條邊，反之加入到連通分支中。一旦加入邊的條數(shù)等于n-1，則算法結(jié)束。剩下唯一的連通分支就是要求取的最小生成樹。

例如，對上圖2，按Kruskal算法求得最小生成樹的過程如下圖4所示。

比較上述兩種方法可以看出，雖然都是利用貪心算法解決，但是由于選擇的貪心準(zhǔn)則不一樣，因次求解步驟和最小生成樹的選邊過程都是不一樣的。

4 總結(jié)

貪心算法也存在著缺點(diǎn)，比如應(yīng)用范疇比較狹窄而且有一些極難證明，但是針對圖論的部分問題，比如上述的兩個(gè)典型問題，貪心算法不但能夠正確的求解，而且與其他算法相比，更是體現(xiàn)了其高效的優(yōu)勢。當(dāng)然，圖論中還有許多未解的問題，這些問題能否用貪心算法求解，或者能否找到更好的貪心準(zhǔn)則提高求解的效率則需要更加深入的研究和發(fā)現(xiàn)。

參考文獻(xiàn)：

[1]余祥宣，崔國華，鄒海明.計(jì)算機(jī)算法基礎(chǔ)（第三版）[M].華中科技大學(xué)出版社，2006.

[2]王曉東.算法設(shè)計(jì)與分析（第2版）[M].清華大學(xué)出版社，2008.

[4]楊克昌.計(jì)算機(jī)常用算法與程序設(shè)計(jì)案例教程[M].清華大學(xué)出版社，2011.

[5]王桂平，王衍，任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京大學(xué)出版社，2011.