（计算机应用技术专业论文）故障树分析算法改进研究与实现.pdf

河北工业大学硕士学位论文 故障树分析算法改进研究与实现 摘要 故障树分析法始于上世纪6 0 年代，现己成为系统可靠性和可用性常用预测方法之一， 广泛地应用于工程实践中。早期故障树分析程序，由于算法和计算机处理能力的原因，对 事件个数进行了限制，课题中对故障树的事件个数不再限制，可以对更大规模单调关联故 障树进行分析。单调关联故障树中引入的补事件，可以通过早期不交化的去补运算消除； 其它逻辑关系的门可以转换为与、门逻辑关系门。在算法分析中，采用两种可选的路径： 大量重复事件的故障树分析采用早期不交化、模块化、转移事件，无重复事件的故障树分 析采用转移事件来有效处理故障树分析中存在的n p 问题，这样故障树规模呈指数下降。 故障树的定性分析中采用了下行法结合素数法求最小割集，并对两种不同的割集存储方 式：队列指针法和二维数组法进行了对比，最终采用队列指针法，为故障树事件个数无限 制提供了可能。由于故障树底事件之间的相容性，进而对所求得的最小割集进行了晚期不 交化。在定量分析算法中引进了状态空间的概念，定义了c u b e 子集的运算并结合递归 s h a r p 算法获得故障树的完好模式不交化蕴涵族和故障模式不交化蕴涵族。所求得的不交 化蕴涵族不仅可以用于单调关联故障树的定量计算，也可以用于非单调关联故障树的定量 计算。 关键词：故障树分析法，n p 问题，定性分析，最小割集，不交蕴涵族 故障树分析算法改进研究与实现 r e s e a r c ho n i m p r o n ga n dr e a l i z i n g a _ i u t 丑哦螂i co ff a u l tt r e ea n a iy s i s a b s t r a c t f t a ( f a u l tt r e ea n a l y s i s ) b e g i n n i n gf r o m19 6 0 si s a ni m p o r t a n tm e t h o dt oe v a l u a t et h e r e l i a b i l i t ya n du s a b i l i t yo fs y s t e m t h ee a r l ya r i t h m e t i cl i m i t e st h en u m b e ro f e v e n t s w h i l et h e n e wo n eh a sn o t i tc a na n a l y z eb i g g e rc o h e r e n tf a u l tt r e e c o h e r e n tf a u l tt r e ea si ti s ，i ti sr i g h t t oh a v es o m en o n e v e n t sw h e nt h e s ee v e n t sc a l lb er e m o v e dt h r o u g ht h en o n o p e r a t i o n t h e r ei s o n l yt w ol o g i cr e l a t i o n s ( a n d o r ) b e t w e e nt h ee v e n t sa n dt h eo t h e rl o g i cr e l m i o n s c a nb e c o n v e r t e dt ot h et w ol o g i cr e l a t i o n s a l t h o u g ht h et h e o r yf o rt h ee v a l u a t i o no ft h ef a u l tt r e ea s s o c i a t e dm o n o t o n i c a l l yh a sb e e n d e v e l o p e dp e r f e c t l y , i ti sa l s oa ne m p h a s i si nt h ep a p e rh o w t ou s et h et h e o r ya v a i l a b l et o o p t i m i z et h ep r o g r a mr e a s o n a b l y a c c o r d i n gt ot h en o n d e t e r m i n i s t i c 7p o l y n o m i a lf n p ) i nt h e f a u l tt r e ea n a l y s i s ，t h ea m o u n to fc o m p u t a t i o ni n c r e a s e se x p o n e n t i a l l yw i t ht h en u m b e ro ft h e b a s i ce v e n t so faf a u l tt r e e t os o l v et h i sp r o b l e m ，t w om e a s u r e s ，e g e a r l y s t a g eu n i n t e r s e c t i o n ， m o d u l a r i z a t i o na n dt r a n s f e re v e n ta r eu s e dw i t hm o r er e p e a t e de v e n t sa n dt r a n s f e re v e n tw i t hn o r e p e a t e de v e n t s 珏h st h ea n a l y s i so f t h ef a u l tt r e ec a nd e s c e n de x p o n e n t i a l l y i nt h eq u m i t a t i v ea n a l y s i s ，w et a k et h em e t h o do ff u s s e l la n ds e t t i n gp r i m ef o re v e r yb a s i c e v e n tw i t ht h ed i f f e r e n tm e t h o d sf o rs t o r i n gt h ec u ts e t s ：q u e u e - p o i n t e ra n dt w o - d i m e n s i o na r r a y i ti sc l e a rt h a tt h eq u e u e p o i n t e ri st h eb e t t e nf o rt h ec e m e n tc l i n k e ri nt h eb a s i ce v e n t sa n dt h e e l e m e n t so ft h em i n i m a lc u ts e t ，i tn e e d st ot a k el a t e s t a g eu n i n t e r s e c t i o nt og e tt h e u n i n t e r s e c t i o n i m p l i c a n ts e t so fb o t ht h ef a u l tm o d ea n dn o r m a lm o d e t h er e s u l ti ss u i tf o r b o t ht h ec o h e r e n tf a u l tt r e ea n d 也en o n c o h e r e n tf a u l tt r e e k e yw o r d s ：f a u l tt r e ea n a l y s i s ( f t a ) ，n pp r o b l e m ，q u a l i t a t i v ea n a l y s i s ，m i n i m a lc u ts e t ， u n i n t e r s e c t i o n - i m p l i c a n ts e t 1 1 塑i ! ! ：些查兰竺! ：兰生堡兰 第一章绪论 1 - 1 论文的意义 卜卜1 故障树分析理论的发展状况 故障树分析法( f a u l tt r e ea n a l y s i s ) ，简称f t a 法，是在系统设计过程中通过对叫能造成系缆敞 障的备种冈素( 包括硬件、软什、环境、人为冈素) 进行分析，画出逻辑框图( 即故障树) ，从而确定 系统故障原因的各种可能组台方式和发生概率，升采取相应的改进措施，是提高系统可靠性的一种改 计分析方法。它是一种图形演绎法，是故障事件在一定条件下的逻辑推理分析方法。一般是由粜到冈， j 上而l i 的推理分析。它是围绕某些特定的状态作层层的分析，以清晰的故障树蚓形表达了零部件与 系统之间的逻辑关系。最终求出导致系统故障的最，l , 害l l 集( 最重要致命原因事件的组合) 并计算顶事 件发i ：的概率，对事件发生频率、费用及损失等作出相应( 或定性) 的评价。与f m e c a ( f a i l u r em o d e ， e f f e c t sa 1 1 dc r i t i c a l i t ya n a l y s i s ) 相比，不仅可以分析零部什的故障，还可以分析由于人为差错、软件错 误、拧制错误、环境应力等引起的故障，及进行多重故障分析。 故障树分析法是1 9 6 4 年由贝尔电话实验室的h a w a t s o n 提出的。6 0 年代初，f t a 在航空航天1 业中得到鹿用。从6 0 年代初期到7 0 年代，利用f t a 定量分析有了迅速的发展，并且成为原子反麻堤， 化学1 厂臀一些单位对可靠性、安全性有特别要求的系统不可缺少的分析方法之一。其中最有代表性 的工作是1 9 7 4 年美国原子能委员会发表的w h s h 一1 4 0 0 ，该j 二作用于评价核电赫的原子反应堆。1 9 7 5 年在奖倒召开的可靠性学术会议上，把f t a 和可靠性理论并列为两大进展，认为后者主要是由概率统 计学家推动发展起来的，而f t a 则是由j 二程师推动发展起来的。两者的侧重点不同，但实质是敛的。 1 9 7 7 年，l a p p & p o w e r s 在分析带有反馈的硝酸冷却系统时提山了一个非单调关联系统的故障树模蛩， 引起了可靠性学术界的热烈讨论，这标志着这一研究方向的兴起。在f t a 定性、定量分析方法和程序 方面的文章虽然很多，但存在n p 豳难，即计算量是接故障树规模的指数增长的困难。f t a 在应用于 多状态系统的带反馈系统、考虑统计相依事件( 包括共因失效) 等实际问题方面困难还很多“j 。 对丁故障树的评估，有定性和定量两种。定性分析是找出导致故障树中顶事州一发生的底事件绸台。 通常是求出割集与最小割集，路集与最小路集。其中以最小割集与最小路集为最重要，最小割集和展 小路集可“通过运算相互转换。求最小割集的方法有下行法( f u s s e l l v e s e l y ) 1 2 、上行法和利用可靠 性框倒! 故障树的等价关系求最小割集等。在定性分析的基础上进行定量分析。定量分析的目的是确 定顶 发生的概率和各种重要度的大小，为改进系统设计方案提供依据。 1 一l - 2 国内外故障树分析软件的发展状况 e j 前国外所开发的故障树软件很多，如：p r e p 、e l r a f t 、m o c u s 、t r e e l 、m i c s u p 、a l l c u t s 、 s e t s 、f t a p 等。对于定鱼分析的有：m t t 、s a m p l e 、m o c a r s 、f r a m t i c 等。住国内，清华人 学核能坎术研究所从1 9 8 0 年开始，经过3 年实践研制出了m f f t a p 的多功能故障树分析程序：航芏 航天部5 0 2 研究所也将f r a p 程序移植到i b m 微机上，西安交通人学研制了f t a m c 稗序。该程序运 用f u s s e l l 算法和素数相结合的算法求最小割集，芳能计算3 类顶事件( 独立事件、相斥事什和楣容事 河北工业大学坝| 学化论立 第一章绪论 1 - 1 论文的意义 】一卜l 故障树分析理论的发展状况 故雅树分析法( f a u l t t r e ea n a l y s i s ) 简称f t a 法，是在系统改计过群。t 通过对；，j 能造成系统敞 障的再种素( 包括地件、软什、环境、人为因素) 进行分析，画出逻辑框图( 即敞障树) ，从而确定 系统敞际原冈的各种可能组台方式和发生概率，并采取相应的改进措施，是提高系统可靠性的一种设 计分析力法。它是一种图形演绎法，足故障事件在一定条件下的逻辑推理分析方法。般是由果到田， 自上而r 的推理分析。它是罔绕某些特定的状态作层层的分析，咀清晰的故障树图形表达了零部r 与 系统之问的逻辑关系。最终求出导致系统故障的最小割集( 最蕈要致命原闪事件的翔台) 并计算顶事 件发生的概率，对事件发生频率、费用及损失等作出相应( 或定性) 的评价。与f m e c a ( f a i l u r em o d e ， e f t 。t sa n dc n t i c a l i c va n a l y s i s ) 相比，不仅可以分析零部件的故障，迁l 叮以分析由j 人为差错、软件错 误、挢哺4 惜误、环境应力等引起的故障，及进行多重故障分析。 故障树分析法是1 9 6 4 年由儿尔电话实验室的h a v a t s n n 提山的。6 0 年代初，f t a 在航空航天 业中褂创意甩。从6 0 年代初期到7 0 年代，列用f t a 定量分析有了迅速的发展并且成为原予反应堆， 化学厂等一些堕位对可靠性、安全性育特别要求的系统不可缺少的分析方法之一。其中最有i t 拒性 的t 作娃1 9 7 4 年美国原子能委员会发表的w h s h 1 4 0 0 该工作用_ 丁评价核电站的原子反应堆。1 9 7 5 年在茭崮召开的可霏性学术会议上，把v u a 和可靠性理论并列为两大进展+ 认为后者主要是由概事统 计学瘃推动发展起来的，而f t a 则是由工程师摊动发展起来的。两者的侧重点川i 同，但实质是致的。 1 9 7 7 年，l a p p & p o w e r s 在分析带有反馈静硝酸冷封系统时提出了一个菲单调关联系统的故障树模型 引起了可靠性学术界的热烈讨论，这标志着这一研究方向的兴起。在f t a 定性、定量分析方法干u 程序 方面的文章虽然很多，但存在n p 困难，即计算量是按故障树规模的指数增 圭的困难。f t a 在应用于 多状态系统的带反馈系统、考虑统计相依事件( 包括共凼失效) 等实际问题方面困难还很多”j 。 对1 故障树的评估，有定性和定量两种。定性分析是找出导致故障树中项事件发生的底事件组合。 通常是求出割集与最小割集，路集与最小路集。其中咀最小割集与最小路集为最重要，最小割集和最 小路集可以通过运算相互转换。求最小割集的力法有下行法( f u s s e l l v e s e l y ) bj 、上行法和利 j 可靠 肚框倒与故障树的等价关系求塌小割集等。在定r 性分析的基础上进行定量分忻。定量分析的目的是确 定项萼i 什发生的概率和各种重要度的大小，为改进系绩设计方案提供依据。 卜卜2 国内外故障树分析软件的发展状况 e i 前国外所开友的故障树软什很多如：p r e p 、e l i l f t 、m o c u s 、t r e e l 、m i c s u p 、a l l c u t s 、 s e t s 、f t a p 等。对于定量分析的有：t t 、s a m p l e 、m o c a r s 、f r a m t l c 等。在国内，清华人 学核能坎术研究所从t 9 8 0 年开始，经过3 年实践研制出了m f f l a p 的多功能故障树分析程序：航空 航天部5 0 2 研究所电将i - l 叠d a 程序移精到工b m 微机上，西安交通大学研制了f t a m c 旱序，该程序运 用f u s s e l l 算法和素数相结台的算法求最小割集，并能计算3 类顶事什( 独立事什、相斥事件干u 相容事 用f u s s e l l 算法和素数相结台的算法求最小割集，并能计算3 类顶事什( 独立事什、相斥事件干u 相容事 故障橱分析算法改进 i 1 究与实现 什) 的发生概率。现在各国也止集中注意力发展共囡失效模式，非相干故障树和不确定| 生分析的程序。 以上虽然有不少软件，但人部分在d o s 下运行，而且图形的形成多用c a d 。本课题住w i n d o w s 平台下使h jv c h 60 米研究开发故障树分析算法。 】、确定最小割集的程序 表1 1 确定最小割集的程序 t a b l e1i t h ep r o c e d u r e so f m i n i n m lc u ts e t s 2 、定趟评估程序 表1 2 定量评估程序 t a b l e1 2t h ep r o c e d u r e so f q u a n t i t a t i v ee v a l u a t i o n 卜2 本文研究思路和主要工作 卜2 一l 本文研究思路 1 、突破传统故障树分析软件对故障树事件个数的限制。 2 、由r 故障树分析中存在n p 困难，虽然目前计算机在运算速度和存储能力等方面都有j ，迅速发 展，但是对丁二火型故障树的分析凼难还是存在。冈此利用已有的理论研究合理的优化分析算法是本科 序要解决的问题。对于大型故障树的分析采用可选的两条途径，即对于有= 久量重复事件的故障树分析 采用早期不交化、模块化和转移事件来缩小故障树的分析规模而对于没有重复事件的大型故障树就采 用顶点分割和转移事件来缩小故障树规模。经分析处理后，故障树的规模早指数减小。 3 、对比两种不同的割集存储方法，为大犁故障树节点个数不受限制提供了理论依据。 4 、传统故障树分析多是针对某一领域内具体的故障来进行分析，此算法具有通用性。 卜2 2 本文研究过程及主要工作 1 、确定故障树的每一个节点的表示特征。 2 、选择一个途径来处理故障树的n p 问题。 3 、有人量重复事件的故障树，选择早期不交化、模块化、转移事件来简化故障树分析。 4 、无重复事件的故障树，选择顶点分割法、转移事件来简化故障树分析。 5 、对已经简化的故障树进行定性分析，在分析过程中对两种不同的割集存储方法进行r 分析、 对比从中选择了一种有利于改进算法分析的存储力法。 6 、对定性分析的结果进行了晚期不交化处理，得到故障树的完好模式不交化蕴涵族和故障模式 2 翌苎三、业盔兰塑主兰垡兰兰 不交化蕴涵族。所得的结果既可以用于正规故障树又可以用于非正规故障树的运算。 算法分析过程中几个主要模块示意图： 图1 1 模块示意图 f i g 1 1t h es k e t c hm a po f m o d u l e 故障树分析算法改进研究与实现 2 2 4 第二章故障树分析法( f t a ) 2 - 1 故障树分析法的特点与应用范围 1 - 1 故障树分析法的特点 1 、使一程人员能以演绎的方式直接探索出系统的故障所在。 2 、能指出与人们感兴趣的失效模式有重要关系的系统状态。 3 、对那些不了解系统设计的变化而要从事系统管理的人提供一个图示的帮助。 4 、提供了系统可靠性分析中定性或定量分析选择的可能。 5 、允许分析人员在某一时刻把注意力集中到某一特殊系统故障之上。 6 、给 程人员提供了对系统的真实而透彻的理解。 1 - 2 故障树的应用范围 1 、系统的可靠性分析； 2 、系统的安全性分析； 3 、故进系统的设计： 4 、概率风险的评估： 5 、系统在设计、维修、运行各个重要阶段进行重要分析和误差分析： 6 、故障诊断与检修表的制定； 7 、系统最佳探测器的配置； 8 、故障树的模拟； 9 、管理人员、运行人员的培训。 河北工业大学帧士学位论文 2 2 名词术语和符号 分析故障树需要了解系统的逻辑关系和逻辑门符号及事件符号。表( 2 1 ) 列举 【 故障树中常用的 事件符号及其含义。表( 22 ) 列举了常用的逻辑门符号及其含义。 表2 1 事件符号及含义 t a b l e2 1t h es y m b o la n dm e a n i n go f t h ee v e n t 故障树分析算法改进研究与实j 儿 表2 2 逻辑门符号及含义 t a b l e2 2t h es y m b o la n dm e a n i n go f t h el o g i cg a t e 2 - 3 逻辑门的使用说明及等价变换 1 、或门、与门。当至少一个以上输入事件发生，输出事件印发生，输出事件和输入事件之间的 逻辑关系连接门是或门。各输入事件必须全部发生，输出事件才发生，那么输入事件和输出事件之问 的逻辑关系连接门是与门， 2 、禁门是一种特殊的与门，仅有输入事件发生还不能导致输出事件发生，必须同时满足禁f j 打 开的条件，输出事件才发生。 图( 2 1 ) 指出：工作高度超过米；下方无遮拦物是工人坠落的发生条件。图( 2 2 ) 是另一种 表示，禁门右边的条什事件长圆形中注明禁门被打开的条件发生概率，这种形式又叫禁门的门概率因 子表示形式。 6 河北工业大学颧 j 学位论文 园 多 囱 圈倒 盆 图2 5 异或门图26 异或门曲等价转换 f i g2 5t h ee x c l u z i v e - o rg a t ef i g 2 6t h ee q u i v a l e n c eo f e x c l u s i v e - o rg a t e 4 、选举门是一种与门、或门组合的简化表示。进行定性分析和定量分析时，应将选举门变换为 原来的与门和或门组合。当把一个可靠性模型是n ，n 的系统转换成故障树时，相应的故障树上的选举 门是n r + 1 n 。如果一个系统，从可靠性模型米说是4 5 ，那么从故障看，就是一个3 5 系统，所以相 戍的纽台门为n r + 1 n = 5 3 + i 5 = 3 5 。 垫堡塑坌堑茎生整竺型至：! 兰墨 图2 72 3 选举门图2 8 选举门的等价转换 f i g2 72 3 f i g 2 8t h ee q u i v a l e n c eo f 2 3 5 、优先与门在定性分析和定量化中等价变换。 图29 优先与门 图2 1 0 优先与门的等价转换 f i g 2 9 t h e p r e f e r r e d a n d g a t e f i g 2 1 0 t h ee q u i v a l e n c eo f p r e f e r r e da n dg a t e 根据以上特蛛门的等价变换的原则，可以把任一棵故障树等价变换为基本故障树。 基本故障树：只含与门、或| 、j 、非门和基本事件的故障树，或只含与门、或fj 和基本事件以及基 本事件的补事件的故障树，称为基本故障树。 在进行定性分析( 寻找最小割集、最小路集) 和定量化之前，一叨故障树均应等价变换为基本故 障树，否则一般的故障树应用计算机程序进行分析和计算是很困难的。 2 - 4 故障事件的分类 故障事件是指系统或者系统中的部件发生了状态改变的过程。由部件的本身、外界环境或人为因 素引起的，或者由r 系统其它部件的控制原因而造成部件失去了规定功能称为部件故障事件。而系统 故障事什，是指其发生原因无法判断是单个部件的故障引起的，还是由丁i 部件的组合引起的故障。这 样划分的 的是为了建造故障树时做到思路清晰、层次分明。当从系统追溯剑部件故障甫什时，立即 可以判断出该故障事件是一次事件、二次事件和受控事件。 一次事件是指由部件本身原因造成的。例如，发动机的轴承内环破碎使转子卡步e 而造成发动机停 车，其发生的原因往往是由于疲劳、磨损或者是内部缺陷造成的。 _ 二次币件是指系统或本身以外的原因导致的故障。般指外界环境或人为筹错，如e 鸟被吸入发 动机内扣坏了压气机下作叶片等。 受控乖什义称指令事件，它的发生是由于本系统的其它某些部件或子系统的错误控制信号、指令 或噪声影响引起的。受控事件在建树过程中是需要进一步分解的。 分类力法不是唯一的，根据系统的特点可以加以区别。一般说来部件故障事件总可以按图( 2 1 1 ) 的规则进 if 女。图( 2 。1 2 ) 是描述部件的故障分类图。 8 l i t 工业大学坝士学位论文 图2 1 1 故障事件分类规则 f i g2 1 1 t h ea s s o e t e dr u l eo f t h e f a u l te v e n t 图2 12 部件故障分类 f i g 2 1 2t h es o r to f f a u l te v e n t 2 - 5 有关故障树的几个概念 ：状态故障树：如果故障树的底事件中不存在互不相容( 互斥) 的故障事t 1 ，称为一状态故障树。 多状态故障树：如果故障树的底事件中存在互不相容的故障事什，则称为多状态故障树 规范化故障树：将画好的故障树中的各种特殊事什与特殊门进行转换或删减，变成仅含有底事1 叶、 结果事什以及“与”、“或”、“非”三种逻辑门的故障树。由此所得的故障树称为规范化的故障树。 ! 规故障树：仅含故障事件以及与门、或门的故障树称为正规故障树。 非止规故障树：含有成功事件或者非门的故障树称为非正规故障树。 对偶故障树：将二状态故障树中的与门换为或门，或fj 换为与门而其余不变，这样得到的故障树 称为相应的对偶故障树。 成功树：除将二状态故障树中的与f 】换为或门，或门换为与门外，并将底事什与结果事件换为相 席的对立事什这样所得的树称为相应的成功故障树。 9 故障树分析算法改进研究与实现 第三章树的存储方法及遍历 3 - 1 二叉树 3 一卜l 二叉树的定义 r 二义树的定义是以递归形式给出的： 一棵二叉树是节点的一个有限结合，该集合或者为空，或者是一个根节点加上两棵分别称为左子 树和右_ r 树互不相交的二叉树组成。 二义树的特点是每个节点最多有两个子女 也就是说，在二叉树中不存在大于2 的点，并h ，因此，它可能有5 种不同的形态。 图3 1 二又树的形态 f i g 3 i2 k l e 矗日e f b m a w 潍e 上述 点分别表示：一棵空的二叉树，一个节点也没有；只有根节点的一叉树根的左于树和右 子树都是空的；根的右子树为空的二叉树：根的左子树为空的二义树；根的两棵子树都不为空的二叉 树。 3 - 1 2 二叉树的表示 存在两种实现二叉树抽象数据类型的存储表示：数组方式和链表方式。 1 、数组表示 如需将一棵_ 二叉树存放在一个向量中。为了能够简单地找到某一各节点的上下左右的关系，也必 须对二义树的节点进行编号，然后按其编号将它放到向量中去。 在编号时，如遇到空子树，应在编号时假定有此子树进行编号而在顺序存储时当作有子树那样 把位置留出来。这样才能反映二叉树节点之间的相互关系，由其存储位置找到它的双亲、子女、兄弟 节点的位置但这样做会消耗人量的存储空间。 2 、链表存储表示 数组表示法用于完全二义树的存储表示非常有效，但表示一般二义树则不很理想。此外，存一颗 树中进行插入和删除时，为了反映节点层次的变动可能需要移动许多节点，降低了算法效率，而使 用链表表示，可以克服这些缺点。 根据二一义树定义，可以设计出二叉树节点的构造。_ 二义树的每一个节点至少应当包含二个域：数 据d a m 、左子树节点指针mp l e f t 和右子树节点摆针”r j 曲t 。这种链表结构称为二叉链表，使用这 种结构，j 以方便的根据节点mp l e f t 指针和mp r g h t 指针找剑它的左孩子和右孩子，但要找到节点 的戕亲很困难。为了便于查找任一节点的双亲节点，可以在节点中再增加一个双亲指针m _ p p a r e n t ， 称为二叉链表。整个链表有个表头指针，指向树的根节点( 故障树的头节点) ，作用是当作树的访问点。 用链表表示一棵树，便丁j 插入、删除、修改和访问。因为数据不需要移动，只需修改指针，这样 1 0 河北工业大学硕士学位论史 丁以提高效率。 3 一l 一3 二叉树的遍历 一义树的遍历就是遵从某种次序，遍历二义树中的多个节点，使得每个节点被访问一次，而且只 访问一次。“访问”就是对节点施行某些操作，例如输出节点的信息、修改节点的数据值等，但要求这 种访问不破坏它原来的数据结构。 闻为二叉树是一种非线性结构，每个节点可能不止一个直接后继，这样必须规定遍历的规则。叛 此规则遍历二叉树，最后得到二义树节点的一个线性序列。 基丁_ 二叉树的递归定义，可以得到不同次序遍历二叉树的递归算法。 1 、先序遍历 先审遍历二义树算法描述： 若_ 二义树为空，则空操作；否则： 访则根节点； 先序遍历左子村： 先序遍历右子树： 2 、中序遍历 q ，序遍历二义树算法描述： 若义树为空，则空操作：否则： 1 市遍历左子树； 访根几点； 中序遍历右子树。 3 、后序遍历 i f 芋遍历二叉树的算法描述： 若一叉树为空，则空操作；否则 后序遍历左子树： 后j 节遍历右子树； 访问根节点。 住递归执行过程中，先序遍历的情形是每进入一层递归调用时先访问根节点，再依次向它的左、 冉子树递归调用。中序遍历的情形是从左子树递归调用退出时访问根节点，然后向它的右子树递归渊 州。后序遍历时，从其右子树递归调用退出时访问根节点。 通过遍历可以方便的插入、删除和查找任一节点。可以查找任一1 ，点的双亲节点以及孩子节点， 3 - 2 树的遍历 树的遍历方式有两种，即深度优先遍历和广度优先遍历。 3 2 一l 深度优先遍历 这种方式通常使用两种：先根次序( 先序) 遍历和斤根次序( 后序) 遍历。假如把树的_ 二义树表 示当作二叉树进行遍历就会发现：对树的二又树表示进行先根次序遍历的结果与对应二叉树的厉序遍 历结果一致。在故障树的模块化中采用的是先序遍历。 故障树分析算法改进 i f 究与实现 3 2 2 广度优先遍历 这种遍历方式是分层进行的访问。首先访问最高层的节点，在自左向顺序访问邻接层的节 点，商到所有几点都访问完。 3 - 3 3 树节点的特征表示 定义c f t n o d e 类表示故障树的节点：f p u b l i c ： c f t n o d e mp p a r e n t ；树节点的父节点 c f t n o d e + m a ) r i g h t ；树节点的右孩子节点 c f t n o d e * ma a l e t t ；树节点的左孩子节点 p r o t e c t e d ： i mm n p r i m e ；t j 子节点的素数 1 m1 1 1 一n t y p e ；l 类型 c s t r m gm _ s t r n a m e ； c s t r i n gm _ s t r c o n t e n l ； i mn l1 】n u m b e r ；表示节点的唯一序号 河北1 _ 业大学坝1 学位论文 第四章故障树n p 问题的处理 4 - 1 故障树的n p 困难 众所周知，故障树的定性分析首先要求出割集。探测法要把全部n 个底事件的所有可能组合送剑 计算机内的故障树中去探测，能使顶事件发生的就是割集。这种组合有2 ”种，冈此是n p 问题。改_ 上( f ) 行法求全部割集，它考虑到故障树的具体结构，按逻辑门规则和分配率，自r 而上( 或r l 上 而f ) 层层代入和展开。割集数日小丁2 “，绝对数目还是很大。与、或交叉出现时割集总数还可能迅 速增k 。 其次是把求得的割集最小化，即求最小割集。对f 不包含补事件的单调关联故障树这需要通过 布尔吸收运算( 爿u ( 爿n 口) = 爿) ，对全部的割集进行两两比较，总的比较次数为坛m ( m 一1 ) ，m 是 ，l 拿部割照个数。对丁非单调关联故障树，还要找质蕴涵集，计算量更大。 最后就是用最小割集表示故障树，由于这些剖集之间一般有相同底事件，因此是相交的，计算顶 事件概率的时候项数按最小割集的个数而以指数增长。因此除用近似法估计系统故障概率j 二，限 制最小割集阶数或按重要度取近似之外，一般需要把全部最小割集不交化，为此通常用递归算法： c l u c 】c 2 u 五u 【c 3 u 己( c 4 u 娜 ( 4 1 ) 由里向外逐层按分配率展开，并使之最小化，其计算量类似前面分析，也是很人的。 练上所述可见。f t a 实施过程中，在求剖集、最小割集、不交化直到计算顶事什概率等基本步骤 中的计算量是巨人的。故障树的规模通常可以用底事件和逻辑门数目来表征，f t a 的计算量随故障树 规模的加大呈指数增长。 根据计算复杂性理论( i n t r a c t a b i l i t y o f c o m p u t a t i o n ) ，用计算机解数学问题时，首先必须把初始数 据和必要的说明用二进制数表示，这样输入到计算机所需内存单元的数目( 输入长度) ，就叫做问题的 规模，而解题所需求的加、减、乘、除、比较等基本操作的总数。叫做计算量。 所谓多项式算法是对任何规模的问题，计算量 t ( l ) = o ( l 。)( k 为正的常数) ( 4 2 ) 指数算法是指t ( l ) = o ( 2 k l ) ( 4 3 ) 月i 者的计算量随着问题规模的增大旱指数增k ，这就是通常所说的“指数爆炸”问题。所以人们 把指数算法叫做“坏”算法或“慢”算法，而把多项式算法叫做“好”算法或“快”算法。 n p ( n o n d e t e r m i n i s t i cp o l y n o m i a l ) 问题1 0 是说在非确定计算祝 m _ n m a r k = 0 ) w h i l e ( p f t ) p r e o r d e r t r a v e r s e o n 一 m _ p l e f i ) ； p r e o r d e r t r a v e r s e ：( p f t - m j p r i g h t ) ； w h i l e ( p f i - m _ p l e r & p n i n _ p r l g h t ) ( 保证再次访问的廿点是非叶子节点 t r a t r e e 一 v i s i t f t n o d e ( p f i ) ； p f i 一 m _ n m a r k 。1 ： 采刚先序遍历对圈( 4 f 4 ) 所示的例子遍历的节点顺序：( t o p ，g l ，b l ，9 3 ，b 2 ，b 3 ，9 3 ，g l ， 9 3 ，9 4 ，b 4 ，b 5 ，9 4 t9 2 ， f o p ) a 故障树分析箅划、改进酬宄实m 图4 4 一个故障树 f i g 4 4af a u l tt r e e 可以得知故障树中的每个节点至少被遍历两次：第一次是遍历过程中开始遍历节点第一次是由 节点的右孩子返回；叶子节点只遍历一次。可以得知遍历上图是树边数的线性关系。寻找模块的基本 思想：节点是一个模块当且仅当它的任何一个孩子不在第一次访问节点之前被访问并且不在节点第二 次被访问后访问。 1 、g l 不是一个模块因为幻在g l 第二次访问后被访问。 2 、9 2 不是一个模块因为函在9 2 第一次访问之前被访问。 3 、g a 是一个模块因为孩子b 2 和b 3 在是在9 3 第一次访问之后和在9 3 第二次被访问之前被访问。 4 、9 4 是一个模块冈为它的孩子b 4 和b s 是在9 4 第一次被访问后和在9 4 第二次被访问前被访问。 为了得知节点的孩子是否是在节点第一次被访问后和在第二次被访问前被访问需要在c f t n o d e 类 中定义以下变量和函数。 c l a s sc f t n o d e ：p u b l i cc o b j e c t p u b l i c ： v o i dv i s i t f t n o d e ( c f t n o d e + p f l ) ；对节点进行访问； c f t n o d e * mo p a r e n t ；指向父节点的指针； c f t n o d e * m _ p r i g h t ；指向右孩子的指针； c f t n o d e * mo l e f t ；指向左孩子的指针； p r o t e c t e d ： i n tmn m a r k n u m ；标记节点被访问的次数； i n tmn f i r s t v i s i t ；第一次访问节点的次序： i n tmn s e c o n d v i s i t ；第二次访问节点的次序； i n tmn l a s t v i s i t ；， 最后一次访问节点的次序； i n t mn m i n v i s i t ；访问非叶子节点孩子的最小访问值； i n tmn m a x v i s i t ；访问非叶子节点孩子的最大访问值； s t a t i cmn c o u n t ；记录节点访问次序的值一全局变量； b o o lmn m a r k m o d u l a r ；i 置模块标记： b o o lmn m a r k ；节点的所有孩子是否已遍历的标记； 1 8 河北工业大学顶士学位论文 b o o l mn m a r k ；1 y 点的所有孩子是否已遍历的标记； 定义对节点的访问在进行模块化分析时是根关键的，在第一次执行p r e o r d e r t r a v e r s e f t r e e ( ) 时 v i s i t f t n o d e 0 6 7m n m a r k n u m 、m n f i r s t v i s i t 、m n s e c o n d v i s i t 、m _ n l a s t v i s i t 等参数的数值发生变化， 为故障树模块化奠定了基础。如卜就是s i t f l n o d e ( ) 函数中参数改变的算法描述： 首先所有参数清零； v o i dc f t n o d e ：v i s i t f t n o d e ( c f t n o d e + p f 【) p f l 一 i nn c o u n t + + ：节点被访问时，节点的访问次序增加： i f ( p f t 一 m _ n m a r k n u m = = 0 ) p f l - mn f i r s t v i s i t = p f l - mn s e e o n d v i s i t = p f l - m _ n l a s t v i s i t 2m n c o u n t ； 记录节点第一次被访问的次序； p f t 一 m _ n m a r k n u m + + ； j e l s ei f ( p f l 一 m _ n m ”k n u m = = 1 ) p f l m n s e c o n d v i s i t = p f l - m _ n l a s t v i s i m mn c o u n t ；廿点第一二次被访问的次序： p f l - m n m a r k n u m + + ； e l s ei f ( p f t - m n m a r k n m n = 2 ) p f t 一 mn l a s t v i s i t = mn c o u n t ；，记录1 ，点最后一次被访问的次序； p f f - mn m a r k n u m + + ； 遮肌后节点的m n c o u n t 变量值如表( 41 ) 所示表( 4 2 ) 是1 1 1 一n f i r s t v i s i t 、m n s e c o n d v i s i t 、 mn l a 5 t v i s i t 的变量值。进行第二次遍历就需要求出非叶子节点的最小访问值- - m _ n m i n v i s i t 和扎叶子 节点的最大访问值一mn m a x v i s i t 。第二次遍历树算法描述： c f a u l t t r e e ：s e c o n d t r a v e r s e f t r e e ( c f t n o d e f o g e t l e f l c h i l d n o d e ( * p f t ) ；得到节点的最左的孩子节点： s e t m i n v i s i t ( ) ；把求得的孩子的m _ n f i r s t v i s i t 值赋予1 ，点的m _ n m i n v i s i t 变量： g e t l a s t c h i l d n o d e ( t p f t ) ；得到遍历节点的最后的孩子肖点： s e t m a x v i s i t ( ) ；把求得的孩子的m _ l a s w i s i t 值赋予节点的m _ n m a x v i s i t 变量； 判断节点