基于改进的不交化最小路集的网络系统可靠性算法  

An Algorithm of Network System Reliabiilty Based on an Improved Disjointed Minimal Path Set

作　　者：史玉芳[1] 陆宁[2] 李慧民[3] 

机构地区：[1]长安大学建筑工程学院,陕西西安710061 [2]西安建筑科技大学土木学院,陕西西安710055 [3]西安建筑科技大学土木学院,陕西西安710054

出　　处：《计算机工程与科学》2011年第1期31-35,共5页Computer Engineering & Science

基　　金：陕西省自然科学基金资助项目(2005E211)

摘　　要：本文根据不交化布尔代数及BDD原理提出了一种简化的求解不交化最小路集的改进算法。对最小路集的路长进行排序,按最小路集的不同路长分两种方法不交化:对于长度为n-1的最小路集,在保持原有弧不变外,将网络图中其余未包含在该条最小路内的弧取逆加入,直接获得不交化运算结果;其余最小路集采用BDD方法进行不交化。最后的实例计算表明,改进的算法有较小的分枝树、较高的计算效率和精度,为大型网络系统的可靠性分析提供了一种新的途径。Constructing a disjoint minimal path set is an important approach for the reliability analysis of networks. Based on the disjoint theory and the BDD algorithm, an improved algorithm is presented for directly and simplily constructing disjointed minimal paths in which different disjoint methods are used for the minimal path set with different path lengths. According to the improved algorithm, a program is provided to obtian the disjointed minimal path set of the network system,and network reliability can be effectively worked out.Finally, a numerical example is given. It is shown that the method is efficient and accurate. It provides a new approach for the reliability analysis of largescale network systems.

关 键 词：网络系统 可靠性 不交化最小路集 BDD算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]