基于二元决策图的网络可靠性评估  

Network reliability evaluation based on binary decision diagrams

作　　者：何明[1] 权冀川[1] 郑翔[2] 赖海光[1] 杨飞[1] 

机构地区：[1]解放军理工大学指挥自动化学院,南京210007 [2]解放军理工大学通信工程学院,南京210007

出　　处：《控制与决策》2011年第1期32-36,共5页Control and Decision

基　　金：国家自然科学基金项目(60974086)

摘　　要：提出一种改进二元决策图(BDD)的网络可靠性评估方法.为了解决BDD构造中有效识别同构子图的问题,将边收缩/删除法应用于BDD的图分解中,并提出了BDD的宽度优先搜索算法,通过遍历BDD图对边进行排序,为布尔函数的不交化提供了一种新的高效途径.实验结果表明,该算法具有精确性高、时间复杂度低的优点,可以避免常规最小路算法中进行不交化的大量运算,并可应用于一些大规模的网络.An improved method for evaluating the network reliability based on binary decision diagrams（BDD） is presented. To solve the structure in the effective identification of BDD subgraph isomorphism problem, the edge contraction/deletion is applied to this decomposition process of network graphs, and the width first search algorithm of BDD is proposed. By traversing BDD graph, the edges are sorted. A new and efficient way is provided for the Boolean function disjoint. The experiment results show that, the algorithm has the merit of high accuracy and low time complexity, and can avoid a large number of disjoint operations in the minimum path algorithm, which can be applied to a number of large-scale networks.

关 键 词：二元决策图 网络可靠性 评估 

分 类 号：TM623[电气工程—电力系统及自动化]