Задача коммивояжёра (или TSP от англ. travelling salesman problem) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города ровно по одному разу с последующим возвратом в исходный город.
Задача относится к классу NP-трудных задач, что означает, что для неё не существует алгоритма, который мог бы найти точное решение за полиномиальное время. Это делает её вычислительно сложной, поскольку время решения растет экспоненциально с увеличением числа городов.
Однако задача эта очень реальная и практически значимая, ее постоянно необходимо решать. Даже если мы не можем решить ее гарантированно максимально оптимально, мы можем стараться найти по меньшей мере неплохое или удовлетворительное решение.
Очень небольшая сеть
Чтобы провести с вами небольшое исследование для задачи коммивояжера, предлагаю упростить задачу до поиска оптимального маршрута между двумя точками. В конце статьи под пунктом 1 дана ссылка на программу на Си++, которая генерирует граф со связями, для которого будем искать оптимальные пути. Граф на выходе представлен информацией о существующих связях между узлами. Будем рассматривать город с односторонним движением, в котором путь в одну сторону может отличаться от пути в обратную сторону.
Создадим матрицу дорог между 5 адресами с разбросом расстояний от 10 до 100, ниже пример тепловой карты.
А визуально такой граф с однонаправленными связями (ассиметричный) выглядит так, как показано на рисунке ниже.
Программа, которая с разным количеством промежуточных узлов (назовем этот параметр глубиной) просчитывает оптимальный маршрут, предложена в конце статьи. Для 5 городов, проиллюстрированных на рисунке выше, расчет с любой точностью занимает незначительное время на обычном ноутбуке.
Сеть побольше
Начиная с 13 узлов процесс поиска оптимальных путей до глубины 7 начинает требовать заметного времени.
На рисунке 4 приведено усредненное (для серии из 20 экспериментов) время в секундах, которое понадобилось для поиска всех оптимальных путей с заданной глубиной. Для глубины от 1 до 3 время практичеки не зависит от глубины, что связано с наличием в программе некоторого количества операций ввода-вывода, на фоне которых время вычисления незначительно. Для глубины от 3 до 7 отчетливо видно, что время растет экспоненциально, обратите внимание, что по вертикальной оси отложено время в логарифмическом масштабе.
Здесь (Рис. 5) показано, как увеличение глубины поиска оптимального пути для 13 узлов (каждого с каждым) уменьшает расстояния. При этом каждое следующее увеличение глубины приводит к менее значительному уменьшению путей, что более отчетливо видно на зависимости, приведенной ниже.
Синяя линия на рисунке 6 демонстрирует, как меняется среднее оптимизированное расстояние с увеличением глубины поиска оптимального маршрута. Эта завсимость носит насыщающийся характер. Более очевидно влияние увеличение глубины поиска показано зеленой линией на этом же графике, которая показывает, насколько уменьшилось относительное расстояние по сравнению с предыдущей глубиной оптимизации. Видно, что, например, увеличение глубины с 5 до 6 уменьшает среднее расстояние примерно на 0.03%, то есть очень мало. При этом, стоимость этого улучшения на порядки больше, чем улучшения, которые получились при увеличении глубины с 0 до 1 (см. Рис. 4).
Здесь напрашивается вывод о том, что увеличение глубины оптимизации не очень нужно, начиная с 5. Но давайте рассмотрим графы разных размеров и либо подтвердим эту версию, либо опровергнем.
Влияние размера сети на скорость и качество оптимизации маршрута
Для оценки влияния размера сети на производительность оптимизации рассмотрим сети разных размеров, начиная от 8 узлов (более маленькие сети оптимизируются слишком быстро относительно выбранной группы сетей).
Зависимости среднего времени оптимизации маршрута в секундах от глубины оптимизации на рисунке 7 показывают, что время оптимизации сети увеличивается даже быстрее, чем экспоненциально, для небольших сетей. Но с увеличением размера сети зависимость времени оптимизации от глубины оптимизации характеризуется экспоненциальной функцией. В логарифмическом масштабе наклон кривой увеличивается с увеличением размеров сети.
Средняя производительность оптимизации маршрутов в графе с увеличением глубины оптимизации уменьшается обратно экспоненте (Рис. 8). При этом достаточно глубокая оптимизация (более 4) не приносит существенного улучшения в сетях разных размеров.
Чтобы определить экономическую стоимость оптимизации маршрутов, мы можем рассмотреть отношение времени к относительному сокращению маршрутов, приведенное на рисунке 9. Эти характеристик показывают, за сколько секунд процессорного времени удается сократить расстояния между узлами сети на 1%. Эта характеристика увеличивается быстрее экспоненты. Это очень быстрый рост и на примере даже небольшой сети видно, как быстро растет стоимость оптимизации с увеличением глубины поиска.
Заключение
Таким образом, навигация является очень сложной проблемой и рано или поздно с увеличением сети методом перебора становится нерешаемой. Вообще нет конкретного числа вершин, после которого задача становится абсолютно нерешаемой, есть практический предел, после которого время ожидания точного решения становится неприемлемым (дни, годы, века). Стоит отметить, что существует не только метод перебора. Есть приближенные методы, которые позволяют решать задачу коммивояжера приближенно, но достаточно хорошо. В конце концов мы, когда не пользуемся интеллектуальным навигатором, неплохо можем найти дорогу, явно пользуясь каким-то неточным интуитивным методом.
Программы, используемые для проведения вычислений
1. Программа generategraph.cpp, генерирующая связи по заданным количеству узлов и связей в заданном диапазоне расстояний: ссылка, действующая до 25.02.2026.
2. Программа exploregraph.cpp, находящая все оптимальные пути между узлами с заданным максимумом промежуточных точек: ссылка, действующая до 26.02.2026.