Search for d-MPs without duplicates in two-terminal multistate networks based on MPs  

作　　者：XU Bei FANG Yining BAI Guanghan ZHANG Yun’an TAO Junyong 

机构地区：[1]Laboratory of Science and Technology on Integrated Logistics Support,College of Intelligent Sciences and Technology,National University of Defense Technology,Changsha 410073,China [2]School of General Aviation,Nanchang Hangkong University,Nanchang 330063,China

出　　处：《Journal of Systems Engineering and Electronics》2022年第6期1332-1341,共10页系统工程与电子技术（英文版）

基　　金：supported by the National Natural Science Foundation of China(71701207);the Science and Technology on Reliability&Environmental Engineering Laboratory(6142004004-2);the Science and Technology Commission of the CMC(2019-JCJQ-JJ-180)。

摘　　要：The reliability evaluation of a multistate network is primarily based on d-minimal paths/cuts(d-MPs/d-MCs).However,being a nondeterminism polynomial hard(NP-hard)problem,searching for all d-MPs is a rather challenging task.In existing implicit enumeration algorithms based on minimal paths(MPs),duplicate d-MP candidates may be generated.An extra step is needed to locate and remove these duplicate d-MP candidates,which costs significant computational effort.This paper proposes an efficient method to prevent the generation of duplicate d-MP candidates for implicit enumeration algorithms for d-MPs.First,the mechanism of generating duplicate d-MP candidates in the implicit enumeration algorithms is discussed.Second,a direct and efficient avoiding-duplicates method is proposed.Third,an improved algorithm is developed,followed by complexity analysis and illustrative examples.Based on the computational experiments comparing with two existing algorithms,it is found that the proposed method can significantly improve the efficiency of generating d-MPs for a particular demand level d.

关 键 词：RELIABILITY multistate network d-minimal path(d-MP) DUPLICATE 

分 类 号：O157.5[理学—数学]