《一类3状态有向设备网络系统可靠度的一个线性时间算法》由会员分享，可在线阅读，更多相关《一类3状态有向设备网络系统可靠度的一个线性时间算法（4页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 6 V 0 1 3 3 N Q 8 ( 增刊)一类3 - 状态有向设备网络系统可靠度的一个线性时间算法AL i n e rT i m eA l g o r i t h mf o rC o m p u t i n gt h eR e l i a b i l i t yo faC l a s so f3 - s t a t eD i r e c t e dD e v i c eN e t w o r k s张军明1 李东魁2( 赤峰学院计算机科学与技术系赤峰0 2 4 0 0 1 ) 1( 包头师范学院计算机系包头0 1 4 0 3 0 ) 2A b s t r a c tI
2、 nt h i sp a p e r ，w eh a v eg i v e no u taf a c t o r i n gt h e o r e mf o r3 - s t a t ed i r e c t e dd e v i c e sn e t w o r k sr e l i a b i l i t yt o m p u t i n g ，t h e n ，w eh a v ep r o v e ns o m er e l i a b i l i t y - p r e s e r v i n gr e d u c t i o n sf o rc o m p u t i n gr e
3、 l i a b i l i t yo f3 - s t a t ed i r e c t e dd e v i c e sn e t w o r k s U s i n gt h e s er e d u c t i o n s ，w eg i v eo u tae f f e c t i v ea l g o r i t h mf o rc o m p u t i n gt h er e l i a b i l i t yo fac l a s so f3 一s t a t ed i r e c t e dd e v i c e sn e t w o r k s K e y w o r d
4、 sF a c t o r i n gt h e o r e m ，R e l i a b i l i t y - p r e s e r v i n gr e d u c t i o n ，E f f e c t i v ea l g o r i t h m1引言假定有向图D 一( N ，A ) 表示3 一状态有向设备网络，N 是结点集，A 是弧集，弧表示设备。系统处于短路失效状态：如果网络D = ( N ，A ) 中存在一条从源结点s 到汇结点t 的s _ t 有向最小路，其上的设备都处于短路失效状态。系统处于开路失效状态：如果网络D = ( N ，A ) 的每一条s t 有向最小路，其上
5、都至少有一个设备处于开路失效状态。否则，系统处于正常工作状态。有向3 一状态设备网络的可靠度计算问题是指利用设备的已知状态概率给出系统的各状态概率。按以上定义，我们若记： P 1 ( D ) 一网络系统D = ( N ，A ) 每条弧i 具有成功概率S i 时系统成功的概率；P 2 ( D ) = 网络系统D = ( N ，A ) 每条弧i 具有成功概率S ；+ P t 时系统成功的概率。其中P ；，q i ，S i 分别为弧i 的正常工作状态概率、开路失效状态概率及短路失效状态概率，且P i + q i + S ；一1 ，则有系统正常工作状态的概率P ( D ) 一P 2 ( D ) 一P
6、1( D ) ；系统的开路失效状态概率Q ( D ) = l P z ( D ) ；系统的短路失效状态概率S ( D ) = P 1 ( D ) 。有向3 一状态设备网络D = ( N ，A ) 中，一条弧e称为是可去的，如果弧e 收缩后得到的网络D 。e 有和D 一样多的含弧e 的s - t 有向最小路。这里D 。e中含e 的s - t 有向最小路是指通过e 收缩为一点那点的s t 有向最小路。否则，称之为不可去的。这样，我们有：引理1设e 是3 一状态有向设备网络D 一( N ，A ) 的一条可去弧，则P ( L ) ) 一p 。( P ( D 。e ) + S ( D e ) 一P (
7、I ) 一e ) 一S( D e ) ) + S 。( P ( 1 ) e ) 一P ( D e ) ) + P ( D e )其中G 。e 表示G 收缩弧e 得到的图，G - e 表示G 删除弧e 后得到的图，P 。，q e ，S e 分别是弧e 的正常工作状态概率、开路失效状态概率及短路失效状态概率，且p 。+ q e + S 。= 1 。 定理2 设e 是3 一状态有向设备网络D 一( N ，A ) 的任意一条可去弧，则有S ( D ) = s 。S ( D 。e ) + ( 1 一s e ) S ( D - - e )Q ( D ) 一( p e + s 。) Q ( D e ) +
8、( 1 一q 。一S 。) Q ( D e )P ( D ) 一( q t + S 。) ( Q ( D 。e ) 一Q ( D e ) ) + s 。( P( D 。e ) 一P ( D e ) ) + ( S ( D e ) 一S ( D- - e ) ) + P ( D e )2 有向网络的保可靠度简化2 1 几种平凡简化( 1 ) 删除平凡无用弧平凡无用弧是指进入源结点或从汇结点发出的弧。 ( 2 ) 删除死终结点和故障开始结点一个死终结点是一个不是汇点但没有弧从这个结点发出的结点。 一个故障开始结点是一个不是源点但没有弧进入这个结点的结点。( 3 ) 如果有向3 一状态设备网络D 有
9、一个单一弧i 从源结点发出或进入汇结点，收缩这条弧得到网络D ( 邻接结点成为新的源结点或汇结点) ，这时有：S( D ) = s lS ( D 7 ) ，Q ( D ) 一( 1 - - q i ) Q ( D i ) + q 成立。( 4 ) 如果只有一条弧进入( 或发出) 一个不是汇结点( 或源结点) 的结点，那么它的反向平行弧( 如果存在) 可以被删除。2 2 串联简化与并联简化定理3 ( 串联简化)设弧j 一( u ，v ) ，j = ( v ，w )是3 一状态有向设备网络的两条同向弧，u W ，v 的出度和人度都是1 ，v s ，t 。将边i ，j 用一条新弧l16 9= ( u
10、 ，w ) 替换，定义新弧的开路失效概率与短路失效概率分别为q l = q i + q j q i 哂，S I = S t s j ，且Q 1 =Q 1 ( q ) 一1 ，Q 2 “= Q 2 q ) 一0 ，则这个变换是保可靠度简化。定理4 ( 并联简化)设i 一( U ，v ) ，j = ( u ，v ) 是3 一状态有向设备网络的两条弧。将弧i ，j 用一条新弧l 一( u ，v ) 替换，定义新弧的开路失效概率与短路失效概率分别为q t q Iq l ，S l S i + s j s iS j ，且Q l 3 一Q 1 q ) 一1 ，Q ：“= Q 。( q - - - - 0 ，
11、则这个变换是保可靠度简化。2 32 一邻结点简化在一个有向3 一状态设备网络D 一( N ，A ) 中，结点U 称为另一个结点的邻居，如果D 有一条弧e =( u ，v ) 或e = ( v ，u ) 。一个结点U 称为是2 一邻结点，如果u 恰有两个邻居。关于2 一邻结点，下面的性质成立：命题5 对一个没有并联弧的有向图D ，如果D含有一个2 一邻结点u ，那么它是下面六种给定的类17 0 型之一。类型1v袁1类型2、，类型3 V类型4、，类型5类型6aW类型2 一邻结点替换变换公式1V ，! 从吵owY 2，喈、bAwq x2 q a + q b q a q bVq!pwO S x = S
12、 a S b3dAwq y2 q c + q d q c q dv 矿了AS y2S c S d4v ) ! p峨力WV表2类型l2 一胁翻aw dK b f变换公式 3 ) 。M “1 ，M ( q ) l ，T v _ 一 S 卜一 t 。S t e p l 重复执行( 1 ) ，( 2 ) ，( 3 ) 直到T 是空集。( 1 ) 从T 中取出一个结点U 。，( 2 ) ( 检查1 1 是否为一个2 一邻结点) 依次考虑进入结点U 或从结点u 发出的边，直到找到u 的三个邻结点或者所有的边都已经检查完。实行可能的并联简化。( 3 ) 如果u 是2 一邻结点，v 和w 是它的邻居结点，那么
13、利用表2 对u 实行对应的2 一邻结点简化。如果v S 或v t ，且v 不在T 中，将v 加到T 中。类似地，如果w s 或w t ，且w 不在T 中，将w 加到T 中。S t e p 2 ( 检查是否s 有多于两个的邻结点) 依次考虑从源结点S 发出的边，直到找到S 的三个邻结点或者全部的边都检查完毕。实行可能的并联简化。如果S 有多于两个的邻结点，那么D 不是个基本串并联有向图，转S t e p 6 。S t e p 3 ( 检查有向图是否可简化为一条边) 如果( 下转第2 1 4 页)17 1各种算法的比较A 。大小平方于该正规则表达式，一般它的尺寸最大，A p d 和A f 线性于正
14、规则表达式，而A 。b 线性于正规则表达式对数平方。可以看出A D d 和A f 是这四种算法中最小的。 结论从以上转移图和参数法的工程实例分析，在大部分实际应用中，部分派生自动机A 耐和跟随自动机A r 的尺寸总的说来是比较小的，但两者不好比较。它们在很多例子，比如程序语言标识符，浮点数，C 语言注释语句等，都是一样大，只有对例2那样的正规则表达式A 一是最小的。共同跟随集合自动机A d 5 算法，虽然是迄今为止比较其他几种N F A ，最坏情况是最好的，为O ( n ( 1 0 9n ) 2 ) 。但是为了减少转移数目，状态数目被人为增加，这使得它在一些情况下可能比其它三种自动机大，它只是
15、在例3 情况下是最小的。位置自动机A 。是早期提出的一种算法，它的尺寸一般总是最大的，尽管经过许多学者的改进和演变，但由于因为结构简单，仍然被广泛使用。以上总结的规律和原则对于构造正则表示式时，如何选择最佳的N F A 算法，提供了重要的参考依据。现在不断有学者提出新的算法，但针对不同的正则表示式进行分析比较时，没有哪种N F A总是最好的或者最坏的。确切地说必须根据具体的正则表示式来进行判断。从理论上来讲，在普遍情况下找出比较各种自动机的算法尺寸的规律是困难的，目前可能最好的方法是实际测试比较。参考文献1A n t i m i r o vv P a r t i a ld e r i v a
16、t i v e so fr e g u l a re x p r e s s i o n sa n df i n i t e a u t o m a t o nc o n s t r u c t i o n s T h e o r e t C o m p u t S c i ，1 9 9 6 ，1 5 5 ：2 9 1 3 】92B e r r yG ，S e t h i1 LF r o mR e g u l a rE x p r e s s i o n st OD e t e r m i n i s t i e A u t o m a t a T h e o r e t C o m p u t S c i ，1 9 8 6 ，4 8 ：1 1 7 1 2 6 3G ，l u s h k o vv T h ea b s t r a c tt h e o r yo fa u t o m a t a
