一种网络可靠度分析的不交和算法

《一种网络可靠度分析的不交和算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、191辽宁_T-学院学报vo119一1999年2月JOURNALOFLIAONINGINSTITUTEOFTECHNOLOGYFeb．1999一种网络可靠度分析的不交和算法许君臣』(基础科学部)摘要通过对AIW算法的改进，得到了一十十分有效的计算网络可靠度的方法。利用本算法所产生的相关系统可靠性公式中的项数，一般要比AIR和AIW算法所产生的项数少。本算法主要包括两部分，即外循环和内循环。在外循环采用一种新的规则对路径(或割)进行排序，内循环的不交和运算采用单个变量取逆的形式。关键词最短路；相关系统；不交乘积

2、和；变量；ALR；ALW帽一％幕俚予利用不交和的原理计算网络的可靠性是当今所有计算。网络可靠性方法中最有数的方法之一。通过输入二元相关系统的最短路径(或最小割)使每条路径(或割)都能产生一个项的集台，这个集台中的各个元素互不相交，并且与前面的路径所产生的项也不相交，由于路径集中的每条路径都是统计独立的，而且所有的项都不相交，所以系统的可靠性公式就是这些项的代数和首次比较完整地利用不交和的方法建立二元相关系统可靠性公式的是Abraham口，在诸文献一般普遍使用的典型例子(本文例子)中，系统可靠性公式共含有71个

3、不相交的项。这之后，FBeichelt，I．Spross口改进了Abraham的算法，对于同一个例子，可靠性公式减少到63项，同时Locks提出了ALR算法，也得到含有61项的不交和公式，1990年．WillSOl2n进一步修改了ALR算法，提出ALW算法，对于上述同一个例子，系统可靠性公式含有59项。而应用本文提出的算法，可靠性公式中只含有55项。本算法在产生不交和公式时，仍采用以最短路径(或最小割)作为输人数据，且为了方便起见，仅对两终端的网络进行讨论，算法基本上遵循Abraham_1的思想，采用每一步外

4、循环都包含一系列内循环的形式。外循环采用新的路径排序规则，根据每一项中各变量在其前面各项中出现的次数总和进行排序，出现次数总和较大的项排在前面。内循环利用等价关系，对每次极小化后所得到的各个因子进行分类，排序．然后再化成不交和的形式，使程序更加规范化，并且在进行不交和运算时，采用单一变量进行取逆运算1系统可靠性公式车稿1998年4月24日收到。许君臣：男-1964年生，讲师．硬士锦州市士英街169号辽宁工学院基础科学都，由5编1210011999年(总第65期)许君臣：一种网络可靠度分析的不变扣算法1．1基本

5、概念及运算法则设集合A，A1，A^+2，⋯，A，如果A．^nA¨l≠，A+1nA+z≠，⋯，AnA．，≠则定义A～J4这样～就确定了一种相容关系，根据这个相容关系可以得到一种分类。设集合A．B，C，⋯，则可以得到以下运算规则：Demorgan法则：A+B—AB；AB=A+B．(1)万丽一t2ABCADF—BCADF(3)ABlAB2⋯A8一A十AB1B2⋯B(4)(A+B)C—AC+BC(j)A+B=A—BB+百=一A十A百AB+CD—AB+ACD+ABCD1．2可靠性公式定理设尸，，⋯，尸为系统的条最短路径

6、，则系统的可靠度【1⋯lP一∑Ⅱ一∑ⅡPi-lJ=1I=1一1其中P。=1．证明当z=2时P—P】十P2=Pl+PlPz定理成立。于是由Demorgan法则，当l=时尸一尸++⋯+尸+P一P++⋯+⋯+尸尸2+⋯+P】P2⋯尸一2P一1]尸=∑Ⅱ尸．+(尸+P2)⋯(P+尸+⋯+尸一+：=)尸f一1Jl^1f1Hl一】一∑ⅡP．+⋯P一∑nPf一1J=1i一1一1式(1)可以表示成P一∑且P：=∑(2)其中B．一n，并且B，一一1，一且PJ一】2算法算法基本上遵循Abraham：的思想，包含两部分；外循环和内

7、循环。2．1外循环列出二元相关系统全部最短路径，它们将作为布尔多项式中的项。每一项的变量都具有1一值，每个变量用字母表示，同时它也代表网络中的一条边。分别把各最短路径按字母46辽宁工学院学报(自然科学版)第19卷第1期表的顺序排列，然后根据下列规则所列出的路径排列顺序。t1)含变量个数较少的项排在较长的项的前面。设含有相同长度的项组成一个子集S．．则所有的项被分为S．，S：，⋯⋯S其中S中各项的长度为(一1，2，⋯．r]，且，<：<⋯<，．(2)在S中，按字典排列顺序取第一项，以后各项按照它与前一项所含的公共

8、元素个数多少进行排列，含有公共元素多的项排在前面；若含有公共元素最多的项不只一个，则按照字典的顺序进行排列。(3)对S中的任意两项P和，分别考察它们中的每个变量在S中出现的次数总和Mz(P．)和M2(P)，如果(a)2(P)>z()，则排在P的前面；(b)(P)