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

Directly Disjoint Algorithm for Network s-t Reliability Evaluation

作　　者：侯本伟[1] 王威[1,2] 苏经宇[1,2] 周锡元[1] 

机构地区：[1]北京工业大学建筑工程学院,北京100124 [2]北京工业大学建筑与城市规划学院,北京100124

出　　处：《北京工业大学学报》2013年第4期500-506,共7页Journal of Beijing University of Technology

基　　金：国家科技支撑计划项目(2009BAJ28B04-02);国家自然科学基金资助项目(51208017)

摘　　要：网络两端可靠性的精确求解属于NP困难问题,对于规模较大的工程网络,求解过程非常耗时.可行的办法是采用满足实际精度要求的近似算法,其中利用两端界限逼近求解的方法是一类较为有效的近似算法.提出了一种可利用界限求解的直接不交化算法.算法可直接生成不交最小路集和不交最小割集,并实时逼近网络可靠性的真实解,可在有限计算时间内求出小型网络可靠性的精确解或大型复杂网络可靠性的近似解.与改进Dotson算法相比,此算法可更快地求解单元处于低可靠度状态时的网络两端连通可靠性;与最小割递推分解算法相比,此算法可得到较优不交解集.The evaluation of source to terminal （s-t） reliability of a network is classed in the NP hard family. The exact computation method of large networks is extremely time-consuming. Therefore, approximate computation methods are generally used. One feasible approximation approach is to use bounds. This paper proposes a directly disjoint algorithm using bounds for s-t reliability evaluation of large networks. This algorithm can obtain disjoint minimal path and disjoint minimal cut without prior enumeration of minimal path or minimal cut. On the principle of breadth-first search and minimal- distance-first search, the algorithm can get exact solution of simple networks and approximation of large networks with real-time accumulation of disjoint minimal paths and cuts. Compared with the modified Dotson algorithm, this algorithm is faster in solving the reliability of large network with low element operation probability. Compared with the minimal cut-based recursive decomposition algorithm, a more optimum disjoint set can be obtained by this algorithm.

关 键 词：大型网络 可靠性 直接不交化算法 

分 类 号：TU991.33[建筑科学—市政工程]