摘要： 分析基于路集矩阵与布尔运算的网络可靠度算法，指出其存在组合爆炸问题。为此，提出一种改进算法，引入位矢量以减少内存需求，对特殊路集进行预处理并统计全1位矢量。实验结果表明，改进算法可提高内存利用率、减少冗余运算，能在一定程度上缓解组合爆炸问题。

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

Abstract: 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.

Key words: network reliability, inclusion-exclusion principle, pathset matrix, Boolean operation, bit vector

中图分类号: 

• TP393