Предлагается детерминированный квазиполиномиальный алгоритм, находящий точное решение задачи Вебера в дискретной постановке для п-последовательно-связной цепи и конечного множества позиций размещения, основанный на динамическом программировании. Дан теоретический анализ предложенного алгоритма. Проведен вычислительный эксперимент по анализу эффективности предложенного алгоритма в сравнении с пакетом IBM ILOG CPLEX.
Скачать электронную версию публикации
Загружен, раз: 203
- Title Точный алгоритм для решения одного частного случая задачи Вебера в дискретной постановке
- Headline Точный алгоритм для решения одного частного случая задачи Вебера в дискретной постановке
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 6 (Приложение)
- Date:
- DOI
Ключевые слова
задача Вебера, п-последовательносвязная цепь, динамическое программирование, точный алгоритм, квазиполиномиальный алгоритм, Weber problem, n-sequentially connected chain, dynamic programming, exact algorithm, quasi-polynomial algorithmАвторы
Ссылки
Panyukov А. V. and Pelzwerger B. V. Polynomial algorithms to finite Veber problem for a tree network // J. Comput. Appl. Math. 1991. V.35. P. 291-296.
Шангин Р. Э. О некоторых свойствах n-последовательносвязной цепи // Вестник ЮУрГУ. Сер. Вычислительная математика и информатика. 2013. Т. 2. №1. С. 106-113.
Панюков А. В. Модели и методы решения задач построения и идентификации геометрического размещения: дис.. докт. физ.-мат. наук. М., 1999.
Забудский Г. Г., Филимонов Д. В. Решение дискретной минимаксной задачи размещения на сети // Изв. вузов. Математика. 2004. №5. С. 33-36.
Трубин В. А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой // Кибернетика. 1978. №6. С. 67-70.
Точный алгоритм для решения одного частного случая задачи Вебера в дискретной постановке | Прикладная дискретная математика. 2013. № 6 (Приложение).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 1887