The Research On Searching For Minimal Path Sets Vectors D-MP In The Multistate Networks

Today in the rapid development of science and technology in modern war are already out of the stage at which individual against individual weapons,into the confrontation stage between the weapon systems and between the equipment systems,the future war is present characteristics of the confrontation between the smart weapons in swarm operation or the network systems.Network system is a common and effective model for the modeling of such complex systems.For complex network systems,it is not only assumed that the component in a system can only be in two possible states,completely working or totally failed,but also require that the networks can transmit a certain amount of traffic.Such networks called multistate networks.In order to improve the reliability of the network and to ensure the stable operation of the network,the commander or manager has taken the network reliability as an important index of evaluation for the network capacity reliability in the process of design,construction,operation and maintenance.However,the constant growth of network scale and complexity makes it very difficult to solve the reliability of multi-state networks.The solution time of network reliability increases exponentially with the increase of network scale.Therefore,it is a difficult problem to develop more efficient algorithms to calculate the reliability of multistate networks.Therefore,the paper focused on improving the reliability assessment efficiency of multistate network.In this paper,the search algorithm of the path set vector based on the minimum path set vector(d-MP for short)is studied,and the main contents are as follows:Firstly,this paper studies the mechanism on generating duplicated d-MP candidates in the process of searching for the d-MP based on the minimal path sets(MPs for short).The paper summarizes the reasons for the duplications of 2-MP candidates in the search process,and then explores the reasons for the duplications of d-MP candidates when the demand value d is greater than 2,and the relationship between the number of duplicated 2-MP candidates generation and the network structure is analyzed.Secondly,we studied the efficiency of algorithm that searches for d-MP with specific d value,and we get the conclusion about the reason of generating on duplications.We also proposed the constraint c_a in combination with the analysis in the third chapter.By the efficiency contrast experiment,the proposed algorithm can avoid the appearance of duplicated candidate d-MP.At the same time,this paper proposed the improved the constraint c_i' based on the insufficiency of the original algorithm in the constraint c_i.After two steps of improvement,the proposed algorithm in this paper greatly improved the efficiency of searching for d-MP in the specific demand d.Finally,we analyzed the recursive search algorithm of searching for all d-MPs for all d levels in multistate two-terminal networks,and a novel approach is incorporated into the existing algorithm to generate the d-MPs without duplications.The generation of duplicated d-MP is avoided completely based on the constraint for the order of MPs.By the efficiency contrast experiment,the effectiveness of the new method and the no-duplications mechanism is verified.