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

doi:10.17223/20710410/45/12

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Задача коммивояжера: приближенный алгоритм по методу ветвей и границ с гарантированной точностью	587 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/45/12

#задача коммивояжера

#приближенные алгоритмы

#метод ветвей и границ

#локальный поиск

#вычислительные эксперименты

Title: Задача коммивояжера: приближенный алгоритм по методу ветвей и границ с гарантированной точностью
Title: The traveling salesman problem: approximate algorithm by branch-and-bound method with guaranteed precision
Creator: Костюк, Юрий Леонидович
Date: 2019
DOI: 10.17223/20710410/45/12
Description: Для решения задачи коммивояжёра с матрицей расстояний порядка n предлагается приближённый алгоритм на основе метода ветвей и границ. Для отсечения используется увеличенная оценка снизу текущего частичного решения, гарантирующая заранее заданную величину е погрешности всего решения. Проведён вычислительный эксперимент для матриц расстояний четырёх видов распределений, среди них для равномерного случайного (несимметричного) распределения, а также для матриц евклидовых расстояний между случайными точками (симметричного распределения). В последнем случае дополнительно применён локальный поиск. Получены оценки степени p для функции полиномиальной трудоёмкости O(np) для разных видов распределений и различных величин погрешности е. Для равномерного случайного распределения полученная оценка степени p оказалась близка к 2,8 в диапазоне n до 1000 и средней погрешности около 1 %.