Исследование влияния асимметрии на сложность решения задачи коммивояжера методом ветвей и границ
Authors: МАМОНОВ Н.В. 
Published: January 2025

Одной из самых известных задач комбинаторной оптимизации является задача коммивояжера. Эта задача является важной и вместе с тем трудноразрешимой, что связано с экспоненциальной сложностью точных методов решения. Она возникает в обширном классе приложений: в построении оптимальных схем движения, распознавании траекторий и образов. Однако, целый ряд научных исследований, в частности, вопросы генетики и биоинформатики, требуют получения точного решения. На основе классической реализации метода ветвей и границ в работе проводится исследование влияния асимметрии на сложность решения. Поскольку проводимое исследование требует анализа большого числа экспериментально полученных данных, возникает необходимость повышения скорости проведения расчетов. Выбранный для работы метод ветвей и границ допускает получение большей скорости перебора решений за счет хранения в памяти состояний активных листовых вершин дерева решений. На эффективность реализации алгоритма влияет также выбор структур данных для быстрого нахождения следующей рассматриваемой вершины. На основании полученных результатов и проведенного анализа установлена зависимость сложности решения задачи от асимметричности матрицы. Некоторые из вариантов внесения асимметрии приводят к сокращению сложности решения. Изучение влияния асимметрии на сложность задачи коммивояжера на примере классического алгоритма решения – метода ветвей и границ – представляет интерес для дальнейшего предиктивного анализа сложности индивидуальных задач.

The traveling salesman problem is the one of the most famous combinatorial optimization problems. This problem is important and at the same time difficult to solve, due to the exponential complexity of the exact methods of solution. It occurs in an extensive class of applications: in the construction of optimal motion schemes, recognition of tracks and images. However, a number of scientific studies, in particular, genetics and bioinformatics, require an accurate solution. This study is concerned with the problem of asymmetry influence on the complexity of the solution, which obtained with the classical implementation of branches and bounds method. Since the study requires the analysis of numerous experimental data, there is a need to increase the speed of calculations. The selected approach using branch and bounds method allows gaining an extra speed of search in decision tree by maintaining in-memory state of the active list nodes of the tree. The efficiency of the implementation of the algorithm is also affected by the choice of data structures for the rapid finding of the next vertex under consideration. Based on the results and the analysis, the dependence of the complexity of the problem solution on the asymmetry of the matrix is established. Some asymmetry options reduce the complexity of the solution. The study of the influence of asymmetry on the traveling salesman problem’s complexity on the example of the classical solution algorithm – the method of branches and bounds – is of interest to further predictive analysis of the complexity of individual problems.