Задача выбора пропускных способностей дуг с ограничением на время задержки потоков

• Опубліковано в: : Кибернетика и системный анализ
• Дата: 2019
• Автори: Трофимчук, А.Н., Васянин, В.А.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
• Теми: Системний аналіз
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/181010
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Задача выбора пропускных способностей дуг с ограничением на время задержки потоков / А.Н. Трофимчук, В.А. Васянин // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 50-60 . — Бібліогр.: 20 назв. — рос.

Рассмотрена задача выбора пропускных способностей дуг из заданного набора, актуальная при распределении потоков в многопродуктовых коммуникационных сетях с ограничением на время задержки потоков. Доказано, что такая задача является NP-трудной. Приведены алгоритмы приближенного решения задачи и результаты их экспериментального сравнения с точным переборным алгоритмом на основе генерации последовательности двоично-отраженных кодов Грея. Отмечено, что получение точного решения возможно с использованием псевдополиномиальных алгоритмов для 0–1 задачи о ранце с мультивыбором. Розглянуто задачу вибору пропускних спроможностей дуг із заданого набору, актуальну для розподілу потоків в багатопродуктових комунікаційних мережах з обмеженням на час затримки потоків. Доведено, що така задача є NP-складною. Наведено алгоритми наближеного розв’язання задачі та результати їхнього експериментального порівняння з точним переборним алгоритмом на основі генерації послідовності двійково-відображених кодів Грея. Відзначено, що отримання точного розв’язку можливо з використанням псевдополіноміальних алгоритмів для 0–1 задачі про ранець з мультивибором The authors consider the problem of choosing the capacity arcs from a given set, which is important in flow distribution in multicommodity communication networks with constraint on flow delay time. It is proved that such problem is NP-hard. The algorithms for the approximate solution of the problem and results of heir experimental comparison with exact algorithm based on generating a sequence of binary reflected Gray codes are given. It is noted that obtaining an exact solution is possible with the use of pseudopolynomial algorithms for the 0–1 Multiple-choice Knapsack Problem.