發(fā)布時間：2018-11-07 15:01

【摘要】：利用損毀網(wǎng)絡(luò)與原網(wǎng)絡(luò)的結(jié)構(gòu)包含性,提出了一種基于增廣路徑選擇樹的最大流增量算法MFIA-ART.算法在原網(wǎng)絡(luò)最大流的求解過程中,對簡單路徑集等相關(guān)的中間結(jié)果給予緩存,構(gòu)成增廣路徑候選集,當(dāng)網(wǎng)絡(luò)拓?fù)涓淖儠r直接在其中查找有效的增廣路徑,無需對新的殘余網(wǎng)絡(luò)進行復(fù)雜計算.同時為了避免遍歷包含飽和邊的簡單路徑,進一步利用增廣路徑選擇樹ART來組織所有可能的增廣路徑集,從而可以通過一條從根節(jié)點到某個葉節(jié)點的路徑找到所有需要的增廣路徑,獲得最大流量.其遍歷的深度為ART樹的高度H,遠(yuǎn)小于所有增廣路徑的數(shù)量,因而顯著地提高了求解最大流的效率.實驗結(jié)果表明,MFIA-ART相對于采用經(jīng)典的Dinic算法重新計算最大流的方法,在時間性能方面有數(shù)量級的提高,尤其適合應(yīng)用于簡單路徑數(shù)量較少的稀疏性網(wǎng)絡(luò).
[Abstract]:Taking advantage of the structural inclusiveness of the damaged network and the original network, a maximum flow increment algorithm (MFIA-ART.) based on the augmented path selection tree is proposed. In the process of solving the maximum flow of the original network, the algorithm caches the relevant intermediate results such as simple path set, which forms an augmented path candidate set. When the network topology changes, it directly finds the valid augmented path. There is no need for complex calculations of new residual networks. In order to avoid traversing simple paths with saturated edges, the augmented path selection tree (ART) is further used to organize all possible augmented path sets. The maximum flow can be obtained by finding all necessary augmented paths from the root node to a leaf node. The depth of traversal is the height of the ART tree H, which is much smaller than the number of all the augmented paths, so the efficiency of solving the maximum flow is improved significantly. The experimental results show that compared with the classical Dinic algorithm, MFIA-ART can improve the performance of the time order of magnitude, and it is especially suitable for sparse networks with small number of simple paths.
【作者單位】： 東南大學(xué)計算機科學(xué)與工程學(xué)院;東南大學(xué)計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室;中國能源研究會電力安全與應(yīng)急技術(shù)中心;南京弘毅電氣自動化有限公司;
【基金】：國家自然科學(xué)基金資助項目(61300200,61232007,61073059)
【分類號】：TP301.6
，

本文編號：2316727