网络可靠性分析中自顶向下的二叉决策图构造研究  

Research on Binary Decision Diagram Construction in Top-down for Network Reliability Analysis

作　　者：曾令国[1] 潘竹生[1] 莫毓昌[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《计算机工程》2015年第1期309-315,共7页Computer Engineering

基　　金：浙江省教育厅基金资助项目(Y201328293;Y201328072);浙江省重中之重学科开放课基金资助项目(ZSDZZZZXK24)

摘　　要：采用边界分区标识网络的思想,实现基于边界分区的自顶向下K端可靠度二叉决策图(BDD)构建算法。针对BDD构建过程中存在的节点冗余问题,提出无效边冗余消除和K点非连通冗余消除2种处理技术。在规则网络和实际工程中的实验结果表明,利用无效边冗余消除和K点非连通消除技术后的BDD改进算法,在不影响算法时间性能的情况下,可大幅缩减BDD尺度,提升K端网络可靠度分析算法性能,适用于大规模的网络可靠度分析。Using the boundary partition of identification network thought,the Binary Decision Diagram（BDD） construction algorithm in top-down K-terminal reliability based on boundary partition is realized. Aiming at the problem of node redundancy existed in BDD construction process,this paper proposes two processing techniques about invalid edge redundancy elimination and K-point nonconnected redundancy elimination. Experimental results of regular network and practical engineering show that,the improved BDD algorithm with invalid edge redundancy elimination technique and K point nonconnected redundancy elimination technique,can substantially reduce the BDD scale,and enhance the Kterminal network reliability analysis of algorithm performance,without affecting the time performance,which is applied to larger scale network reliability analysis.

关 键 词：网络可靠度 二叉决策图 边界集 边收缩 冗余 

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