Воронеж, Воронежская область, Россия
Воронеж, Воронежская область, Россия
Воронеж, Воронежская область, Россия
В работах Германа О.В. был предложен статистически оптимальный алгоритм для отыскания минимального покрытия 0,1-матрицы для невзвешенной матрицы. Алгоритм основан на итеративном добавлении к матрице новых столбцов (столбцы-резольвенты), которые строятся согласно сформулированному авторами принципу групповых резолюций (ПГР). Они обладают следующим свойством. В предположении, что еще не получено оптимальное покрытие, каждое такое покрытие содержит как минимум одну строку из числа тех, которые покрывают столбец- резольвенту. После добавления каждого нового столбца, рассматриваемого как случайный 0,1-вектор, производится аналитическая оценка математического ожидания числа минимальных покрытий с заданным количеством строк. По результатам оценки делается вывод о необходимости продолжения итераций или прекращения алгоритма. Алгоритм проверен для 600 случайно сгенерированных задач с последующим сравнением с точным решением. Можно сделать вывод, что аналитические оценки для математического ожидания числа покрытий с заданным размером устойчивы для матриц большой размерности. Напротив, с уменьшением числа столбцов эти оценки менее устойчивы. Несомненное, на наш взгляд, достоинство метода - его высокое быстродействие. Таким образом, в подавляющем большинстве случаев алгоритм завершает работу отысканием точного решения задачи, что позволяет считать его статистически оптимальным. Достоинством метода является его быстродействие, но опытным путем проверено, что увеличение размерности задачи приводит к непрогнозируемым провалам.
матрица, алгоритм, строки, столбцы, веса.
Настоящая статья предлагает статистически оптимальный алгоритм распространить на более общий случай, в котором переменные входят в целевую функцию с произвольными неотрицательными коэффициентами, построенный алгоритм позволяет получить оптимальное решение в большинстве случаев, причем процент задач с точным решением увеличивается с увеличением числа итераций.
1. Герман О.В. Статистически оптимальный алгоритм для задачи о минимальном покрытии / О.В. Герман, В.Г. Найденко // Экономика и мат. методы. - М.: Мир, 2013. Т. 29. Вып. 4. С. 42-48.
2. Пападимитриу X. Комбинаторная оптимизация / X. Пападимитриу, К. Стайглиц - М.: Наука, 2007. - 217 с.
3. Кофман А.А. Методы и модели исследования операций. Целочисленное программирование / А.А. Кофман, А. Анри-Лабордер - М.: Мир, 2012. - 241 с.
4. Балашевич В А. Алгоритмизация математических методов планирования / В. А. Балашевич - Минск: Вышэйш. шк., 2008. -218 с.
5. Ковалев М.М. Дискретная оптимизация / М.М. Ковалев. - Минск: Изд-во Белорус, ун-та, 2007. - 167 с.
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.
