摘要： 采用边界分区标识网络的思想,实现基于边界分区的自顶向下K端可靠度二叉决策图(BDD)构建算法。针对BDD构建过程中存在的节点冗余问题,提出无效边冗余消除和K点非连通冗余消除2种处理技术。在规则网络和实际工程中的实验结果表明,利用无效边冗余消除和K点非连通消除技术后的BDD改进算法,在不影响算法时间性能的情况下,可大幅缩减BDD尺度,提升K端网络可靠度分析算法性能,适用于大规模的网络可靠度分析。

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

Abstract: 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 K-terminal network reliability analysis of algorithm performance,without affecting the time performance,which is applied to larger scale network reliability analysis.

Key words: network reliability, Binary Decision Diagram(BDD), boundary set, edge contraction, redundancy

中图分类号: 

• TB114