计算网络s-t可靠性的直接不交界限值算法

被引：3

作者：

侯本伟 ^{[1
]}

王威 ^{[1
,2
]}

苏经宇 ^{[1
,2
]}

周锡元 ^{[1
]}

机构：

[1] 北京工业大学建筑工程学院

[2] 北京工业大学建筑与城市规划学院

来源：

北京工业大学学报 | 2013年 / 39卷 / 04期

关键词：

大型网络; 可靠性; 直接不交化算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论]; O157.5 [图论];

学科分类号：

081202 ; 070104 ;

摘要：

网络两端可靠性的精确求解属于NP困难问题,对于规模较大的工程网络,求解过程非常耗时.可行的办法是采用满足实际精度要求的近似算法,其中利用两端界限逼近求解的方法是一类较为有效的近似算法.提出了一种可利用界限求解的直接不交化算法.算法可直接生成不交最小路集和不交最小割集,并实时逼近网络可靠性的真实解,可在有限计算时间内求出小型网络可靠性的精确解或大型复杂网络可靠性的近似解.与改进Dotson算法相比,此算法可更快地求解单元处于低可靠度状态时的网络两端连通可靠性;与最小割递推分解算法相比,此算法可得到较优不交解集.

引用

页码：500 / 506

页数：7

共 7 条

[1] 基于网络缩减的递推分解算法 [J].