摘要
采用边界分区标识网络的思想,实现基于边界分区的自顶向下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.
出处
《计算机工程》
CAS
CSCD
北大核心
2015年第1期309-315,共7页
Computer Engineering
基金
浙江省教育厅基金资助项目(Y201328293
Y201328072)
浙江省重中之重学科开放课基金资助项目(ZSDZZZZXK24)
关键词
网络可靠度
二叉决策图
边界集
边收缩
冗余
network reliability
Binary Decision Diagram(BDD)
boundary set
edge contraction
redundancy