增廣鏈修復的最大流求解算法
大小：0.58 MB 人氣： 2018-01-10 需要積分：1
標簽：
最大流問題是運籌學中經典問題之一，它可以使用圖的方法進行求解。網絡最大流在計算機、工程學等學科中有著廣泛的用途，例如通信網絡流量分配、交通運輸線路分配等都能轉化為網絡最大流數學模型。最大流的經典算法主要分為增廣鏈法和預流推進法，其中常用的增廣鏈法有Ford-Fulkerson提出的增廣鏈算法、Dinic研究的阻塞流和分層網絡算法、Edmonds等設計的最短路增廣算法、Karzanov改進的先進先出預流推進算法及Cherkassky改進的最高標號預流推進算法。這些經典算法逐漸降低了求解網絡最大流的時間復雜度，是研究大規模網絡的基礎。
經典算法的經典之處在于它的適用面廣，在各類網絡中都能穩定運行且在較短時間內完成求解過程，但在部分特殊網絡如稀疏網絡中，它們的效率不高，因此需針對這些網絡的特點改進或使用新算法提高執行效率，實現其研究價值。
本文針對Newman和Watts提出的NW小世界網絡以及Barabasi和Albert提出的BA無標度網絡兩種現實中常見的網絡提出了一種新算法，這種算法能夠盡可能地避免反復地重新尋找新的增廣鏈，通逋捷徑的方法修復滿足條件的原始增廣鏈，從而縮短了重復計算的時間，提高算法效率。
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%