Voronezh, Voronezh, Russian Federation
Voronezh, Voronezh, Russian Federation
Voronezh, Voronezh, Russian Federation
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.
matrix, algorithm, rows, columns, weight.
Настоящая статья предлагает статистически оптимальный алгоритм распространить на более общий случай, в котором переменные входят в целевую функцию с произвольными неотрицательными коэффициентами, построенный алгоритм позволяет получить оптимальное решение в большинстве случаев, причем процент задач с точным решением увеличивается с увеличением числа итераций.
1. German O.V. Statisticheski optimal'nyy algoritm dlya zadachi o minimal'nom pokrytii [A statistically optimal algorithm for the minimal covering problem] // O.V. Herman, V.G. Naidenko /Economics and Math. Methods. - M .: Mir, 2013. T. 29. Issue. 4. pp. 42-48. (In Russian).
2. Papadimitriou X. Kombinatornaya optimizatsiya [Combinatorial optimization] / X. Papadimitriou, K. Staiglitz - Moscow: Nauka, 2007. - 217 p. (In Russian).
3. Kofman AA Metody i modeli issledovaniya operatsiy. Tselochislennoye programmirovaniye [Methods and models of operations research. Integer Programming] / A.A. Kofman, A. Henri-Laborder - M .: Mir, 2012. - 241 p. (In Russian).
4. Balashevich V A. Algoritmizatsiya matematicheskikh metodov planirovaniya [Algorithmization of mathematical methods of planning] / VA Balashevich-Minsk: Vysheish. Shk., 2008. -218 s. (In Russian).
5. Kovalev M.M. Diskretnaya optimizatsiya [Discrete optimization]. Kovalev. - Minsk: Belarusian Publishing House, University, 2007. - 167 p. (In Russian).
6. Lee D.T., Wu Y.F. Geometric complexity of some location problems, Algorithmica, 1 / D.T. Lee, Y.F. Wu. 1986. - p. 193-211.
7. McCreiqht E.M., van Wyk C.J. An O(n loglog n)-time algorithm for triangulating a simple polygon / E.M. McCreiqht, C.J. van Wyk // SIAM J. Comput., 17 - 1988. - p. 143-178.
8. Chazelle B.M., Edelsbrunner H. An optimal algorithm for intersecting line segments, manuscript / B.M. Chazelle, H. Edelsbrunner. - 2008. - 83 p.
9. Samuelson P.A. Abstract of a theorem concerning substituatability in open Leontief models / P.A. Samuelson. - I.: Collected Scientific papers, MIT Press, 2016. - pp. 36-44.
10. Zadeh L.A. Linear system Theory / L.A. Zadeh, C.A. Desoer // The State Space Approach, McGraw-Hill, N.Y., 1983. - p.p. 84-92.
