动态网络中最大流快速增量求解

摘要：

利用损毁网络与原网络的结构包含性,提出了一种基于增广路径选择树的最大流增量算法MFIA_ ART.算法在原网络最大流的求解过程中,对简单路径集等相关的中间结果给予缓存,构成增广路径候选集,当网络拓扑改变时直接在其中查找有效的增广路径,无需对新的残余网络进行复杂计算.同时为了避免遍历包含饱和边的简单路径,进一步利用增广路径选择树ART来组织所有可能的增广路径集,从而可以通过一条从根节点到某个叶节点的路径找到所有需要的增广路径,获得最大流量.其遍历的深度为ART树的高度H,远小于所有增广路径的数量,因而显著地提高了求解最大流的效率.实验结果表明,MFIA_ART相对于采用经典的Dinic算法重新计算最大流的方法,在时间性能方面有数量级的提高,尤其适合应用于简单路径数量较少的稀疏性网络.

关键词：最大流、增量算法、增广路径选择树、简单路径

所属期刊栏目：47

分类号：TP301.6;TP393(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61300200,61232007,61073059

在线出版日期：2017-10-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：450-455