动态网络中最大流快速增量求解
发布时间：2018-11-07 15:01
【摘要】：利用损毁网络与原网络的结构包含性,提出了一种基于增广路径选择树的最大流增量算法MFIA-ART.算法在原网络最大流的求解过程中,对简单路径集等相关的中间结果给予缓存,构成增广路径候选集,当网络拓扑改变时直接在其中查找有效的增广路径,无需对新的残余网络进行复杂计算.同时为了避免遍历包含饱和边的简单路径,进一步利用增广路径选择树ART来组织所有可能的增广路径集,从而可以通过一条从根节点到某个叶节点的路径找到所有需要的增广路径,获得最大流量.其遍历的深度为ART树的高度H,远小于所有增广路径的数量,因而显著地提高了求解最大流的效率.实验结果表明,MFIA-ART相对于采用经典的Dinic算法重新计算最大流的方法,在时间性能方面有数量级的提高,尤其适合应用于简单路径数量较少的稀疏性网络.
[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.
【作者单位】： 东南大学计算机科学与工程学院;东南大学计算机网络和信息集成教育部重点实验室;中国能源研究会电力安全与应急技术中心;南京弘毅电气自动化有限公司;
【基金】：国家自然科学基金资助项目(61300200,61232007,61073059)
【分类号】：TP301.6
，
本文编号：2316727
[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.
【作者单位】： 东南大学计算机科学与工程学院;东南大学计算机网络和信息集成教育部重点实验室;中国能源研究会电力安全与应急技术中心;南京弘毅电气自动化有限公司;
【基金】：国家自然科学基金资助项目(61300200,61232007,61073059)
【分类号】：TP301.6
，
本文编号：2316727
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2316727.html
