Задача коммивояжера: Python, C++ Алгоритм
⚡ Умное резюме
Задача коммивояжера — это классическая NP-трудная задача оптимизации, которая заключается в поиске кратчайшего маршрута, включающего посещение каждого города ровно один раз и возвращение в начало координат, с использованием данных о расстояниях, предоставленных через граф.

Что такое задача коммивояжера (TSP)?
Задача коммивояжера (TSP) — это классическая задача комбинаторной оптимизации из теоретической информатики. Дана диаграмма городов, и задача TSP заключается в нахождении кратчайшего пути, который посещает каждую вершину ровно один раз и возвращается в исходный город.
В условии задачи приведен список городов, а также расстояния между каждой парой городов.
Цель: Начните с города отправления, посетите каждый второй город ровно один раз и вернитесь в город начала маршрута. Цель — найти кратчайший возможный маршрут туда и обратно.
Пример ТСП
Рассмотрим граф ниже, где 1, 2, 3 и 4 обозначают города, а вес каждого ребра соответствует расстоянию между этими городами.
Цель состоит в том, чтобы найти кратчайший возможный маршрут, который начинается из города отправления, посещает каждый второй город ровно один раз и возвращается в город отправления.
Для представленного выше графика оптимальный маршрут — это 1-2-4-3-1Стоимость самой короткой экскурсии составляет 10 + 25 + 30 + 15 = 80.
Различные решения проблемы коммивояжера
Задача коммивояжера классифицируется как NP-трудная, поскольку ни один известный полиномиальный алгоритм не решает её точно. Сложность экспоненциально возрастает с увеличением числа городов.
Существует несколько способов атаки на задачу коммивояжера (TSP). Наиболее распространенные подходы:
Метод грубой силы: Наивный метод вычисляет все возможные маршруты и сравнивает их. Количество маршрутов в графе с n городами равно... n!, что делает вычисления методом перебора очень затратными для всего, что находится за пределами примерно десяти городов.
Метод ветвей и границ: Задача разбивается на подзадачи, и решения этих подзадач объединяются в оптимальное решение. Эффективная обрезка отбрасывает частичные маршруты, которые не могут превзойти текущую наилучшую стоимость.
В этом руководстве демонстрируется... подход динамического программирования, которая представляет собой мемоизированную версию метода ветвей и границ и соответствует алгоритму Беллмана-Хелда-Карпа.
Динамическое программирование: Это точный метод, который ищет оптимальное решение путем повторного использования перекрытий.ping Результаты решения подзадачи. Это медленнее, чем почти оптимальный вариант. жадные методыно он всегда возвращает глобально оптимальный маршрут.
Вычислительная сложность этого подхода составляет O(N² × 2^N), о чем мы поговорим позже в статье.
Метод ближайшего соседа: Эвристический жадный подход, который всегда переходит к ближайшему непосещенному городу. Он намного дешевле, чем динамическое программирование, но не гарантирует оптимального маршрута, поэтому используется для почти оптимальных решений, когда скорость важнее точного минимума.
Алгоритм решения задачи коммивояжера
Для решения задачи коммивояжера мы используем подход динамического программирования. Прежде чем приступить к алгоритму, давайте разберемся с некоторыми терминами:
- График
G = (V, E)представляет собой множество вершин и рёбер. V— это множество вершин.E— это множество ребер.- Вершины соединены ребрами.
Dist(i, j)обозначает неотрицательное расстояние между вершинами i и j.
Предположим, S — подмножество городов, взятых из множества {1, 2, 3, …, n}, где i и j — два города из этого подмножества. Тогда cost(i, S, j) — это длина кратчайшего пути, который начинается в точке i, посещает каждый город в S ровно один раз и заканчивается в точке j.
Например, cost(1, {2, 3, 4}, 1) обозначает кратчайший путь, где:
- Стартовый город — 1.
- Города 2, 3 и 4 посещаются только один раз.
- Конечная точка - 1.
Рекуррентное соотношение динамического программирования выглядит следующим образом:
- Поставьте
cost(i, {}, i) = 0, что означает, что мы начинаем и заканчиваем в точке i с нулевыми затратами. - После появления
|S| > 1определитьcost(i, S, 1) = ∞дляi ≠ 1, поскольку реальная стоимость тура пока неизвестна. - Начиная с города 1, выберите следующий город таким образом, чтобы
cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ]дляi ∈ Sиi ≠ j.
Для представленного выше графа матрица смежности выглядит следующим образом:
| dist(i, j) | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 10 | 15 | 20 |
| 2 | 10 | 0 | 35 | 25 |
| 3 | 15 | 35 | 0 | 30 |
| 4 | 20 | 25 | 30 | 0 |
Вот как работает алгоритм:
Шаг 1) Путешествие начинается в городе 1, включает посещение каждого второго города по одному разу и возвращается в город 1.
Шаг 2) S — подмножество городов. Для каждого |S| > 1 инициализируйте cost(i, S, 1) = ∞, Вот cost(i, S, j) обозначает маршрут, начинающийся в точке i, посещающий города в S один раз и достигающий точки j. Мы начинаем с бесконечности, поскольку расстояние в этой точке неизвестно. Таким образом, значения следующие:
cost(2, {3, 4}, 1) = ∞ Это означает, что мы начинаем в городе 2, проходим через города 3 и 4 и достигаем города 1 с неизвестной стоимостью. Аналогично:
cost(3, {2, 4}, 1) = ∞
cost(4, {2, 3}, 1) = ∞
Шаг 3) Для каждого подмножества S вычислите:
cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Где j ∈ S и i ≠ j.
Это маршрут с минимальной стоимостью, который начинается в городе i, посещает подмножество городов один раз и возвращается в город j. Поскольку маршрут начинается в городе 1, оптимальная стоимость составляет cost(1, {other cities}, 1).
Пошаговая инструкция по устранению повторения проблемы
Теперь S = {1, 2, 3, 4}. В множестве четыре элемента, поэтому количество подмножеств равно 2^4 = 16Эти подмножества:
1) |С| = 0: {Φ}
2) |С| = 1: {{1}, {2}, {3}, {4}}
3) |С| = 2: {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |С| = 3: {{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |С| = 4: {{1, 2, 3, 4}}
Поскольку тур начинается в городе 1, мы можем отбросить все подмножества, содержащие город 1, при вычислении промежуточных затрат.
Алгоритм вычислений разворачивается следующим образом:
1) |С| = Ф:
- cost(2, Φ, 1) = dist(2, 1) = 10
- cost(3, Φ, 1) = dist(3, 1) = 15
- cost(4, Φ, 1) = dist(4, 1) = 20
2) |С| = 1:
- cost(2, {3}, 1) = dist(2, 3) + cost(3, Φ, 1) = 35 + 15 = 50
- cost(2, {4}, 1) = dist(2, 4) + cost(4, Φ, 1) = 25 + 20 = 45
- cost(3, {2}, 1) = dist(3, 2) + cost(2, Φ, 1) = 35 + 10 = 45
- cost(3, {4}, 1) = dist(3, 4) + cost(4, Φ, 1) = 30 + 20 = 50
- cost(4, {2}, 1) = dist(4, 2) + cost(2, Φ, 1) = 25 + 10 = 35
- cost(4, {3}, 1) = dist(4, 3) + cost(3, Φ, 1) = 30 + 15 = 45
3) |С| = 2:
- cost(2, {3, 4}, 1) = min [ dist(2, 3) + cost(3, {4}, 1) = 35 + 50 = 85, dist(2, 4) + cost(4, {3}, 1) = 25 + 45 = 70 ] = 70
- cost(3, {2, 4}, 1) = min [ dist(3, 2) + cost(2, {4}, 1) = 35 + 45 = 80, dist(3, 4) + cost(4, {2}, 1) = 30 + 35 = 65 ] = 65
- cost(4, {2, 3}, 1) = min [ dist(4, 2) + cost(2, {3}, 1) = 25 + 50 = 75, dist(4, 3) + cost(3, {2}, 1) = 30 + 45 = 75 ] = 75
4) |С| = 3:
- cost(1, {2, 3, 4}, 1) = min [ dist(1, 2) + cost(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + cost(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + cost(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80
Таким образом, оптимальное решение — это 1-2-4-3-1.
Псевдо-код
Algorithm: Traveling-Salesman-Problem
Cost (1, {}, 1) = 0
for s = 2 to n do
for all subsets S belongs to {1, 2, 3, ..., n} of size s
Cost (s, S, 1) = Infinity
for all i in S and i != 1
Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)
Реализация на C/C++
Вот реализация в C++В приведенной ниже версии исправлена ранняя ошибка в исходном коде. return Ошибка, которая возвращалась после первой же перестановки вместо того, чтобы перечислить все маршруты.
#include <bits/stdc++.h> using namespace std; #define V 4 #define MAX 1000000 int tsp(int graph[][V], int s) { vector<int> vertex; for (int i = 0; i < V; i++) if (i != s) vertex.push_back(i); int min_cost = MAX; do { int current_cost = 0; int j = s; for (int i = 0; i < vertex.size(); i++) { current_cost += graph[j][vertex[i]]; j = vertex[i]; } current_cost += graph[j][s]; min_cost = min(min_cost, current_cost); } while (next_permutation(vertex.begin(), vertex.end())); return min_cost; } int main() { int graph[][V] = { { 0, 10, 15, 20 }, { 10, 0, 35, 25 }, { 15, 35, 0, 30 }, { 20, 25, 30, 0 } }; int s = 0; cout << tsp(graph, s) << endl; return 0; }
Выход:
80
Реализация в Python
Python реализация отражает C++ версия. Она исправляет ошибку в исходном тексте. from itertools, import опечатка в запятой, неправильно расставленное return внутри внутренней петли и случайная вмятина на s = 0.
from sys import maxsize from itertools import permutations V = 4 def tsp(graph, s): vertex = [] for i in range(V): if i != s: vertex.append(i) min_cost = maxsize for perm in permutations(vertex): current_cost = 0 k = s for j in perm: current_cost += graph[k][j] k = j current_cost += graph[k][s] min_cost = min(min_cost, current_cost) return min_cost graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]] s = 0 print(tsp(graph, s))
Выход:
80
Академические решения для TSP
Специалисты в области компьютерных наук десятилетиями искали улучшенные полиномиальные алгоритмы для решения задачи коммивояжера. До сих пор задача коммивояжера остается NP-трудной.
Существует несколько опубликованных методик, позволяющих снизить практическую сложность для конкретных семейств задач коммивояжера:
- Классическая симметричная задача коммивояжера решается с помощью Метод нулевого суффикса.
- Алгоритм оптимизации на основе биогеографии Использует стратегии миграции для решения задач оптимизации, которые соответствуют задаче коммивояжера.
- Многоцелевой эволюционный алгоритм Он предназначен для решения многоцелевой задачи коммивояжера и основан на алгоритме NSGA-II.
- Мультиагентная система Данный подход решает задачу коммивояжера для N городов при фиксированных вычислительных ресурсах.
- Эвристика Лин-Кернигана и его преемник ЛКХ Проведение туров с точностью до 2-3% от оптимальной, особенно в случаях с миллионами городов.
- Согласие Использует секущие плоскости и метод ветвей и отсечений для вычисления точных оптимумов для тестовых примеров, включающих десятки тысяч городов.
Применение задачи коммивояжера
Задача коммивояжера встречается в реальном мире как в чистом, так и в модифицированном виде. Основные примеры её применения:
- Планирование, логистика и производство микрочипов: В микрочиповой промышленности проблемы внедрения микросхем моделируются как варианты задачи коммивояжера (TSP) для минимизации времени перемещения роботизированной руки.
- секвенирование ДНК: Модифицированный алгоритм TSP используется в секвенировании ДНК, где города представляют собой фрагменты ДНК, а расстояния — сходство между фрагментами.
- Астрономия: Астрономы используют алгоритм TSP для минимизации времени, затрачиваемого на наведение телескопов между объектами наблюдения.
- Оптимальное управление: В формулировках задачи коммивояжера моделируются задачи оптимального управления, в которых необходимо соблюдать множество ограничений, минимизируя при этом стоимость обхода.
- Доставка последней мили: AmazonПриложения для доставки еды, такие как UPS, решают динамические варианты задачи коммивояжера для упорядочивания остановок водителей.
- Комплектация на складе: Роботы и операторы-сборщики следуют оптимизированным маршрутам TSP, что сокращает время перемещения внутри распределительных центров.
Анализ сложности TSP
- Сложность времени: Метод динамического программирования Хелда-Карпа решает 2 задачи.N подмножества для каждого начального узла, что дает
N × 2^Nподзадачи. Объединение каждой подзадачи занимает линейное время. Если исходный узел не указан, требуется внешний цикл по N узлам. Общая временная сложность составляетO(N² × 2^N). - Космическая сложность: В таблице DP хранятся
C(S, i)для каждого подмножества S множества вершин. Существует 2N подмножества на узел, поэтому пространственная сложность составляетO(N × 2^N), который часто записывается какO(2^N)когда N рассматривается как фиксированное значение.
Далее, узнайте о Сито Эратосфена Алгоритм.




