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

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

为了明确启发式排序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.