不确定图最可靠最大流算法研究
蔡　伟　张柏礼　吕建华

计算机学报  Vol.35  No.1  Nov  2012

 

摘要　

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

但时间复杂度方面具有较大的优势，能够很好地解决SPCA算法性能受制于容量的问题，具有更好的性能与适用性．

关键词　不确定图；可能世界模型；最大流；流可靠性

 

1 引言

  不确定图

  research problem:  如何在不确定图中寻找最可靠子图问题 ?

  author's work: 

  -- 基于可能世界模型，首先对不确定图最可靠最大流问题进行定义，并给出最大流可靠性的概率计算模型

  -- 然后，借鉴随机流网络中相关的算法，针对问题提出一种基于简单路径组合思想的基本算法SPCA (Simple path Combination Algorithm)

 

 

2 问题定义

3 基于简单路径组合算法

 

3.1 流约束模型

 

3.3. SPCA算法
  SPCA算法主要由５步骤构成

 

 

4 基于空间划分算法

 

5 实验

6　结论