基于同构子网判定的结点不可靠网络可靠度计算方法

 为提高结点不可靠网络的可靠度计算效率,提出一种基于子网同构判定的高效计算方法。在生成有序二元决策图（OBDD）的因子分解过程中,利用特征合并划分（CMP）识别网络分解产生的同构子网,然后根据网络中边和节点的逻辑联系,执行边替换操作将不可靠结点存储于OBDD;通过遍历OBDD 计算网络的可靠度。结果显示,该方法减少了同构子网带来的重复计算,并充分利用OBDD 的存储结构进一步增强了计算效率,计算中小型网络可靠度的时间保持在100 s 以下,计算数百结点网络可靠度的时间保持在百秒级,且计算中大型网络的开销远低于标准二元决策图（BDD）方法。     

一个计算无圈有向网络可靠度的有效算法

研究了无圈有向网络结点集合的两部分划分(点化分)与极小割集之间的关系·通过对网络结点集合的满足一定条件的两部分点划分,直接得到了网络的极小割集·根据点划分对应结点集合之间的包含关系,提出并证明了网络可靠度的容斥原理表达式中项的几个相消原则;在此基础上建立了一个基于割集的计算无圈有向网络可靠度的容斥原理公式及算法,算法直接给出了容斥原理公式中的所有不相消项;最后,通过例子说明了算法的有效性·     

计算有圈有向网络根通信可靠度的因子分解算法

对有圈有向网络的拓扑结构进行了研究,提出了一个保持网络可靠度不变的缩减规则和因子分解的一个选边规则.由此建立了一个计算有圈有向网络根可靠度的有效算法.算法的时间复杂度是O(N.(|V|+|E|)),其中N是算法所产生二叉树的叶点数,|V|和|E|分别表示网络的节点数和边数.对一些网络进行了计算,结果显示利用该算法计算根通信可靠度所产生的N比其他算法的要小得多,因此,所提算法更有效.     

基于网络缩简的K-剩余连通可靠度的蒙特卡洛方法

讨论了具有不可靠结点网络的可靠度估计问题,提出了具有不可靠结点K-终端网络的串并联缩简原则,并将该缩简原则应用于递归方差衰减(Recursive Variance Reduction,RVR)蒙特卡洛(Monte Carlo)方法中,得到一种无偏且高效的估计可靠度的方法.该方法是依据状态空间分解原理,将对原状态空间的抽样实验递归地转为对其子空间的实验,并且在对子空间抽样实验前进行网络缩简,使得有些子空间不用抽样,对应方差为0.最后,通过实验验证了算法的有效性.     

采用节点流守恒求取多状态网络d-最小路集的改进算法

针对多状态网络可靠度的计算问题,给出一种求解多状态网络d-最小路集的改进算法.引入可行流向量,并将网络中的双向边等效为单向边,使算法对网络中边的容量取值无特殊要求,且可用于含双向边的网络,适用性更强.通过引入边的容量下确界,并将网络中的反向边等效为单向边,减少求取d-最小路集可行解时需枚举的解数目,降低算法复杂度.以多状态网络为例,进行分析验证.结果表明:该算法可以准确得到多状态网络所有d-最小路集.     

基于混合算法的最短路径优化算法

为了解决无向网络的最短路径优化问题,本文采用的是遗传算法和模拟退火算法相结合的思想,阻止早熟现象的发生,保证种群的多样性,防止陷入局部寻优情况的出现,并且定义了无向网络中的结点结构.仿真比较实验说明,混合算法不仅比单一遗传算法运算时间缩短,而且可以找到最短路径,证实了该算法的可行性.     

基于网络简化技术的通风网络可靠度新算法

为了解决在网络可靠度计算中存在运算量过大的问题,利用不交和的原理计算网络的可靠性是当今所有计算网络可靠性方法中最有效的方法之一,但对大型网络依然无法快速确定网络可靠度。针对这一问题,采用直接构造不交化通路集的方法,结合网络简化技术和截断误差理论,提出了一种快速确定大型通风网络可靠度的算法。结果表明:本算法可在24 s内计算出传统算法10 h都无法算出的大型通风网络可靠度问题。该算法对提高大型通风网络可靠度计算速度具有很大作用。     

非电接力格式爆破网络结构分析及可靠性计算

对格式爆破网络的结构进行分析计算，给出了计算网络的结点准爆率和可靠度的有效方法，此法可供大型爆破工程参考应用。     

考虑节点与边失效的网络全端可靠性上界拓展算法

拓展了Jan R H的网络全端可靠性上界。根据网络失效类型(节点自身失效与边失效造成节点孤立的两类网络系统失效状态),给出了节点与边均不可靠的网络系统全端可靠性上界的计算方法。在多项式时间内,该上界计算精度较以往的一个上界算法有显著提高。该上界适用于交通网络、ER随机网络、BA无标度网络等不同网络结构的可靠性评价与可靠性设计。     

基于微粒群优化的贝叶斯网络结构学习方法

建立了一种基于微粒群优化的贝叶斯网络结构学习方法,将贝叶斯网络的结构学习过程转化为对应邻接矩阵的评分寻优问题;将网络节点顺序和节点间因果关系的确定内化于评分寻优过程,避免了算法需要节点有序或事前排序的限制.建立了完整的0-1矩阵微粒群优化计算法则,在网络寻优过程中仅通过改变有向边的方向去除网络中出现的环路,以保证搜索过程中网络结构的完整性.通过ASIA网和CarStart网的数据实验证明了算法的有效性.     

3—状态复杂设备网络可靠度的一个快速算法

本文利用3-状态设备网络可靠度分解定理及保可靠度简化,给出一个计算3-状态有向设备网络可靠度的一个新算法。算法易于计算机上实现。它是文章[2][3]算法在3-状下的拓广。     

基于L形瓦的无向双环网络直径求解算法

针对构造无向双环网络最短路径图(MDD)常用的节点遍历方式较为复杂、割裂了有向双环网络和无向双环网络之间的内在联系的问题,将有向双环网络拓扑结构映射到平面直角坐标系,在得到的L形瓦基础上,对其上的节点坐标通过简单坐标变换,得到无向双环网络MDD上对应节点坐标,进而计算无向双环网络的直径.相对于目前构造无向双环网络MDD或其等价拓扑结构普遍采用节点遍历方式而言,该算法仅增加了几次比较,就改善并提高了无向双环网络直径的求解效率.     

任意无向加权图K点连通扩充的逐次改善算法

为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K 点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明.最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果.为解决任意无向加权图最小扩充问题给出了一种新途径.     

网络可靠度分析的改进最小割递推分解算法

在网络连通可靠度分析的最小割递推分解算法基础上,充分利用分解过程中获得的信息,采用合并节点以及合并并联边的方法,有效地简化了分解出来的子网,大幅度降低了算法分解出来的不交最小割和不交最小路数量,从而大幅度地减少了计算时间.3个网络实例计算分析表明,与最小割递推分解算法相比,改进最小割递推分解算法能更高效地计算得到网络系统的连通可靠度,为生命线工程网络的抗震可靠性提供了1种更加有效的分析工具.     

基于网络缩减的递推分解算法

根据生命线工程网络的特点,介绍了串联边缩减、并联边缩减和源点合并这三种有效的网络缩减规则,并将这些网络缩减规则引入到改进最小路递推分解算法和改进最小割递推分解算法之中,大大简化了上述算法分解出来的子网,减少了网络可靠度分析的复杂程度.实例分析表明,通过引入网络缩减技术,可以有效地降低网络的复杂程度,并能大幅度地提高计算效率.     

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

给出了一种计算网络可靠度的不交和算法,该算法的最大特点是操作简便,易于在计算机上实现,从而适用于大型网络可靠度的计算。     

动态多 DAG 调度的改进算法

工作流调度问题通常可以描述为一个活动与数据传输约束组成的有向无环图（directed acyclic graph,DAG）,基于 Plan-ner-guided 算法框架,采用新的基于多有向无环图节点合并的优先级计算方案改进原有算法,改善了系统中已存在未执行的DAG 结点优先级过小而被滞后的问题,从而使得任务在机器上排布相对比较密集,提升了多个 DAG 结点间调度公平性。结果表明,提出的改进算法优先级计算更加合理,在资源利用率和执行时间上优于 Planner-guided 算法,调度整体性能得到一定提升。     

网络点对连通可靠度的近似计算

通过对无向简单网络中基于任意两点间最小路集和边割集的概率随机事件的定义,利用点对连通可靠度和两终端可靠度的关系,给出了边失效条件下无向简单网络点对连通可靠度的近似计算公式,并给予验证。     

参照零模型的符号社交网络理论研究

 结构平衡理论和地位理论是社交网络领域的重要理论,可以用来分析同时具有正向和负向连边的社交符号网络。提出了3种新的随机断边重连零模型,基于随机断边重连和符号随机置乱两大类零模型,对符号社交网络的地位理论和结构平衡理论进行了系统研究。发现基于零模型不但可以验证两种理论在实证网络中的准确性,还能揭示正边、负边拓扑结构和连边符号相关性对于整个网络性质的影响。提出了一个新框架,研究能否将有向符号网络转化为无向符号网络,发现目前常用的将有向符号网络转化成无向符号网络的方法在有些情况下对于研究社交网络理论是不合适的,存在着信息损失;讨论了非符号有向网络中的势能理论。     

一种指纹的自动识别方法

分析了几种指纹自动识别方法的优缺点，提出了一种新的识别方法，有向图集法，此法中，结点表示指纹中隆线上的分叉点，有向边表示这些分叉之间的关系，此外，还给出了与此有关的２个算法，有向图集的匹配算法及指纹图象的识别算法。