基于路集矩阵与布尔运算的网络可靠度算法  

Network Reliability Algorithm Based on Pathset Matrix and Boolean Operation

作　　者：高会生[1] 展敬宇[1] 王博颖[1] 李潇睿[1] 

机构地区：[1]华北电力大学电子与通信工程系,河北保定071003

出　　处：《计算机工程》2012年第11期117-119,共3页Computer Engineering

摘　　要：分析基于路集矩阵与布尔运算的网络可靠度算法,指出其存在组合爆炸问题。为此,提出一种改进算法,引入位矢量以减少内存需求,对特殊路集进行预处理并统计全1位矢量。实验结果表明,改进算法可提高内存利用率、减少冗余运算,能在一定程度上缓解组合爆炸问题。This paper analyzes the network reliability algorithm based on pathset matrix,and there exists a serious combination explosion problem in this algorithm.Aiming at this problem,it proposes a network reliability algorithm based on pathset matrix and boolean operation.The concept of bit vector is introduced.In addition,the pre-process of special pathsets and count of all-one bit vectors are also implied.Experimental results show that it not only increases the memory utilization,reduce the redundancy but also relieve the combination explosion problem in some degree.

关 键 词：网络可靠度 容斥原理 路集矩阵 布尔运算 位矢量 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]