On algorithm for the synthesis of reliable probabilistic networks of minimal complexity (Q2707371)

Some non-oriented nets with \(m\) input poles and \(h\) output poles, i.e. the \((m,n)\)-poles nets, every edge of which belongs to one of non-crossing classes \(K_1,..., K_l\) are considered. It is supposed that the every edge \(u\) of the classe \(K_i\) has a cost \(c_i, c_i>0\) and can be in a conducting state with the probability \(p_i\) and in a non-conducting state with the probability \(q_i=1-p_i\) in spite of states of the other edges. Additionally it is supposed that an every line, connected the two vertex of the \((m,h)\)-poles net \(S\), has at least \(d>2\) edges and it is considered as a conducting one if the every edge of the line is in a conducting state. A complexity of the net is determined as a summary cost all of its edges. Some complexity estimates (including an asymptotic one for the \((1,1)\)-poles net) of a minimal cost net are obtained. Here it was taken into consideration that for any pair ''input-output'' the probability of existence of a conducting line between the input and the output is not less then a given number \(n\) \((0<n<1)\). An algorithm for synthesizing of the minimal \(m,h\)-poles net the complexity of which is depending on a length \(d\) of the net, on the quantity of the poles \(m,h\), on the quantity and the characteristics of the classes \(K_1,..., K_l\), and is not depending on a given reliability \(n\) is presented.