доктор технических наук;
doctor of technical sciences;
кандидат технических наук;
candidate of technical sciences;
В работах Германа О.В. был предложен статистически оптимальный алгоритм для отыскания минимального покрытия 0,1-матрицы для невзвешенной матрицы. Алгоритм основан на итеративном добавлении к матрице новых столбцов (столбцы-резольвенты), которые строятся согласно сформулированному авторами принципу групповых резолюций (ПГР). Они обладают следующим свойством. В предположении, что еще не получено оптимальное покрытие, каждое такое покрытие содержит как минимум одну строку из числа тех, которые покрывают столбец- резольвенту. После добавления каждого нового столбца, рассматриваемого как случайный 0,1-вектор, производится аналитическая оценка математического ожидания числа минимальных покрытий с заданным количеством строк. По результатам оценки делается вывод о необходимости продолжения итераций или прекращения алгоритма. Алгоритм проверен для 600 случайно сгенерированных задач с последующим сравнением с точным решением. Можно сделать вывод, что аналитические оценки для математического ожидания числа покрытий с заданным размером устойчивы для матриц большой размерности. Напротив, с уменьшением числа столбцов эти оценки менее устойчивы. Несомненное, на наш взгляд, достоинство метода - его высокое быстродействие. Таким образом, в подавляющем большинстве случаев алгоритм завершает работу отысканием точного решения задачи, что позволяет считать его статистически оптимальным. Достоинством метода является его быстродействие, но опытным путем проверено, что увеличение размерности задачи приводит к непрогнозируемым провалам.
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.
Настоящая статья предлагает статистически оптимальный алгоритм распространить на более общий случай, в котором переменные входят в целевую функцию с произвольными неотрицательными коэффициентами, построенный алгоритм позволяет получить оптимальное решение в большинстве случаев, причем процент задач с точным решением увеличивается с увеличением числа итераций.