BDD网络可靠性分析中启发式排序策略性能比较及指标数据研究  

Performance comparison and insight into heuristic ordering strategies in BDD-based network reliability analysis

作　　者：李闻白 潘竹生 王耀燕[3] 林飞龙 LI Wenbai;PAN Zhusheng;WANG Yaoyan;LIN Feilong(College of Economics and Management,Zhejiang Normal University,Jinhua 321004,China;College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua 321004,China;Yiwu Industrial and Commercial College,Yiwu 322000,China)

机构地区：[1]浙江师范大学经济与管理学院,浙江金华321004 [2]浙江师范大学数学与计算机科学学院,浙江金华321004 [3]义乌工商职业技术学院,浙江义乌322000

出　　处：《浙江师范大学学报（自然科学版）》2020年第2期162-167,共6页Journal of Zhejiang Normal University:Natural Sciences

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

摘　　要：为了明确启发式排序DFS,BFS和NDS的性能优劣及正确选择合适的排序策略和排序起点,采用实证研究方法,在比较DFS,BFS和NDS排序策略性能的基础上,研究排序策略选择和排序起点选择的指标数据.提出依赖集总长度小优先的排序策略和最佳排序起点的选择方法,并在工程网络中进行验证.结果表明:1)相比较于BFS和DFS,NDS能指导生成更小的BDD模型;2)指标数据依赖集总长度可以有效表征排序策略和排序起点;3)基于依赖集总长度小优先的选择方法有助于选出最优的排序策略和排序起点.该结果可以为选择和设计启发式排序策略提供理论依据.In order to clarify the performance of heuristic ordering DFS,BFS,and NDS,and to choose a heuristic and a root to build a smaller BDD model,performance comparison between DFS,BFS,and NDS were carried out.Firstly,based on empirical studies,a measurement index named TLDS(total-length-of-dependency-set)was proposed to characterize ordering strategy and ordering root.Then,an ordering strategy selection method and an ordering root selection method based on TLDS were proposed,and were verified to be correct in practical networks.The empirical researches showed that:1)NDS outperforms DFS and BFS for most cases brought the smaller BDD model;2)The measurement TLDS could effectively identify a heuristic ordering and its root;3)The selection method based on minimum-TLDS-first was helpful to choose a heuristic from an ordering library and find an optimal ordering root.The results could provide theoretical basis for choosing or designing high performance heuristic ordering.

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

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