Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа/ Probability distribution of the complexity of the individual traveling salesman problem (fixed number of nodes)

Головешкин В. А.; Жукова Г. Н.; М. В. Ульянов; М. И. Фомичев

?

Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа/ Probability distribution of the complexity of the individual traveling salesman problem (fixed number of nodes)

С. 304–310.

Головешкин В. А., Жукова Г. Н., Ульянов М. В., Фомичев М. И.

На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности.

Язык: русский

Полный текст

Текст на другом сайте

Ключевые слова: метод ветвей и границ задача коммивояжера Traveling Salesman Problem branch and bound method

В книге

CEUR Workshop Proceedings

Vol. 1761: SITITO 2016. Modern Information Technologies and IT-Education. Selected Papers of the XI International Scientific-Practical Conference Modern Information Technologies and IT-Education (SITITO 2016). Moscow, Russia, November 25-26, 2016. , CEUR Workshop Proceedings, 2016.

The Estimation of the Individual Travelling Salesman Problem Complexity Extreme Values

Жукова Г. Н., Ульянов М. В., , 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 г.

Tool for Simulating Branch and Bound Computations

Игнатов А. Д., 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 г.

Коррeляция сложности и времени решения TSP

Головешкин В. А., Жукова Г. Н., Ульянов М. В. и др., Системы компьютерной математики и их приложения 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 г.

A Hybrid Exact Algorithm for the Asymmetric Traveling Salesman Problem: Construction and a Statistical Study of Computational Efficiency

Жукова Г. Н., Ульянов М. В., Фомичев М. И., Automation and Remote Control 2019 Vol. 80 No. 11 P. 2054–2067

Добавлено: 24 ноября 2019 г.

Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности

Жукова Г. Н., Ульянов М. В., Фомичев М. И., Автоматика и телемеханика 2019 № 11 С. 155–172

Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin- Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного ...

Добавлено: 10 ноября 2019 г.

BOINC-based Branch-and-Bound

Игнатов А. Д., Посыпкин М. А., Communications in Computer and Information Science 2018 P. 511–522

Добавлено: 18 октября 2019 г.

Эффективный по времени точный комбинированный алгоритм для асимметричной задачи коммивояжера

Жукова Г. Н., Ульянов М. В., Фомичев М. И., Бизнес-информатика 2018 Т. 45 № 3 С. 20–28

Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Достаточно часто особенности этих задач приводят к задаче коммивояжера в асимметричной постановке (asymmetric traveling salesman problem, ATSP). Более того, в некоторых практических применениях желательно получение точного решения. Одним из известных ...

Добавлено: 11 декабря 2018 г.