最快路径问题下的网络可靠度OBDD算法

作     者：方春林 董荣胜 赵岭忠 FANG Chun-lin;DONG Rong-sheng;ZHAO Ling-zhong

作者机构：桂林电子科技大学计算机科学与工程学院广西桂林541004 

基　　金：国家自然科学基金项目(61363070) 广西高等学校高水平创新团队及卓越学者计划基金项目 桂林电子科技大学创新团队基金项目 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2016年第37卷第8期

页      码：2032-2036,2056页

摘      要：针对Theologou等给出的求解网络可靠度的factoring算法,分析该算法存在的冗余计算问题,给出DTN_OBDD算法。基于边排序策略的邻接终点矩阵方法,有效计算最小路集,将边失效特性引入网络可靠度分析中;基于最快路径求解公式,提高容量和时延约束下可行路径的筛选效率;构建所有可行路径的符号OBDD表示,遍历OBDD计算网络可靠度。以Python的igraph包生成的5组随机网络图为例,验证了DTN_OBDD算法的有效性,其中50个节点、201条边、状态空间为250的网络可靠度求解时间不超过80s。

主 题 词：网络可靠度 有序二叉决策图 最快路径问题 容量 时延 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 08[工学] 081201[081201] 0812[工学-测绘类] 

D　O　I：10.16208/j.issn1000-7024.2016.08.011

馆 藏 号：203187433...