Задача коммивояжера: приближенный алгоритм по методу ветвей и границ с гарантированной точностью Ю. Л. Костюк
Material type: ArticleOther title: The traveling salesman problem: approximate algorithm by branch-and-bound method with guaranteed precision [Parallel title]Subject(s): задача коммивояжера | приближенные алгоритмы | метод ветвей и границ | локальный поиск | вычислительные экспериментыGenre/Form: статьи в журналах Online resources: Click here to access online In: Прикладная дискретная математика № 45. С. 104-112Abstract: Для решения задачи коммивояжёра с матрицей расстояний порядка n предлагается приближённый алгоритм на основе метода ветвей и границ. Для отсечения используется увеличенная оценка снизу текущего частичного решения, гарантирующая заранее заданную величину е погрешности всего решения. Проведён вычислительный эксперимент для матриц расстояний четырёх видов распределений, среди них для равномерного случайного (несимметричного) распределения, а также для матриц евклидовых расстояний между случайными точками (симметричного распределения). В последнем случае дополнительно применён локальный поиск. Получены оценки степени p для функции полиномиальной трудоёмкости O(np) для разных видов распределений и различных величин погрешности е. Для равномерного случайного распределения полученная оценка степени p оказалась близка к 2,8 в диапазоне n до 1000 и средней погрешности около 1 %.Библиогр.: 8 назв.
Для решения задачи коммивояжёра с матрицей расстояний порядка n предлагается приближённый алгоритм на основе метода ветвей и границ. Для отсечения используется увеличенная оценка снизу текущего частичного решения, гарантирующая заранее заданную величину е погрешности всего решения. Проведён вычислительный эксперимент для матриц расстояний четырёх видов распределений, среди них для равномерного случайного (несимметричного) распределения, а также для матриц евклидовых расстояний между случайными точками (симметричного распределения). В последнем случае дополнительно применён локальный поиск. Получены оценки степени p для функции полиномиальной трудоёмкости O(np) для разных видов распределений и различных величин погрешности е. Для равномерного случайного распределения полученная оценка степени p оказалась близка к 2,8 в диапазоне n до 1000 и средней погрешности около 1 %.
There are no comments on this title.