本文關(guān)鍵詞：分層法求解網(wǎng)絡(luò)最大流的研究　出處：《計算機(jī)研究與發(fā)展》2014年08期 　論文類型：期刊論文

  更多相關(guān)文章： 分層法 最大流 流網(wǎng)絡(luò) 最小割 網(wǎng)絡(luò)分層

【摘要】：網(wǎng)絡(luò)最大流問題是經(jīng)典的組合優(yōu)化問題,隨著網(wǎng)絡(luò)規(guī)模的增加,提高算法效率成為解決問題的關(guān)鍵.為了降低求解大規(guī)模網(wǎng)絡(luò)最大流的計算量,針對單源單匯網(wǎng)絡(luò)提出基于網(wǎng)絡(luò)分層的最大流問題求解新方法.分層法首先構(gòu)造原有向網(wǎng)絡(luò)對應(yīng)的層次網(wǎng)絡(luò),接著在構(gòu)造出的層次網(wǎng)絡(luò)中計算各相鄰結(jié)點(diǎn)層之間的最大流,以此為基礎(chǔ)最終獲得整個網(wǎng)絡(luò)最大流的快速估算.分層法有效降低了計算的復(fù)雜性,為在大規(guī)模網(wǎng)絡(luò)中快速獲取最大流的求解提供了方便,并給出了一個解決最大流問題的新思路.不同網(wǎng)絡(luò)上測試的實(shí)驗(yàn)結(jié)果顯示,最大流的近似解誤差可控制在1%左右,而平均運(yùn)行時間僅為經(jīng)典算法(FordFulkerson算法)運(yùn)行時間的11%,最好情況下的運(yùn)行時間僅為經(jīng)典算法運(yùn)行時間的2%,是two-phase capacity scaling改進(jìn)算法運(yùn)行時間的25%,表明分層方法的有效性.
【作者單位】： 安徽大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院;計算智能與信號處理教育部重點(diǎn)實(shí)驗(yàn)室(安徽大學(xué));
【基金】：國家自然科學(xué)基金項(xiàng)目(61073117,61175046,61203290) 安徽省自然科學(xué)基金項(xiàng)目(11040606M) 安徽大學(xué)2011級研究生學(xué)術(shù)創(chuàng)新研究項(xiàng)目(01001770-10117700163)
【分類號】：TP393.01
【正文快照】： 最大流問題[1]是網(wǎng)絡(luò)流理論的重要組成部分.它是組合優(yōu)化中的經(jīng)典問題,同時也可以看作特殊的線性規(guī)劃問題[2-3].除了解決實(shí)際網(wǎng)絡(luò)中的最大流問題外,最大流算法在許多領(lǐng)域都有廣泛的應(yīng)用[4-6].解決最大流問題的經(jīng)典算法是Ford和Fulkerson提出的增廣路算法[7],隨后許多學(xué)者提出

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 張新猛;蔣盛益;;基于核心圖增量聚類的復(fù)雜網(wǎng)絡(luò)劃分算法[J];自動化學(xué)報;2013年07期

2 黃文良;劉勇;鐘志強(qiáng);沈仲明;;基于復(fù)雜網(wǎng)絡(luò)的垃圾短信過濾算法[J];自動化學(xué)報;2009年07期

3 張憲超;江賀;劉馨月;于紅;;無向平面單位容量網(wǎng)絡(luò)中的最大流[J];計算機(jī)研究與發(fā)展;2008年S1期

4 張憲超 ,陳國良 ,萬穎瑜;網(wǎng)絡(luò)最大流問題研究進(jìn)展[J];計算機(jī)研究與發(fā)展;2003年09期

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 趙禮峰;紀(jì)亞勁;;基于最短增廣鏈的最大流改進(jìn)算法[J];計算機(jī)技術(shù)與發(fā)展;2017年08期

2 胡楊;馮旭鵬;戴丹;劉利軍;黃青松;;最小費(fèi)用最大流跨領(lǐng)域情感分類框架[J];小型微型計算機(jī)系統(tǒng);2017年01期

3 周巧扣;倪紅軍;;一種基于語義的垃圾短信過濾算法[J];實(shí)驗(yàn)室研究與探索;2016年11期

4 林洋;李燕;董瑋;劉延昕;任麗曄;;復(fù)雜網(wǎng)絡(luò)社區(qū)的抽樣概率分布估計檢測算法[J];西南師范大學(xué)學(xué)報(自然科學(xué)版);2016年10期

5 趙禮峰;紀(jì)亞寶;;最大流問題的改進(jìn)最短增廣鏈算法[J];計算機(jī)技術(shù)與發(fā)展;2016年08期

6 梁晉;梁吉業(yè);趙興旺;;一種面向大規(guī)模社會網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法[J];南京大學(xué)學(xué)報(自然科學(xué));2016年01期

7 黃孝鵬;羅軍;鑒福升;;基于多任務(wù)的海上跨平臺自主傳感網(wǎng)最大流改進(jìn)模型及求解[J];兵工學(xué)報;2015年S2期

8 鄧立軍;劉劍;;無回路阻力平衡約束的固定風(fēng)量平衡算法研究[J];安全與環(huán)境學(xué)報;2015年04期

9 孫大鵬;;云計算技術(shù)在垃圾短信過濾中的應(yīng)用與實(shí)現(xiàn)[J];信息網(wǎng)絡(luò)安全;2015年07期

10 郭鑫龍;;幾類求解最大流問題算法在運(yùn)輸問題中的應(yīng)用[J];電子制作;2015年18期

【二級參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 劉旭;易東云;;基于局部相似性的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J];自動化學(xué)報;2011年12期

2 金弟;劉杰;楊博;何東曉;劉大有;;局部搜索與遺傳算法結(jié)合的大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)探測[J];自動化學(xué)報;2011年07期

3 李輝;趙海;徐久強(qiáng);李博;李鵬;王家亮;;基于k-核的大規(guī)模軟件宏觀拓?fù)浣Y(jié)構(gòu)層次性研究[J];電子學(xué)報;2010年11期

4 何東曉;周栩;王佐;周春光;王U，

本文編號：1324690