最大流問題是一種組合最優(yōu)化的經(jīng)典問題,緊連運(yùn)籌學(xué)和網(wǎng)絡(luò)流理論,常應(yīng)用在現(xiàn)實(shí)場景中的復(fù)雜問題求解,為決策人員提供關(guān)于調(diào)度資源以及合理決策的數(shù)學(xué)依據(jù),在科學(xué)與工程領(lǐng)域具有廣泛的應(yīng)用。大數(shù)據(jù)時代下的計(jì)算機(jī)以及網(wǎng)絡(luò)規(guī)模都在飛速發(fā)展,雖然最大流問題有幾十年的研究歷史,但人們需要智能高效的方式去處理海量數(shù)據(jù),在這個背景下使用經(jīng)典算法計(jì)算大規(guī)模網(wǎng)絡(luò)最大流變得困難。同時,隨著計(jì)算機(jī)網(wǎng)絡(luò)流量巨幅增加,網(wǎng)絡(luò)擁塞的隱患尤為顯著,最小割集是最終決定網(wǎng)絡(luò)承載量的邊集,也是影響網(wǎng)絡(luò)通行能力上限的特殊位置,因此,最小割集的求解在具體應(yīng)用下也有著重要意義。依據(jù)面對大量復(fù)雜信息人類智能能夠把復(fù)雜的問題簡單化、抽象化、在不同角度進(jìn)行轉(zhuǎn)換的特點(diǎn),商空間理論能夠模擬人類思考特點(diǎn)將復(fù)雜問題轉(zhuǎn)化到不同空間上進(jìn)行描述分析,有效地簡小問題規(guī)模,提高求解效率。因此,本文提出將商空間理論應(yīng)用到最大流以及最小割集的求解中,以簡化問題規(guī)模,加快求解速度。本文的研究重點(diǎn)在于,如何結(jié)合商空間理論(Quotient Space理論)將粒度較細(xì)的大規(guī)模復(fù)雜網(wǎng)絡(luò)依據(jù)其結(jié)構(gòu)信息構(gòu)建粒度較粗的小規(guī)模網(wǎng)絡(luò),并在粗粒度的小規(guī)模網(wǎng)絡(luò)上近似求解大規(guī)模網(wǎng)絡(luò)的最大流... 

【文章來源】：安徽大學(xué)安徽省 211工程院校

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

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景及意義
    1.2 國內(nèi)外相關(guān)研究現(xiàn)狀
    1.3 本文主要工作和組織結(jié)構(gòu)
第二章 基本概念、理論知識及算法
    2.1 網(wǎng)絡(luò)流的基本理論
        2.1.1 圖與網(wǎng)絡(luò)
        2.1.2 網(wǎng)絡(luò)流的主要概念
    2.2 最大流/最小割的基本概念
        2.2.1 最大流問題定義
        2.2.2 最大流與最小割
        2.2.3 增廣路
    2.3 本文相關(guān)算法描述及分析
        2.3.1 Ford-Fulkerson算法
        2.3.2 Dinic算法
        2.3.3 Improved SAP算法
        2.3.4 基于F-F標(biāo)記法求最小割
        2.3.5 標(biāo)簽傳播算法
    2.4 商空間理論概述
    2.5 本章小結(jié)
第三章 基于商空間模型和標(biāo)簽傳播的最大流求解算法
    3.1 基本定義和概念
    3.2 基于標(biāo)簽傳播快速求解最大流的MFLPA算法
        3.2.1 MFLPA算法框架
        3.2.2 MFLPA算法詳述
    3.3 實(shí)驗(yàn)結(jié)果與分析
        3.3.1 實(shí)驗(yàn)設(shè)置與數(shù)據(jù)來源
        3.3.2 實(shí)驗(yàn)結(jié)果
    3.4 本章小結(jié)
第四章 基于商空間模型和增廣標(biāo)記的最小割求解算法
    4.1 基本定義和概念
    4.2 DSM算法
        4.2.1 DSM算法思想
        4.2.2 DSM算法詳述
    4.3 實(shí)驗(yàn)結(jié)果與分析
        4.3.1 實(shí)驗(yàn)設(shè)置與數(shù)據(jù)來源
        4.3.2 實(shí)驗(yàn)結(jié)果
    4.4 本章小結(jié)
第五章 總結(jié)與展望
    5.1 本文總結(jié)
    5.2 未來展望
參考文獻(xiàn)
附錄A 圖索引
Appendix A Figure Index
附錄B 表索引
Appendix B Table Index
致謝
攻讀碩士學(xué)位期間參與的科研項(xiàng)目與論文


【參考文獻(xiàn)】：
期刊論文
[1]幾類求解最大流問題算法在運(yùn)輸問題中的應(yīng)用[J]. 郭鑫龍.  電子制作. 2015(18)
[2]基于粒計(jì)算的大數(shù)據(jù)處理[J]. 徐計(jì),王國胤,于洪.  計(jì)算機(jī)學(xué)報. 2015(08)
[3]分層法求解網(wǎng)絡(luò)最大流的研究[J]. 趙姝,蘇建忠,劉倩倩,張燕平.  計(jì)算機(jī)研究與發(fā)展. 2014(08)
[4]網(wǎng)絡(luò)分析中求最大流的商空間方法[J]. 鄭誠,張鈴.  計(jì)算機(jī)學(xué)報. 2015(08)
[5]收縮鄰居節(jié)點(diǎn)集方法求解有向網(wǎng)絡(luò)的最大流問題[J]. 趙姝,許顯勝,華波,張燕平.  模式識別與人工智能. 2013(05)
[6]復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展[J]. 駱志剛,丁凡,蔣曉舟,石金龍.  國防科技大學(xué)學(xué)報. 2011(01)
[7]運(yùn)輸問題國內(nèi)外研究評述[J]. 王有鴻,費(fèi)威.  商業(yè)時代. 2010(24)
[8]復(fù)雜系統(tǒng)層次的內(nèi)涵及相互關(guān)系原理研究[J]. 顧文濤,王以華,吳金希.  系統(tǒng)科學(xué)學(xué)報. 2008(02)
[9]人工智能的歷史與未來[J]. 劉毅.  科技管理研究. 2004(06)
[10]一個科學(xué)新領(lǐng)域——開放的復(fù)雜巨系統(tǒng)及其方法論[J]. 錢學(xué)森,于景元,戴汝為.  自然雜志. 1990(01)

碩士論文
[1]網(wǎng)絡(luò)流算法的研究與應(yīng)用分析[D]. 董方.南京郵電大學(xué) 2014
[2]基于BSP模型的網(wǎng)絡(luò)最大流算法的并行化研究與實(shí)現(xiàn)[D]. 趙正委.電子科技大學(xué) 2014
[3]基于圖論的圖像分割技術(shù)研究[D]. 羅青青.南京郵電大學(xué) 2014
[4]最大流算法與應(yīng)用研究[D]. 陶曉莉.南京郵電大學(xué) 2014
[5]網(wǎng)絡(luò)優(yōu)化算法及其應(yīng)用[D]. 程鳳敏.西安電子科技大學(xué) 2013
[6]最大流及最小費(fèi)用的算法研究[D]. 白睿.南京郵電大學(xué) 2012
[7]計(jì)算運(yùn)籌學(xué)在經(jīng)濟(jì)管理領(lǐng)域的應(yīng)用[D]. 何明華.電子科技大學(xué) 2008
[8]帶容量限制的運(yùn)輸問題研究[D]. 董鵬.華中科技大學(xué) 2005



本文編號：2907174