|
|
Дискретн. анализ и исслед. опер., 2014, том 21, номер 3, страницы 64–75
(Mi da776)
|
 |
|
 |
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Точный алгоритм решения дискретной задачи Вебера для $k$-дерева
А. В. Панюков, Р. Э. Шангин
Южно-Уральский гос. университет, пр. Ленина, 76,
454080 Челябинск, Россия
Аннотация:
Рассматривается известная NP-трудная задача размещения взаимосвязанных объектов – дискретная задача Вебера. Предлагается последовательный детерминированный алгоритм, находящий точное решение задачи для $k$-дерева и конечного множества позиций размещения. Алгоритм использует идею динамического программирования на основе дерева декомпозиции. Проведён вычислительный эксперимент по анализу эффективности предложенного алгоритма в сравнении с пакетом IBM ILOG CPLEX. Ил. 2, библиогр. 23.
Ключевые слова:
задача Вебера, $k$-дерево, динамическое программирование, дерево декомпозиции, точный алгоритм.
 Полный текст:
PDF файл (285 kB)
Список литературы:
PDF файл
HTML файл
Реферативные базы данных:
Тип публикации:
Статья
УДК:
519.863
Статья поступила: 03.09.2013
Переработанный вариант: 31.01.2014
Образец цитирования:
А. В. Панюков, Р. Э. Шангин, “Точный алгоритм решения дискретной задачи Вебера для $k$-дерева”, Дискретн. анализ и исслед. опер., 21:3 (2014), 64–75
Цитирование в формате AMSBIB
\RBibitem{PanSha14}
\by А.~В.~Панюков, Р.~Э.~Шангин
\paper Точный алгоритм решения дискретной задачи Вебера для $k$-дерева
\jour Дискретн. анализ и исслед. опер.
\yr 2014
\vol 21
\issue 3
\pages 64--75
\mathnet{http://mi.mathnet.ru/da776}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3242102}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da776 http://mi.mathnet.ru/rus/da/v21/i3/p64
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Р. Э. Шангин, “Точный и эвристический алгоритмы решения дискретной задачи Вебера для простого цикла”, Вестн. НГУ. Сер. матем., мех., информ., 14:2 (2014), 98–107
 -
А. В. Панюков, Р. Э. Шангин, “Алгоритм с оценкой точности для дискретной задачи Вебера”, Автомат. и телемех., 2016, № 7, 103–112
 ; A. V. Panyukov, R. E. Shangin, “Algorithm for the discrete Weber's problem with an accuracy estimate”, Autom. Remote Control, 77:7 (2016), 1208–1215   -
Г. Г. Забудский, Т. И. Кейнер, “Оптимизация размещения прямоугольников на плоскости с фиксированными объектами”, Автомат. и телемех., 2017, № 9, 131–144 ; G. G. Zabudskii, T. I. Keiner, “Optimal placement of rectangles on a plane with fixed objects”, Autom. Remote Control, 78:9 (2017), 1651–1661
|
| Просмотров: |
| Эта страница: | 372 | | Полный текст: | 85 | | Литература: | 45 | | Первая стр.: | 22 |
|
Пользовательское соглашение