Что такое 2-opt и зачем он нужен?

2-opt — это эвристика локального поиска, которая последовательно удаляет два ребра из маршрута и пересоединяет их иным способом. Если новый маршрут короче, замена сохраняется. Он работает за полиномиальное время и находит решения, близкие к оптимальным.

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

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

Является ли решение 2-opt оптимальным?

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

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

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

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

Найдите кратчайший маршрут, который посещает каждый город ровно один раз и возвращается в начало. Точное динамическое программирование (алгоритм Хелда–Карпа) для небольших наборов данных и эвристика ближайшего соседа + 2-opt для крупных задач. Поддерживает координаты или матрицу расстояний и генерирует анимированный SVG-маршрут.

Быстрые примеры:

5 городов (квадрат + пик) 8 случайных городов 8 столиц ЕС Матрица 4×4 Тест (10 городов) Треугольник (открытый путь)

⌖ Координаты (x, y) ▦ Матрица расстояний

Города или матрица

Строки координат: A, 10, 20 или 10 20. Строки матрицы: 0 10 15 20 — по одной строке на линию, квадратная, неотрицательная. Макс. 40 городов.

Метки матрицы (необязательно)

Разделенные запятой или пробелом метки, по одной на строку матрицы. По умолчанию: A, B, C…

Алгоритм

Тип маршрута

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

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

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

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

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

minimize Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

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

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

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

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

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

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

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

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

До: ... a — b ... c — d ... После 2-opt перестановки: ... a — c ... b — d ... Если d(a,c) + d(b,d) < d(a,b) + d(c,d) → принимаем замену, инвертируем подмаршрут b..c

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

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

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

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

A, 10, 20 B, 40, 70 C, 75, 30 Paris: 2.35, 48.86 10 20 ← авто-метка C1

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

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

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

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

Алгоритм	Временная сложность	Память	Качество результата	Практичный размер
Полный перебор	O(n!)	O(n)	Оптимально	n ≤ 10
ДП Хелда-Карпа	O(2ⁿ · n²)	O(2ⁿ · n)	Оптимально	n ≤ 20
Ближайший сосед	O(n²)	O(n)	~25% хуже оптимума	n ≤ тысячи
БС + 2-opt	O(n² · проходы)	O(n)	~2–5% хуже оптимума	n ≤ сотни

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

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

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

Ссылайтесь на этот контент, страницу или инструмент так:

"Решатель задачи коммивояжёра (TSP)" на сайте https://ru.miniWebtool.com/решатель-задачи-коммивояжёра-tsp/ от MiniWebtool, https://MiniWebtool.com/

от команды miniwebtool. Обновлено: 21 апр. 2026 г.

Вы также можете попробовать наш AI Решатель Математических Задач GPT, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.