• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2017-03-29 09:25楊迪
      關(guān)鍵詞:圖論應(yīng)用

      楊迪

      【摘要】 在對(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ā)揮作用,解決好圖論中一些疑難問題.

      猜你喜歡
      圖論應(yīng)用
      基于FSM和圖論的繼電電路仿真算法研究
      構(gòu)造圖論模型解競(jìng)賽題
      代數(shù)圖論與矩陣幾何的問題分析
      點(diǎn)亮兵書——《籌海圖編》《海防圖論》
      多媒體技術(shù)在小學(xué)語文教學(xué)中的應(yīng)用研究
      分析膜技術(shù)及其在電廠水處理中的應(yīng)用
      GM(1,1)白化微分優(yōu)化方程預(yù)測(cè)模型建模過程應(yīng)用分析
      煤礦井下坑道鉆機(jī)人機(jī)工程學(xué)應(yīng)用分析
      氣體分離提純應(yīng)用變壓吸附技術(shù)的分析
      會(huì)計(jì)與統(tǒng)計(jì)的比較研究
      黄陵县| 孙吴县| 肥城市| 武宁县| 舒兰市| 汝阳县| 佛冈县| 稻城县| 海淀区| 鸡西市| 连城县| 潮州市| 电白县| 清远市| 南通市| 灯塔市| 蛟河市| 安康市| 江达县| 阜康市| 卓资县| 常山县| 武川县| 花莲市| 刚察县| 资兴市| 靖江市| 磴口县| 铜梁县| 沁阳市| 湖口县| 奎屯市| 宝应县| 新乐市| 新乡县| 雷州市| 和林格尔县| 承德市| 宣汉县| 无极县| 宁乡县|