不确定图最可靠最大流算法研究

Algorithms of the Most Reliable Maximum Flow on Uncertain Graph

文中首先基于可能世界模型提出了不确定图的最可靠最大流问题和可靠性计算模型,这对于构建可靠性网络、可靠传输路径选择以及系统薄弱环节分析等一系列实际问题具有重要意义;然后基于简单路径组合思想提出了一种求解最可靠最大流的算法SPCA,通过简单路径流量的组合,在无需求得所有最大流分布的情况下获得最可靠最大流,并在组合过程中引入概率剪枝与约束剪枝策略,对无效组合进行过滤,从而显著地提高了算法效率;接着文中针对SPCA算法易受路径数量及瓶颈容量影响的问题,又提出一种基于状态空间划分的最可靠最大流算法SDBA,该算法的主要思想是将不确定图所蕴含的子图空间划分为互不相交且满足最大流值的闭合区间集合,进而寻找所有闭合区间中概率最大的下界状态,经证明这个下界状态对应子图中的最大流分布为最可靠最大流;最后通过实验,比较了两种算法的性能.实验结果表明SDBA算法相对于SPCA算法其空间复杂度有一定的增加,但时间复杂度方面具有较大的优势,能够很好地解决SPCA算法性能受制于容量的问题,具有更好的性能与适用性.

Reliability is one of the most important issues on system design and maintenance, such as reliable network construction, reliable transportation path selection, etc. This paper defines the most reliable maximum flow problem （MRMF） on uncertain graphs based on the possible world model, and introduces the reliability calculation model of MRMF. A simple path combina- tion （SPCA） based algorithm is put forward, which can get the most reliable maximum flow without calculating all the maximum flow distributions. Furthermore, a space decomposition based algorithm （SDBA） is proposed to avoid the influence of the numbers and the bottleneck capacity of simple paths. SDBA divides the sub-graph space of an uncertain graph into a collection of closed intervals, which are disjoint and satisfy the maximum flow constraints. Among the lower bounds of all the intervals, the one with greatest probability is proved to be the most reliable maximum flow. Finally, experimental results show the effectiveness and efficiency of the proposed algorithms.