论文部分内容阅读
在科学技术日新月异的今天,人类的发展进程正在大跨步前进。与此同时,世界范围内生产生活的举动也在随着科技的进步而加快频率。伴随着全球生产力的提升,人类的交流活动以及各系统性工程都在以一个个网络的形式急速运行着,因此对于各种网络的可靠性分析对于当今人类的生活有发展有着重要的意义。对于网络的可靠性研究目前是一个热点。二分决策图技术(BDD)就是研究方法中非常著名的一种。该分析方法的操作过程是首先对于网络中的变量进行边排序,然后生成等价BDD,最后对生成的BDD进行可靠度的计算。在使用BDD分析方法进行网络进行可靠度计算时,计算过程的工作效率与生成的等价BDD规模直接相关。大规模的BDD会导致计算效率降低,时效性很差。因此使用与原网络等价的小规模的BDD进行计算,在网络可靠性分析工作中是非常有必要的。在生成等价BDD时,我们总需要选择一个边排序初始点。不同的边排序初始点排序后生成的BDD规模可能存在巨大的差别,生成BDD的规模越小的边排序初始点其性能越好。因此,如何选择规模小的BDD进行网络可靠性计算问题就等价为了如何找出高性能的边排序初始点以得到规模小的等价BDD问题。在目前的网络可靠性BDD计算中,提升算法的计算效率非常重要。本文针对与计算效率直接相关的高性能的边排序初始点做了一些研究工作,具体的内容如下所述：(1)对于不同的工程网络,以及不同的K节点子集,将网络中所有的节点作为边排序初始点生成BDD。研究高性能的边排序初始点的变化情况与其分布特征。在不同的K节点子集情况下,高性能边排序初始点始终保持不变,得出结论一：高性能边排序初始点自身具有稳定性。并且在将高性能边排序初始点标注在网络分区中时,这些节点都落在一个分区内,得出结论二：高性能边排序初始点具有汇聚性。(2)提出工程网络中高性能边排序初始点的选择方法。首先基于网络中节点介数进行网络分区操作,在此给出了划分点的定义和选取规则；然后在所得不同网络分区中选择节点对比排序性能,找出高性能边排序初始点所在的网络分区。在对工程网络进行网络分区的操作时,必须选择合适的介数阈值以确定划分点。选取多个实际工程网络进行实验,实验结果表明,此方法具有可操作性与指导意义。(3)不同的排序策略在对工程网络中所有节点的遍历方式上是不同的。策略不同时,同一个初始点生成的BDD规模可能相差巨大。对于不同的排序策略下的高性能边排序初始点的分布特征和稳定性进行了对比。得出在常用的BFS策略中,高性能边排序初始点依然具有较强的稳定性和汇聚性,为其他可用策略下的高性能边排序初始点的选择提供了一定的参考。综上所述,本文就如何选择规模小的等价BDD以提升工程网络可靠性计算效率,对工程网络中的边排序初始点的分布进行了研究工作,得出了高性能边排序初始点的分布特征。并且在此研究基础上给出了工程网络中高性能边排序初始点的选择方法。最后就Snooker策略与BFS策略下高性能边排序初始点的分布特征进行比较,为其他可用策略的边排序研究工作提供一定参考。