圖論中貪心算法的應(yīng)用

楊迪

【摘要】 在對(duì)一些圖論問(wèn)題求解中，應(yīng)用貪心算法能夠快速地、準(zhǔn)確地求解，受到了很多工作者的肯定和使用.本文簡(jiǎn)單地介紹貪心算法解題思想，并在兩個(gè)典型實(shí)例的分析下，闡明了圖論中心貪心算法的實(shí)際運(yùn)用.

【關(guān)鍵詞】 圖論；貪心算法；應(yīng)用

在求解一些問(wèn)題中，貪心算法作為一種優(yōu)解的有效算法，能夠快速地、有效地解決很多實(shí)際存在的問(wèn)題，被廣泛運(yùn)用在圖論領(lǐng)域中.雖然貪心算法也有不足之處，如應(yīng)用范疇比較狹窄，但對(duì)于圖論有些問(wèn)題，貪心算法既可以正確求解，也有著很高的應(yīng)用價(jià)值.

一、概述貪心算法

貪心算法是一種分級(jí)處理方法，在決策中，貪心算法總會(huì)對(duì)當(dāng)前情況進(jìn)行最好的選擇.與動(dòng)態(tài)規(guī)劃算法不同的是，貪心算法并不考慮問(wèn)題的整體最優(yōu)，而只是考慮某種意義上的局部最優(yōu).因此，貪心算法并未結(jié)合所有問(wèn)題求得整體最優(yōu)解，但對(duì)于一些問(wèn)題來(lái)講，它可以求得整體最優(yōu)解.在一些狀況下，雖然貪心算法并未得到整體最優(yōu)解，但是能夠得到與最優(yōu)解的近似，所以，貪心算法有著很高的應(yīng)用價(jià)值.

二、貪心算法的求解步驟

1.基本要素.對(duì)于一個(gè)切實(shí)存在的問(wèn)題，怎樣才能知道是否能夠用貪心算法求解并得到最優(yōu)解，在具體應(yīng)用過(guò)程中，人們研究和總結(jié)出兩個(gè)重要性質(zhì)：一是，貪心選擇的性質(zhì)；二是，最優(yōu)子結(jié)構(gòu)的性質(zhì).很多使用貪心方法求解問(wèn)題中都會(huì)具有這兩個(gè)性質(zhì).

2.步驟的求解.貪心算法的求解先要明確出一個(gè)貪心準(zhǔn)則，每步都按照此準(zhǔn)則進(jìn)行方案優(yōu)化.排序各個(gè)問(wèn)題，排一次輸一個(gè)量.假若這個(gè)輸入與已構(gòu)成的量最優(yōu)解加在一起后很難出現(xiàn)可行解，這樣就不能將輸入值與這部分解相融合.

三、使用貪心算法對(duì)單源點(diǎn)最短路徑求解的可行性

在圖論中存在一個(gè)很典型的問(wèn)題：?jiǎn)卧袋c(diǎn)最短路徑這一問(wèn)題.對(duì)問(wèn)題的描述如下：對(duì)于有向帶權(quán)圖G=（V，E），其每條邊上的權(quán)重都是非負(fù)實(shí)數(shù).選定在V中某個(gè)頂點(diǎn)，稱為源點(diǎn).此問(wèn)題求解的是從源點(diǎn)到圖G中其各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度.在這里所講的長(zhǎng)度就是指通過(guò)各個(gè)邊的權(quán)值總和.Dijkstra正是運(yùn)用貪心算法求解這個(gè)問(wèn)題，用所有路徑長(zhǎng)度之和作為最小貪心準(zhǔn)則，所以，每個(gè)單獨(dú)路徑都要有最小長(zhǎng)度.實(shí)現(xiàn)此算法步驟是：將頂點(diǎn)集合分為兩個(gè)子集，即：S，V-S.在子集S中將所有最短路徑頂點(diǎn)都已求得.在初始時(shí)，集合S中有源點(diǎn)，然后，將其做貪心來(lái)擴(kuò)充此集合.選取在G中頂點(diǎn)V，從源點(diǎn)到V點(diǎn)并通過(guò)S中頂點(diǎn)的路徑稱之為源點(diǎn)到頂點(diǎn)V的特殊路徑，設(shè)置數(shù)組Dirt記錄各個(gè)頂點(diǎn)對(duì)應(yīng)的最短特殊路徑長(zhǎng)度.

四、應(yīng)用貪心算法求解最小生成樹的可行性

（一）Kruskal算法的應(yīng)用

對(duì)于最小生成樹圖論的討論是非常有價(jià)值和有意義的，具體描述包括如下幾點(diǎn)：已知無(wú)項(xiàng)連通帶權(quán)圖 G=（V，E）.E中每條邊（u，v）的權(quán)值設(shè)為c[u][v].求圖G的生成樹G′，使G′上各邊權(quán)值的總和是所有生成樹中各邊權(quán)值中總和最小.此問(wèn)題被稱為最小生成樹問(wèn)題.求解最小生成樹問(wèn)題有很 多種方法，其中Kruskal、Prim等算法應(yīng)用最為廣泛.

Kruskal算法與Prim算法相比，在生成最小生成樹中，前者比后者更加簡(jiǎn)潔明了.一是將無(wú)向連通帶權(quán)圖 G的n個(gè)頂點(diǎn)視為n個(gè) 獨(dú)立的分支，但這幾個(gè)分支間是互相連通的.并根據(jù)權(quán)值給各個(gè)邊從小至大展開排序.將第一條邊與連通分支進(jìn)行相連，之后按照權(quán)值遞增順序檢查剩下的各個(gè)邊，若加入此邊就構(gòu)成回路，就拋棄此邊，然后，考察余下每條邊；反之，加入此邊并不會(huì)構(gòu)成回路，就將此邊加入.

（二）Prim算法的應(yīng)用

Prim算法思想是：一是在圖中選取一個(gè)頂點(diǎn)u，將u置于頂點(diǎn)集合子集S里.若S是頂點(diǎn)集合V的真子集，就應(yīng)該將頂點(diǎn)加入子集S中，但要滿足iI ^ S，jI ^ V-S條件，并且C[i][j]是權(quán)值最小的一個(gè)邊.根據(jù)同樣的步驟進(jìn)行貪心選擇，直至子集S=V結(jié)束.在這時(shí)，已被選取的邊就構(gòu)成了在圖G中的一顆小生成樹.

在對(duì)比上文兩種方法后才發(fā)現(xiàn)，這兩種方法雖然都是使用貪心算法解決問(wèn)題，但由于貪心準(zhǔn)則不同的影響，最小生成樹選邊與求解步驟也是不同的，所以，在實(shí)際應(yīng)用貪心算法中，需要因地制宜地應(yīng)用，盲目、一味地應(yīng)用貪心算法，很容易引發(fā)其他方面的問(wèn)題，但相對(duì)而言，貪心算法還是值得大范圍地應(yīng)用的.

五、結(jié) 語(yǔ)

總而言之，圖論中還有一些問(wèn)題很難解決，貪心算法是否能夠解決這些問(wèn)題，還需要深入地探討和研究.同時(shí)，想要在圖論中充分應(yīng)用貪心算法，這就需要有關(guān)工作者必須要全面掌握和了解貪心算法，能夠熟練、準(zhǔn)確地應(yīng)用，確保貪心算法能夠發(fā)揮作用，解決好圖論中一些疑難問(wèn)題.