By this author

Statistical Study of the Quality of the Cycle Merging Algorithm for Solving the Traveling Salesman Problem at Minimum

Issue number 5 from 01.05.2025

Задача коммивояжера является одной из наиболее изученных в комбинаторной оптимизации, однако исследование новых подходов и улучшение существующих методов остается актуальной задачей. Вда нной работе проведен анализ качества алгоритма соединения циклов для задачи коммивояжера на минимум. Представлены результаты вычислительного эксперимента на пяти семействах задач, проанализированы точность и временная сложность алгоритма. Для симметричных экземпляров задачи построена регрессионная модель, описывающая зависимость оценки относительной погрешности от числа вершин. Показано, что полиномиальная модель наилучшим образом аппроксимирует полученные данные и удовлетворяет основным статистическим предпосылкам. Полученные результаты позволяют оценить характер роста ошибки и обосновать применимость алгоритма к экземплярам задачи коммивояжера большой размерности.

11 0