楊迪
【摘要】 在對(duì)一些圖論問題求解中,應(yīng)用貪心算法能夠快速地、準(zhǔn)確地求解,受到了很多工作者的肯定和使用.本文簡(jiǎn)單地介紹貪心算法解題思想,并在兩個(gè)典型實(shí)例的分析下,闡明了圖論中心貪心算法的實(shí)際運(yùn)用.
【關(guān)鍵詞】 圖論;貪心算法;應(yīng)用
在求解一些問題中,貪心算法作為一種優(yōu)解的有效算法,能夠快速地、有效地解決很多實(shí)際存在的問題,被廣泛運(yùn)用在圖論領(lǐng)域中.雖然貪心算法也有不足之處,如應(yīng)用范疇比較狹窄,但對(duì)于圖論有些問題,貪心算法既可以正確求解,也有著很高的應(yīng)用價(jià)值.
一、概述貪心算法
貪心算法是一種分級(jí)處理方法,在決策中,貪心算法總會(huì)對(duì)當(dāng)前情況進(jìn)行最好的選擇.與動(dòng)態(tài)規(guī)劃算法不同的是,貪心算法并不考慮問題的整體最優(yōu),而只是考慮某種意義上的局部最優(yōu).因此,貪心算法并未結(jié)合所有問題求得整體最優(yōu)解,但對(duì)于一些問題來講,它可以求得整體最優(yōu)解.在一些狀況下,雖然貪心算法并未得到整體最優(yōu)解,但是能夠得到與最優(yōu)解的近似,所以,貪心算法有著很高的應(yīng)用價(jià)值.
二、貪心算法的求解步驟
1.基本要素.對(duì)于一個(gè)切實(shí)存在的問題,怎樣才能知道是否能夠用貪心算法求解并得到最優(yōu)解,在具體應(yīng)用過程中,人們研究和總結(jié)出兩個(gè)重要性質(zhì):一是,貪心選擇的性質(zhì);二是,最優(yōu)子結(jié)構(gòu)的性質(zhì).很多使用貪心方法求解問題中都會(huì)具有這兩個(gè)性質(zhì).
2.步驟的求解.貪心算法的求解先要明確出一個(gè)貪心準(zhǔn)則,每步都按照此準(zhǔn)則進(jìn)行方案優(yōu)化.排序各個(gè)問題,排一次輸一個(gè)量.假若這個(gè)輸入與已構(gòu)成的量最優(yōu)解加在一起后很難出現(xiàn)可行解,這樣就不能將輸入值與這部分解相融合.
三、使用貪心算法對(duì)單源點(diǎn)最短路徑求解的可行性
在圖論中存在一個(gè)很典型的問題:?jiǎn)卧袋c(diǎn)最短路徑這一問題.對(duì)問題的描述如下:對(duì)于有向帶權(quán)圖G=(V,E),其每條邊上的權(quán)重都是非負(fù)實(shí)數(shù).選定在V中某個(gè)頂點(diǎn),稱為源點(diǎn).此問題求解的是從源點(diǎn)到圖G中其各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度.在這里所講的長(zhǎng)度就是指通過各個(gè)邊的權(quán)值總和.Dijkstra正是運(yùn)用貪心算法求解這個(gè)問題,用所有路徑長(zhǎng)度之和作為最小貪心準(zhǔn)則,所以,每個(gè)單獨(dú)路徑都要有最小長(zhǎng)度.實(shí)現(xiàn)此算法步驟是:將頂點(diǎn)集合分為兩個(gè)子集,即:S,V-S.在子集S中將所有最短路徑頂點(diǎn)都已求得.在初始時(shí),集合S中有源點(diǎn),然后,將其做貪心來擴(kuò)充此集合.選取在G中頂點(diǎn)V,從源點(diǎn)到V點(diǎn)并通過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):已知無項(xiàng)連通帶權(quán)圖 G=(V,E).E中每條邊(u,v)的權(quán)值設(shè)為c[u][v].求圖G的生成樹G′,使G′上各邊權(quán)值的總和是所有生成樹中各邊權(quán)值中總和最小.此問題被稱為最小生成樹問題.求解最小生成樹問題有很 多種方法,其中Kruskal、Prim等算法應(yīng)用最為廣泛.
Kruskal算法與Prim算法相比,在生成最小生成樹中,前者比后者更加簡(jiǎn)潔明了.一是將無向連通帶權(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),這兩種方法雖然都是使用貪心算法解決問題,但由于貪心準(zhǔn)則不同的影響,最小生成樹選邊與求解步驟也是不同的,所以,在實(shí)際應(yīng)用貪心算法中,需要因地制宜地應(yīng)用,盲目、一味地應(yīng)用貪心算法,很容易引發(fā)其他方面的問題,但相對(duì)而言,貪心算法還是值得大范圍地應(yīng)用的.
五、結(jié) 語
總而言之,圖論中還有一些問題很難解決,貪心算法是否能夠解決這些問題,還需要深入地探討和研究.同時(shí),想要在圖論中充分應(yīng)用貪心算法,這就需要有關(guān)工作者必須要全面掌握和了解貪心算法,能夠熟練、準(zhǔn)確地應(yīng)用,確保貪心算法能夠發(fā)揮作用,解決好圖論中一些疑難問題.
數(shù)學(xué)學(xué)習(xí)與研究2017年5期