Using a Generalized Statistically Optimal Method of Solution for Minimum Weighted Cover Task
Д.Д. Лапшин, Dmitriy Lapshin, Марина Лапшина, Марина Лапшина, Надежда Юдина, Nadezhda Yudina · Forestry Engineering Journal · 2017
Statistically optimal algorithm for finding minimal cover of 0.1-matrices for the unweighted matrix has been proposed in the works of O. V. German. The algorithm is based on iterative addition of new columns (columns-resolvent)to the matrix, which are built according to the authors' formulated the principle of group resolution (PGR). They have the following property. Under the assumption that optimal cover has not been obtained yet, each such cover contains at least one row from among those that cover the column - resolvent. After adding each new column, considered as a random 0.1-vector, analytical evaluation of mathematical expectation of the number of minimal covers with a given number of rows is made. The evaluation concludes the need to continue the iterations or termination of the algorithm. After evaluation it can be concluded about the necessity to continue the iterations or termination of the algorithm.The algorithm is tested for 600 randomly generated problems with a subsequent comparison with the exact solution. It can be concluded that analytical estimates for mathematical expectation of the number of covers with specified size are stable for matrices of large dimension. On the contrary, with a decrease in the number of columns these estimates become less stable. Doubtless, in our opinion, advantage of this method is its high speed. Thus, in the vast majority of cases, the algorithm concludes by finding the exact solution, which makes to consider it statistically optimal one. The advantage of this method is its speed, but it is empirically proven that increase in the dimension of the problem leads to unpredictable failures.