|
Информация о статье
2015 г., Том 20, № 6, с.72-86
Пролубников А.В.
Задача о покрытии множества с интервальными весами подмножеств и жадный алгоритм ее решения
Рассматривается задача о покрытии множества с интервальными весами подмножеств. Представлены варианты определения слабого и сильного оптимальных решений задачи, объединенного оптимального решения. Доказывается теорема о характеризации сильного оптимального решения. Представлена модификация жадного алгоритма нахождения приближенного решения задачи, определяемого в работе. Рассматриваются вычислительная сложность представленного алгоритма и точность получаемых приближенных решений задачи.
[полный текст]
Ключевые слова: задача о покрытии множества, интервальная неопределенность, жадный алгоритм
Библиографическая ссылка:
Пролубников А.В. Задача о покрытии множества с интервальными весами подмножеств и жадный алгоритм ее решения // Вычислительные технологии. 2015. Т. 20. № 6. С. 72-86
|
|
|
|
