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

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

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

【學位級別】：碩士

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


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

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



本文編號：2907174