?
Особый случай классического метода ветвей и границ для задачи коммивояжёра // Вестник Волжской государственной академии водного транспорта
Вестник Волжской государственной академии водного транспорта. 2017. № 49. С. 68–78.
Фомичев М. И.
-
Классический алгоритм, реализующий метод ветвей и границ для решения задачи коммивояжёра, предложенный в 1963 году Дж. Литл, К. Мурти, Д. Суини и К. Кэрол, остаётся по настоящее время самым востребованным алгоритмом при решении задачи нахождения гамильтонового цикла минимальной стоимости в полном графе. Существует много различных источников, в которых представлен псевдокод алгоритма с текстовыми комментариями. Однако в этих источниках не уделяется внимание некоторым особым случаям. Анализу одного из таких особых случаев и посвящена настоящая статья
Жукова Г. Н., Ульянов М. В., , in: Modern Information Technology and IT Education: 12th International Conference, SITITO 2017, Moscow, Russia, November 24–26, 2017, Revised Selected PapersVol. 1204.: Springer, 2021. P. 261–270.
Добавлено: 15 июня 2021 г.
Игнатов А. Д., Andrei Gorchakov, Open Computer Science 2020 Vol. 10 No. 1 P. 112–116
Добавлено: 11 июня 2020 г.
Фомичев М. И., Системы управления и информационные технологии 2017 № 3 С. 88–92
Алгоритм, реализующий метод ветвей и границ для решения задачи коммивояжёра - один из самых востребованных точных алгоритмов её решения. Метаэвристические алгоритмы решения этой задачи не гарантируют точного решения, но работают «быстро». В данной статье рассматривается комбинация таких алгоритмов с методом ветвей и границ. ...
Добавлено: 23 марта 2020 г.
Фомичев М. И., Информационные технологии моделирования и управления 2018 Т. 109 № 1 С. 47–54
В современном мире промедление в секунду, или даже долю секунды, может стоить миллионы рублей. Заинтересованному лицу важно получить точный ответ на вопрос в кратчайшие сроки. Но, к сожалению, даже при ны- нешних вычислительных мощностях, многие задачи не могут быть решены точно за приемлемое время. ...
Добавлено: 22 марта 2020 г.
Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Системы компьютерной математики и их приложения 2017 № 18 С. 136–138
В докладе рассматривается статистическая зависимость числа
порожденных вершин дерева решений и физического времени работы
программной реализации метода ветвей и границ для задачи
коммивояжера (TSP). На основе результатов вычислительного
эксперимента получено приближенное соотношение между числом
порожденных вершин (сложность индивидуальной TSP) и физическим
временем. Предлагается использовать это эмпирическое соотношение
для прогнозирования времени работы программы, решающей TSP с
числом «городов» больше 40. ...
Добавлено: 22 марта 2020 г.
Мищенко Александр Владимирович, Кошелев П. С., Прикладная информатика 2018 № 2 С. 5–21
В статье рассмотрены методы и программные средства оптимизации оптовых закупок. ...
Добавлено: 11 марта 2020 г.
Ульянов М. В., Фомичев М. И., Информационные технологии 2019 Т. 25 № 10 С. 590–595
Алгоритм, реализующий метод ветвей и границ, для решения задачи коммивояжера - один из востребованных точных алгоритмов ее решения. Метаэвристические алгоритмы решения этой задачи не гарантируют получения точного решения, но работают "быстро". Для сокращения числа вершин порожденного дерева решений в методе ветвей и границ можно использовать решение, полученное метаэвристическим алгоритмом. За счет выбора метаэвристического алгоритма и ...
Добавлено: 16 февраля 2020 г.
Фомичев М. И., Ульянов М. В., Информационные технологии 2018 Т. 24 № 11 С. 698–704
Повышение временной эффективности программных реализаций метода ветвей и границ для асимметричной задачи коммивояжера может быть достигнуто как за счет выбора наиболее приемлемой структуры данных, обеспечивающей эффективные по времени операции с листьями поискового дерева решений, так и за счет использования дополнительной памяти для хранения усеченных матриц в листьях поискового дерева решений. Дополнительно могут быть предложены и ...
Добавлено: 26 января 2020 г.
Жукова Г. Н., Ульянов М. В., Фомичев М. И., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054–2067
Добавлено: 24 ноября 2019 г.
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...
Добавлено: 10 ноября 2019 г.
Игнатов А. Д., Посыпкин М. А., Communications in Computer and Information Science 2018 P. 511–522
Добавлено: 18 октября 2019 г.
Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Достаточно часто особенности этих задач приводят к задаче коммивояжера в асимметричной постановке (asymmetric traveling salesman problem, ATSP). Более того, в некоторых практических применениях желательно получение точного решения. Одним из известных ...
Добавлено: 11 декабря 2018 г.