|
Дискретный анализ и исследование операций, 2014, том 21, выпуск 3, страницы 64–75
(Mi da776)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Точный алгоритм решения дискретной задачи Вебера для $k$-дерева
А. В. Панюков, Р. Э. Шангин Южно-Уральский гос. университет, пр. Ленина, 76,
454080 Челябинск, Россия
Аннотация:
Рассматривается известная NP-трудная задача размещения взаимосвязанных объектов – дискретная задача Вебера. Предлагается последовательный детерминированный алгоритм, находящий точное решение задачи для $k$-дерева и конечного множества позиций размещения. Алгоритм использует идею динамического программирования на основе дерева декомпозиции. Проведён вычислительный эксперимент по анализу эффективности предложенного алгоритма в сравнении с пакетом IBM ILOG CPLEX. Ил. 2, библиогр. 23.
Ключевые слова:
задача Вебера, $k$-дерево, динамическое программирование, дерево декомпозиции, точный алгоритм.
Статья поступила: 03.09.2013 Переработанный вариант: 31.01.2014
Образец цитирования:
А. В. Панюков, Р. Э. Шангин, “Точный алгоритм решения дискретной задачи Вебера для $k$-дерева”, Дискретн. анализ и исслед. опер., 21:3 (2014), 64–75
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da776 https://www.mathnet.ru/rus/da/v21/i3/p64
|
Статистика просмотров: |
Страница аннотации: | 503 | PDF полного текста: | 197 | Список литературы: | 56 | Первая страница: | 22 |
|