RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2019, номер 45, страницы 104–112 (Mi pdm677)  

Вычислительные методы в дискретной математике

Задача коммивояжёра: приближённый алгоритм по методу ветвей и границ с гарантированной точностью

Ю. Л. Костюк

Национальный исследовательский Томский государственный университет, г. Томск, Россия

Аннотация: Для решения задачи коммивояжёра с матрицей расстояний порядка $n$ предлагается приближённый алгоритм на основе метода ветвей и границ. Для отсечения используется увеличенная оценка снизу текущего частичного решения, гарантирующая заранее заданную величину $\varepsilon$ погрешности всего решения. Проведён вычислительный эксперимент для матриц расстояний четырёх видов распределений, среди них для равномерного случайного (несимметричного) распределения, а также для матриц евклидовых расстояний между случайными точками (симметричного распределения). В последнем случае дополнительно применён локальный поиск. Получены оценки степени $p$ для функции полиномиальной трудоёмкости $O(n^p)$ для разных видов распределений и различных величин погрешности $\varepsilon$. Для равномерного случайного распределения полученная оценка степени $p$ оказалась близка к $2{,}8$ в диапазоне $n$ до $1000$ и средней погрешности около $1 %$.

Ключевые слова: задача коммивояжёра, метод ветвей и границ, приближённый алгоритм, локальный поиск, вычислительный эксперимент.

Финансовая поддержка Номер гранта
Министерство образования и науки Российской Федерации 2.4218.2017/4.6
Результаты получены в рамках выполнения госзадания Минобрнауки России, проект № 2.4218.2017/4.6.


DOI: https://doi.org/10.17223/20710410/45/12

Полный текст: PDF файл (613 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.7

Образец цитирования: Ю. Л. Костюк, “Задача коммивояжёра: приближённый алгоритм по методу ветвей и границ с гарантированной точностью”, ПДМ, 2019, № 45, 104–112

Цитирование в формате AMSBIB
\RBibitem{Kos19}
\by Ю.~Л.~Костюк
\paper Задача коммивояжёра: приближённый алгоритм по методу ветвей и границ с гарантированной точностью
\jour ПДМ
\yr 2019
\issue 45
\pages 104--112
\mathnet{http://mi.mathnet.ru/pdm677}
\crossref{https://doi.org/10.17223/20710410/45/12}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm677
  • http://mi.mathnet.ru/rus/pdm/y2019/i3/p104

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:60
    Полный текст:11
    Литература:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020