Информация о статье
2017 г., Том 22, № 2, с.115-126
Пролубников А.В.
Об одном подходе к решению задачи о покрытии с интервальными весами и его вычислительной сложности
Рассмотрена задача о покрытии множества с интервальными весами подмножеств. Решение задачи основано на получении множества приближенных решений для всех возможных весов из заданных интервалов - объединенного приближенного множества решений задачи. Такой подход использует модификацию жадного алгоритма для решения задачи о покрытии на случай интервальных весов. Количество приближенных решений, содержащихся в объединенном приближенном решении, определяет вычислительную сложность его нахождения. Показано, что зависимость вычислительной сложности предложенного подхода от радиусов интервалов весов множеств является неубывающей кусочно-постоянной функцией. Приведен пример приложения подхода к решению задачи формирования рейсов для сети железных дорог при неопределенностях в стоимостях обслуживания рейсов. В заключение работы ставится задача коррекции численно неразрешимых задач о покрытии с интервальными весами.
[полный текст] Ключевые слова: задача о покрытии множества, интервальная неопределенность, вычислительная сложность
Библиографическая ссылка: Пролубников А.В. Об одном подходе к решению задачи о покрытии с интервальными весами и его вычислительной сложности // Вычислительные технологии. 2017. Т. 22. № 2. С. 115-126
|
|
|