ИСПОЛЬЗОВАНИЕ ОБОБЩЕННОГО СТАТИСТИЧЕСКИ ОПТИМАЛЬНОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ВЗВЕШЕННОМ ПОКРЫТИИ

В работах Германа О.В. был предложен статистически оптимальный алгоритм для отыскания минимального покрытия 0,1-матрицы для невзвешенной матрицы. Алгоритм основан на итеративном добавлении к матрице новых столбцов (столбцы-резольвенты), которые строятся согласно сформулированному авторами принципу групповых резолюций (ПГР). Они обладают следующим свойством. В предположении, что еще не получено оптимальное покрытие, каждое такое покрытие содержит как минимум одну строку из числа тех, которые покрывают столбец- резольвенту. После добавления каждого нового столбца, рассматриваемого как случайный 0,1-вектор, производится аналитическая оценка математического ожидания числа минимальных покрытий с заданным количеством строк. По результатам оценки делается вывод о необходимости продолжения итераций или прекращения алгоритма. Данная оценка базируется на правиле

, устанавливающем вероятность попадания случайной величины с биномиальным законом распределения в интервал, близкой к единице . Алгоритм проверен для 600 случайно сгенерированных задач с последующим сравнением с точным решением. Можно сделать вывод, что аналитические оценки для математического ожидания числа покрытий с заданным размером устойчивы для матриц большой размерности. Напротив, с уменьшением числа столбцов эти оценки менее устойчивы. Несомненное, на наш взгляд, достоинство метода - его высокое быстродействие. Таким образом, в подавляющем большинстве случаев алгоритм завершает работу отысканием точного решения задачи, что позволяет считать его статистически оптимальным. Достоинством метода является его быстродействие, но опытным путем проверено, что увеличение размерности задачи приводит к непрогнозируемым провалам.