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

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

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

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


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



本文編號：3170029