BDD网络可靠性分析中启发式排序策略研究  

Insight into Heuristic Ordering Strategies in BDD-Based Network Reliability Analysis

作　　者：李闻白 潘竹生 林飞龙 LI Wen-bai;PAN Zhu-sheng;LIN Fei-long(College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua Zhejiang 321004,China)

机构地区：[1]浙江师范大学数学与计算机科学学院,浙江金华321004

出　　处：《计算机仿真》2020年第5期165-172,共8页Computer Simulation

基　　金：国家自然科学基金(61503343,61877055);浙江省自然科学基金(LY18F030013)。

摘　　要：启发式排序DFS、BFS和NDS被广泛应用于BDD网络的可靠性分析,然而这三种排序策略整体性能的优劣性尚缺乏研究成果。采用实证研究的方法,通过比较DFS、BFS和NDS排序策略在规则网络De-Bruijn、Square Lattice和Hyper Cube以及工程网络中的性能表现,得到NDS优于BFS和DFS,以及最佳排序起点分布有规律等两组结论,并提出一种最佳排序起点选择方法。实验结果表明,所提方法有利于提高基于BDD的网络可靠性分析方法的性能。Heuristic orderings, such as DFS, BFS and NDS, are widely used to build the BDD models in network reliability analysis. However, there is no such a conclusion about which one is the best in DFS, BFS and NDS. In this paper, using comparative studies and empirical studies which are performed in De-Bruijn network, Square Lattice network, Hyper Cube network and some lifeline networks, we concluded that NDS outperforms DFS and BFS for most cases, and the contribution of the best ordering root node is regular. Furthermore, we proposed a new method to choose root node for BDD model construction. They are of significance to improve the performance of BDD-based network reliability analysis.

关 键 词：网络可靠性 二叉决策图 启发式排序 

分 类 号：TB114[理学—概率论与数理统计]