最大流問題是圖論中一個重要的基礎性問題,其求解算法在科學和工程領域以及現(xiàn)實生活中都有廣泛的應用,城市交通相關的車流量控制、城市排水管道的最大排水量計算、網(wǎng)絡規(guī)劃、路徑規(guī)劃等重要問題都可以抽象為最大流問題;最大流問題也是計算機視覺、大數(shù)據(jù)以及圖像處理等技術的理論基礎。上述技術目前仍在快速發(fā)展和更新,因此對最大流問題的深入研究有助于促進相關領域的發(fā)展,具有重要的理論意義和實際意義。學術界已提出多種用來解決最大流問題的新算法和新思路,逐步建立了單機求解最大流問題的較為完善的理論體系。雖然現(xiàn)有算法從多個角度求解最大流問題,但在應用到海量圖數(shù)據(jù)處理時仍存在計算結果不準確和求解效率較低等問題。針對這些問題,本文主要研究基于GraphChi框架的大規(guī)模圖最大流加速,并在該并行圖計算框架中嘗試解決圖分割計算復雜度較高,多次計算存在大量冗余工作等關鍵問題。本文主要內容如下:(1)研究面向最大流計算的圖數(shù)據(jù)劃分和覆蓋圖構建方法,利用割點構建覆蓋圖并把原圖拆分成多個子圖,將割點映射到覆蓋圖并把其余頂點放入不同的子圖。在美國路網(wǎng)等經(jīng)典數(shù)據(jù)集上的測試結果表明,該算法將頂點數(shù)量縮減到了原圖的0.97%^6...

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

【學位級別】：碩士

【文章目錄】：
摘要
abstract
第一章 緒論
    1.1 研究背景及意義
    1.2 研究現(xiàn)狀
    1.3 主要創(chuàng)新點
    1.4 章節(jié)安排
第二章 最大流問題的相關理論和算法
    2.1 最大流問題模型
        2.1.1 圖的定義及相關概念
        2.1.2 最大流理論模型
        2.1.3 BDT理論模型
        2.1.4 基于BDT的查詢優(yōu)化
    2.2 增廣路徑算法
    2.3 預流推進算法
    2.4 本章小結
第三章 覆蓋圖構建算法
    3.1 圖數(shù)據(jù)劃分方法
    3.2 覆蓋圖構建算法
        3.2.1 算法思想
        3.2.2 算法步驟
    3.3 實例分析
    3.4 實驗結果與分析
    3.5 本章小結
第四章 最大流并行加速算法
    4.1 最大流問題回顧及限制條件
    4.2 查找路徑算法
    4.3 并行計算最大流
    4.4 實驗結果與分析
    4.5 本章小結
第五章 基于Graph Chi框架加速計算
    5.1 Graph Chi框架簡介
    5.2 并行滑動窗口機制
        5.2.1 磁盤加載機制
        5.2.2 并行更新機制
        5.2.3 數(shù)據(jù)持久化機制
    5.3 基于框架的多子圖計算
    5.4 實驗結果與分析
        5.4.1 基于框架加速構建覆蓋圖實驗
        5.4.2 基于框架并行計算多子圖最大流實驗
        5.4.3 本文算法與經(jīng)典算法的對比實驗
    5.5 本章小結
第六章 總結與展望
    6.1 總結
    6.2 展望
參考文獻
致謝
個人簡歷、攻讀碩士學位期間取得的學術成果



本文編號：3970816