Решатель задачи коммивояжёра (TSP)

О Решатель задачи коммивояжёра (TSP)

Решатель задачи коммивояжёра — это практический обучающий калькулятор для классической Задачи коммивояжёра (TSP): имея набор городов и расстояний между ними, необходимо найти кратчайший маршрут, проходящий через каждый город ровно один раз с возвратом в начало. Этот решатель принимает координаты на плоскости или пользовательскую матрицу расстояний, автоматически выбирает лучший алгоритм в зависимости от масштаба задачи и визуализирует результат в виде анимированной SVG-карты.

Что такое задача коммивояжёра?

Формально, имея полный взвешенный граф G = (V, E) с множеством вершин V = {1, 2, ..., n} и весами рёбер d(i, j), TSP ищет перестановку π вершин, которая минимизирует сумму:

Последнее слагаемое замыкает цикл. TSP — одна из старейших и наиболее изученных задач комбинаторной оптимизации. Она является NP-трудной, что означает отсутствие известных алгоритмов для решения любого экземпляра за полиномиальное время. Несмотря на это, она встречается в бесчисленных реальных приложениях: логистике, сверлении печатных плат, секвенировании ДНК, маршрутах на складах и даже в астрономических наблюдениях.

Как работает этот решатель

Динамическое программирование Хелда-Карпа (Точное)

Для небольших задач (до 12 городов) решатель вычисляет гарантированно оптимальный маршрут с помощью алгоритма Хелда-Карпа, опубликованного Ричардом Беллманом, а также Майклом Хелдом и Ричардом Карпом в 1962 году. Ключевое рекуррентное соотношение, где C(S, j) — кратчайший путь из вершины 1 в вершину j, посещающий подмножество S:

Стоимость оптимального тура составит min_j [C({1,...,n}, j) + d(j, 1)]. Алгоритм работает за время O(2ⁿ · n²) и требует O(2ⁿ · n) памяти. Это огромный прорыв по сравнению с полным перебором n!, но все же экспоненциальный рост делает его неприменимым для более чем 20 городов из-за нехватки памяти.

Ближайший сосед + 2-opt (Эвристика)

Для более крупных задач решатель использует двухэтапную эвристику. Сначала метод Ближайшего соседа строит быстрый маршрут, жадно переходя к ближайшему не посещенному городу. Решатель пробует разные начальные точки и сохраняет лучший вариант. Затем локальный поиск 2-opt улучшает путь, последовательно удаляя два ребра и пересоединяя их иным способом:

Геометрически 2-opt устраняет самопересечения в маршруте. Алгоритм останавливается в локальном оптимуме, называемом 2-оптимальным. На реалистичных евклидовых данных 2-opt находит решение в пределах 2–5% от истинного оптимума за миллисекунды.

Форматы ввода

Режим координат (x, y)

Один город на строку. Каждая строка содержит название, x, y (название необязательно). Решатель автоматически вычисляет евклидовы расстояния и визуализирует города на их реальных позициях.

Режим матрицы расстояний

Квадратная матрица n × n неотрицательных расстояний, значения разделены пробелами или запятыми. Матрицы могут быть симметричными или асимметричными (для моделирования дорог с односторонним движением или влияния ветра). Метки можно указать в поле «Метки матрицы».

Сравнение алгоритмов

Как использовать решатель

1. Выберите режим ввода. Используйте координаты, если позиции (x, y) имеют смысл; выберите матрицу расстояний, если ваши данные не евклидовы или асимметричны.
2. Вставьте или введите данные. По одному городу или строке матрицы на линию. Можно нажать кнопку быстрого примера над формой.
3. Выберите алгоритм. Оставьте Авто для оптимального выбора: Хелд-Карп для малых задач и БС + 2-opt для крупных.
4. Выберите тип маршрута. Замкнутый маршрут возвращается в начало — это классическая TSP. Режим открытого пути решает родственную задачу о Гамильтоновом пути.
5. Нажмите «Решить». На странице результатов отобразится общая длина, анимированная SVG-карта (нажмите «Повторить анимацию»), последовательность городов и детальная разбивка по рёбрам.

Пример работы

Рассмотрим пять городов — прямоугольник и вершину: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). Решатель выдаст:

• Маршрут: A → D → E → C → B → A
• Длина: 3 + √8 + √8 + 3 + 4 ≈ 15.66
• Оптимально? Да — алгоритм Хелда-Карпа доказывает, что более короткого пути не существует.
• Почему такой порядок? Путь следует по выпуклой оболочке пяти точек. Классическое свойство евклидовой TSP гласит, что оптимальный маршрут посещает точки выпуклой оболочки в их циклическом порядке.

Применение в реальном мире

• Логистика и доставка — оптимизация ежедневного маршрута водителя с 15 остановками для экономии топлива.
• Производство — последовательность отверстий для сверла ЧПУ на печатной плате для минимизации перемещений головки.
• Сборка генома — упорядочивание фрагментов ДНК по сходству перекрытий.
• Астрономия — планирование поворотов телескопа между звездами для максимизации времени наблюдения.
• Складские операции — построение маршрута сборщика заказов между стеллажами.
• Туризм — планирование поездки по нескольким городам с минимальными затратами времени.

Часто задаваемые вопросы

Что такое задача коммивояжёра?

Задача коммивояжёра (TSP) заключается в поиске самого короткого маршрута, который проходит через каждый заданный город один раз и возвращается в исходную точку.

Что такое алгоритм Хелда-Карпа?

Это метод точного решения задачи на основе динамического программирования. Он эффективнее перебора, но ограничен количеством городов (обычно до 20) из-за экспоненциального роста требований к памяти.

Что такое 2-opt и почему он популярен?

Это эвристический алгоритм, который быстро находит очень хорошие (хотя и не всегда идеальные) решения, исправляя пересечения путей. Он является стандартом для решения крупных практических задач TSP.

Когда использовать координаты, а когда матрицу?

Координаты подходят для точек на карте. Матрица нужна, когда стоимость перехода между пунктами не зависит от расстояния напрямую (например, разные цены на авиабилеты или пробки на дорогах).

Является ли решение 2-opt самым лучшим?

Не гарантированно. Оно является локальным оптимумом. В большинстве случаев оно очень близко к идеалу, но для 100% уверенности в кратчайшем пути на малых данных лучше использовать метод Хелда-Карпа.

Поддерживает ли этот инструмент асимметричные расстояния?

Да, в режиме матрицы расстояний. Вы можете указать разные веса для переходов A→B и B→A.

Дополнительные материалы

• Алгоритм Хелда-Карпа — Wikipedia (англ.)
• 2-opt — Wikipedia (англ.)

Продвинутые математические операции:

• Калькулятор матрицы смежности Новый
• Антилогарифмический Калькулятор
• Калькулятор бета-функции
• Калькулятор биномиального коэффициента
• Калькулятор биномиального распределения
• Побитовый калькулятор Популярное
• Упроститель Булевой Алгебры Новый
• Калькулятор центральной предельной теоремы
• Калькулятор китайской теоремы об остатках
• Комбинированный калькулятор
• Калькулятор дополнительной функции ошибки
• Калькулятор комплексных чисел Популярное
• Калькулятор цепных дробей
• Калькулятор беспорядков (субфакториал)
• Калькулятор кратчайшего пути Дейкстры
• Калькулятор Энтропии
• Калькулятор функции ошибки
• Калькулятор функции Эйлера
• Калькулятор экспоненциального распада
• Калькулятор экспоненциального роста: высокая точность
• Калькулятор экспоненциального интеграла
• Калькулятор показателей (высокая точность)
• Калькулятор расширенного алгоритма Евклида
• Калькулятор факториала Популярное
• Калькулятор гамма-функции
• Калькулятор золотого сечения
• Калькулятор раскраски графов Новый
• Валидатор последовательности степеней графа
• Калькулятор Порядка в Теории Групп Новый
• Калькулятор полураспада
• Проверка Гамильтонова Пути Новый
• Калькулятор формулы включений-исключений Новый
• Решатель Карты Карно (K-Map) Популярное
• Решатель Линейного Программирования Новый
• Калькулятор стационарного распределения цепи Маркова
• Калькулятор минимального остовного дерева
• Калькулятор Модульного Возведения в Степень Новый
• Калькулятор модулярного мультипликативного обратного
• Калькулятор отрицательного биномиального распределения Новый
• Калькулятор сетевого потока (Максимальный поток) Новый
• Калькулятор процентного роста
• Калькулятор перестановок
• Калькулятор перестановок с повторениями Новый
• Калькулятор принципа голубятни
• Проверка планарного графа Новый
• Калькулятор распределения Пуассона
• Калькулятор корней многочленов с подробными шагами
• Калькулятор первообразного корня
• Калькулятор вероятности
• Калькулятор распределения вероятностей
• Калькулятор пропорций
• Калькулятор квадратичных формул
• Калькулятор Колец и Полей Новый
• Калькулятор округления Новый
• Научный Калькулятор
• Калькулятор экспоненциальной записи
• Калькулятор теории множеств Популярное
• Калькулятор значащих цифр Новый
• Решатель задачи о стабильных браках Новый
• Калькулятор чисел Стирлинга
• Калькулятор суммы кубов
• Калькулятор суммы последовательных чисел Популярное
• Калькулятор суммы квадратов
• Калькулятор топологической сортировки Новый
• Решатель задачи коммивояжёра (TSP) Новый
• Генератор таблицы истинности
• Генератор диаграммы Венна (3 множества)