發(fā)布時(shí)間：2021-05-01 03:10

　　網(wǎng)絡(luò)最大流問題是經(jīng)典的組合優(yōu)化問題,為了降低求解大規(guī)模網(wǎng)絡(luò)最大流的計(jì)算量,若用Ford-Fulkerson算法尋找增廣鏈,則效率不高且步驟繁雜。為了改善以上不足,在原有算法的基礎(chǔ)上作了一些改進(jìn),應(yīng)用圖的寬度優(yōu)先搜索原理,針對(duì)單源單匯網(wǎng)絡(luò)提出了一種新的求解最大流問題的算法。該算法的思想是:用寬度優(yōu)先搜索原理,尋找一條包含剩余容量最大的弧的最短增廣鏈后,刪除飽和弧,且沿合適的路徑修復(fù)包含剩余容量最大的弧的最短增廣鏈。該算法避免了Ford-Fulkerson算法的標(biāo)號(hào)過程,減少了反復(fù)重新尋找增廣鏈的次數(shù),為在大規(guī)模網(wǎng)絡(luò)中快速獲取最大流的求解提供了方便并提高了求解網(wǎng)絡(luò)最大流的執(zhí)行效率。通過實(shí)例分析與BA無標(biāo)度網(wǎng)絡(luò)建模仿真,驗(yàn)證了該算法的實(shí)用性,且新算法的運(yùn)行效率高于Ford-Fulkerson算法。 

【文章來源】：計(jì)算機(jī)技術(shù)與發(fā)展. 2019,29(06)

【文章頁數(shù)】：4 頁

【文章目錄】：
0 引 言
1 基本概念
    1.1 最大流的模型
    1.2 剩余網(wǎng)絡(luò) (增量網(wǎng)絡(luò))
2 一種改進(jìn)的最大流算法
    2.1 算法思想
    2.2 算法步驟
    2.3 算法可行性分析
    2.4 算法復(fù)雜度分析
3 數(shù)值實(shí)例與分析
4 算法的仿真與比較
5 結(jié)束語


【參考文獻(xiàn)】：
期刊論文
[1]基于最短增廣鏈的最大流改進(jìn)算法[J]. 趙禮峰,紀(jì)亞勁.  計(jì)算機(jī)技術(shù)與發(fā)展. 2017(08)
[2]動(dòng)態(tài)網(wǎng)絡(luò)中最大流快速增量求解[J]. 張柏禮,王媛瑗,洪亮,田偉,呂建華.  東南大學(xué)學(xué)報(bào)(自然科學(xué)版). 2017(03)
[3]定流值比例的最小雙費(fèi)用流算法研究[J]. 趙禮峰,劉艷清.  計(jì)算機(jī)技術(shù)與發(fā)展. 2017(04)
[4]最大流最小截問題的遺傳算法研究[J]. 趙禮峰,紀(jì)亞寶.  計(jì)算機(jī)技術(shù)與發(fā)展. 2017(04)
[5]最大流問題的改進(jìn)最短增廣鏈算法[J]. 趙禮峰,紀(jì)亞寶.  計(jì)算機(jī)技術(shù)與發(fā)展. 2016(08)
[6]基于增廣鏈修復(fù)的最大流求解算法[J]. 趙禮峰,嚴(yán)子恒.  計(jì)算機(jī)應(yīng)用. 2015(05)
[7]容差修正網(wǎng)絡(luò)最大流2F算法[J]. 陳靜,單銳.  長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版). 2008(06)
[8]一個(gè)新的最大流問題增載軌算法[J]. 張憲超,江賀.  小型微型計(jì)算機(jī)系統(tǒng). 2006(09)
[9]求解網(wǎng)絡(luò)最大流問題的一個(gè)算法[J]. 謝凡榮.  運(yùn)籌與管理. 2004(04)
[10]網(wǎng)絡(luò)最大流的"沖塞式"求法[J]. 紀(jì)偉,戴理昱,王永紅.  運(yùn)籌與管理. 2003(03)



本文編號(hào)：3170029