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

摘要：

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

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

所属期刊栏目：37

分类号：TP393(计算技术、计算机技术)

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

在线出版日期：2016-09-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：2032-2036,2056