一种用于BDD网络可靠性分析的启发式排序新方法  

A novel ordering heuristic for BDD-based network reliability analysis

作　　者：潘竹生 李闻白 林飞龙 PAN Zhusheng;LI Wenbai;LIN Feilong(College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua 321004,China;College of Economics and Management,Zhejiang Normal University,Jinhua 321004,China)

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

出　　处：《浙江师范大学学报（自然科学版）》2022年第4期378-387,共10页Journal of Zhejiang Normal University:Natural Sciences

基　　金：国家自然科学基金资助项目(61877055)。

摘　　要：BDD(binary decision diagram)模型大小严重影响基于BDD的网络可靠性分析方法的性能,而所选定的变量排序又决定着BDD模型大小.然而,选择最佳变量排序是一个NP-hard问题,在实际应用中,通常采用启发式排序.其中,BFS(breadth-first-search)应用最为广泛,也被认为是最好的排序.为寻找新的高性能启发式排序,从分析基于边界集的BDD模型构建的动态过程入手,研究影响BDD模型大小的因素,得到启发式指导参数:BDD模型宽度和边界集总长度,提出排序起点选择方法和BDD模型宽度小优先的排序策略.大量实验表明,新提出的启发式排序能指导生成更小的BDD模型,从而提升基于BDD的网络可靠性分析方法的性能.The performance of network reliability analysis method heavily depended on the size of BDD model.However,the BDD size was determined by the chosen variable ordering.As finding the optimal variable ordering was an NP-hard problem,a heuristic had to be used in practice.Among them,the BFS(breadth-first-search)was widely used and considered to be state-of-the-art.From deep understanding of the dynamic process of BDD model construction based on boundary set,it was derived two important measures for building a high-performance heuristic ordering.One was the width of BDD model,which was guided to design the ordering strategy,the other was the sum of the length of each boundary set,which was used to choose the starting vertex.The idea of ordering was the width of BDD model should be as smaller as possible.The Comprehensive examples and experiments showed that the proposed heuristic would bring smaller BDD models.With the advantage,runtime and memory requirements could be drastically reduced for BDD-based reliability methods.

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

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