首页 | 本学科首页   官方微博 | 高级检索  
     

不确定图最可靠最大流算法研究
引用本文:蔡伟,张柏礼,吕建华.不确定图最可靠最大流算法研究[J].计算机学报,2012,35(11):2371-2380.
作者姓名:蔡伟  张柏礼  吕建华
作者单位:1. 东南大学计算机科学与工程学院 南京210096
2. 东南大学计算机网络和信息集成教育部重点实验室 南京210096
基金项目:国家自然科学基金项目,江苏省自然科学基金项目
摘    要:文中首先基于可能世界模型提出了不确定图的最可靠最大流问题和可靠性计算模型,这对于构建可靠性网络、可靠传输路径选择以及系统薄弱环节分析等一系列实际问题具有重要意义;然后基于简单路径组合思想提出了一种求解最可靠最大流的算法SPCA,通过简单路径流量的组合,在无需求得所有最大流分布的情况下获得最可靠最大流,并在组合过程中引入概率剪枝与约束剪枝策略,对无效组合进行过滤,从而显著地提高了算法效率;接着文中针对SPCA算法易受路径数量及瓶颈容量影响的问题,又提出一种基于状态空间划分的最可靠最大流算法SDBA,该算法的主要思想是将不确定图所蕴含的子图空间划分为互不相交且满足最大流值的闭合区间集合,进而寻找所有闭合区间中概率最大的下界状态,经证明这个下界状态对应子图中的最大流分布为最可靠最大流;最后通过实验,比较了两种算法的性能.实验结果表明SDBA算法相对于SPCA算法其空间复杂度有一定的增加,但时间复杂度方面具有较大的优势,能够很好地解决SPCA算法性能受制于容量的问题,具有更好的性能与适用性.

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

Algorithms of the Most Reliable Maximum Flow on Uncertain Graph
CAI Wei , ZHANG Bai-Li , LV Jian-Hua.Algorithms of the Most Reliable Maximum Flow on Uncertain Graph[J].Chinese Journal of Computers,2012,35(11):2371-2380.
Authors:CAI Wei  ZHANG Bai-Li  LV Jian-Hua
Affiliation:(School of Computer Science and Engineering,Southeast University,Nanjing 210096)(Key Laboratory of Computer Network and Information Integration of Ministry of Education,Southeast University,Nanjing 210096)
Abstract:
Keywords:
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号