二元决策图的排序优化及故障树转化方法的研究

论文摘要

随着计算机软硬件系统日益复杂,保证系统的正确性和可靠性日显重要,为此提出的许多理论和方法中,模型检测以其简洁明了和自动化程度高而引人注目。论文介绍了二元决策图的基本原理与研究现状,针对影响二元决策图结构的因素——变量排序进行了深入分析;给出了节点规模优化的排序算法的改进思想;研究了利用动态交换来完成路径数量优化的方法,提出了OSMNP排序优化算法。该算法通过对节点路径的定义和记录,实现了在变量交换中局部路径改变量向全局改变量的转移,从而实现路径数量的优化。论文还研究了基于二元决策图的故障树分析的排序和转化问题,提出一种快速有效的LNPC方法,该方法采用逐渐分解的策略直接完成子事件的排序与组合,一次性地实现故障树到二元决策图的转化与优化,并通过实例验证了其有效性。OSMNP算法利用相邻变量交换的有效性能获取最少路径的排序;LNPC算法通过按定义的规则遍历故障树不仅完成底事件的优化排序,同时也有效地实现了故障树向二元决策图的转化,这些研究成果对二元决策图应用的深入有较好的理论意义和一定的实用价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 研究内容
• 1.4 论文组织结构
• 第二章 二元决策图的基本原理
• 2.1 二元决策图的基本概念
• 2.2 二元决策图的基本操作
• 2.3 二元决策图结构优化与扩展
• 2.5 本章总结
• 第三章 二元决策图的排序优化
• 3.1 BDD结构与排序
• 3.2 BDD节点数量排序优化
• 3.2.1 精确排序算法
• 3.2.2 动态启发式排序
• 3.2.3 筛选算法的改进
• 3.3 BDD路径数量排序优化
• 3.3.1 BDD节点路径的记录
• 3.3.2 BDD节点路径改变量的传递
• 3.3.3 最少路径排序优化算法
• 3.3.4 OSMNP算法试验结果与分析
• 3.4 本章小结
• 第四章 LNPC故障树的转化
• 4.1 故障树的概念和特点
• 4.2 故障树与 BDD
• 4.3 故障树向BDD的转化方法
• 4.4 故障树中底事件的排序
• 4.4.1 底事件顺序影响 BDD规模
• 4.4.2 结构重要度排序
• 4.5 LNPC转化方法
• 4.5.1 LNPC方法的概念描述
• 4.5.2 LNPC排序策略
• 4.5.3 LNPC的组合方法
• 4.5.4 LNPC方法的实现
• 4.5.5 LNPC实现实例
• 4.5.6 LNPC的算法分析
• 4.6 本章小结
• 第五章 结论
• 5.1 工作总结
• 5.2 研究展望
• 参考文献
• 致谢
• 攻读学位期间主要的研究成果