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

被引：9

作者：

蔡伟

张柏礼

吕建华

机构：

[1] 东南大学计算机科学与工程学院

[2] 东南大学计算机网络和信息集成教育部重点实验室

来源：

计算机学报 | 2012年 / 35卷 / 11期

关键词：

不确定图; 可能世界模型; 最大流; 流可靠性;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：2371 / 2380

页数：10

共 7 条

[1] 不确定图上的高效top-k近邻查询处理算法 [J].