Задача коммивояжера: Python, C++ Алгоритм
Сара Чен
Что такое задача коммивояжера (TSP)?
Задача коммивояжера (TSP) — это классическая комбинаторная задача теоретической информатики. Задача состоит в том, чтобы найти кратчайший путь в графе с условием посещения всех узлов только один раз и возвращения в исходный город.
В постановке задачи дается список городов с указанием расстояний между каждым городом.
Цель: Чтобы начать с исходного города, посетите другие города только один раз и снова вернитесь в исходный город. Наша цель — найти кратчайший возможный путь для завершения маршрута туда и обратно.
Пример ТСП
Здесь дан граф, где 1, 2, 3 и 4 представляют города, а вес, связанный с каждым ребром, представляет расстояние между этими городами.
Цель состоит в том, чтобы найти кратчайший возможный путь для тура, который начинается из исходного города, пересекает граф, посещая другие города или узлы только один раз, и возвращается в исходный город.
Для приведенного выше графика оптимальным маршрутом является путь с минимальными затратами: 1-2-4-3-1. И этот кратчайший маршрут будет стоить 10+25+30+15 =80.
Различные решения проблемы коммивояжера
Задача коммивояжера (TSP) классифицируется как NP-трудная задача из-за отсутствия алгоритма с полиномиальным временем. Сложность возрастает в геометрической прогрессии с увеличением количества городов.
Существует несколько способов решения задачи коммивояжера (tsp). Некоторые популярные решения:
Подход грубой силы — это наивный метод для решения задач коммивояжера. В этом подходе мы сначала вычисляем все возможные пути, а затем сравниваем их. Количество путей в графе, состоящем из n городов, равно n! Решение задачи коммивояжера при таком подходе грубой силы требует очень больших вычислительных затрат.
Метод ветвей и границ: В этом подходе проблема разбивается на подзадачи. Решение этих отдельных подзадач обеспечит оптимальное решение.
В этом руководстве будет продемонстрирован подход динамического программирования, рекурсивная версия метода ветвей и границ, для решения задачи коммивояжера.
Динамическое программирование – это такой метод поиска оптимальных решений путем анализа всех возможных маршрутов. Это один из точных методов решения, который решает проблемы коммивояжера за счет относительно более высоких затрат, чем метод жадные методы которые обеспечивают почти оптимальное решение.
Вычислительная сложность этого подхода составляет О(Н^2 * 2^Н) который обсуждается далее в этой статье.
Метод ближайшего соседа — это жадный подход, основанный на эвристике, при котором мы выбираем ближайший соседний узел. Этот подход вычислительно менее затратен, чем динамический подход. Но это не дает гарантии оптимального решения. Этот метод используется для получения решений, близких к оптимальным.
Алгоритм решения задачи коммивояжера
Мы будем использовать подход динамического программирования для решения задачи коммивояжера (TSP).
Прежде чем приступить к алгоритму, познакомимся с некоторой терминологией:
- Граф G=(V, E), представляющий собой множество вершин и ребер.
- V — множество вершин.
- E — множество ребер.
- Вершины соединены ребрами.
- Dist(i,j) обозначает неотрицательное расстояние между двумя вершинами i и j.
Предположим, S — это подмножество городов, принадлежащее {1, 2, 3, …, n}, где 1, 2, 3… n — города, а i, j — два города в этом подмножестве. Теперь Cost(i, S, j) определяется таким образом, как длина кратчайшего пути, посещающего узел в S, который ровно один раз имеет начальную и конечную точки как i и j соответственно.
Например, стоимость (1, {2, 3, 4}, 1) обозначает длину кратчайшего пути, где:
- Стартовый город — 1.
- Города 2, 3 и 4 посещаются только один раз.
- Конечная точка - 1.
Алгоритм динамического программирования будет следующим:
- Установите стоимость(i, , i) = 0, что означает, что мы начинаем и заканчиваем в i, а стоимость равна 0.
- Когда |S| > 1, мы определяем Cost(i, S, 1) = ∝, где i !=1 . Потому что изначально мы не знаем точную стоимость проезда из города i в город 1 через другие города.
- Теперь нам нужно начать с 1 и завершить тур. Нам нужно выбрать следующий город таким образом-
стоимость(i, S, j)=минимальная стоимость (i, S−{i}, j)+dist(i,j), где iεS и i≠j
Для данного рисунка матрица смежности будет следующей:
| расстояние (я, 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, мы установим стоимость расстояния (i, S, 1) = ∝. Здесь Cost(i, S, j) означает, что мы начинаем с города i, посещаем города S один раз, и теперь мы находимся в городе j. Мы установили стоимость пути как бесконечность, поскольку расстояние еще не известно. Таким образом, значения будут следующими:
Стоимость (2, {3, 4}, 1) = ∝; обозначение означает, что мы начинаем с города 2, проходим через города 3, 4 и достигаем 1. А стоимость пути равна бесконечности. Сходным образом-
стоимость(3, {2, 4}, 1) = ∝
стоимость(4, {2, 3}, 1) = ∝
Шаг 3) Теперь для всех подмножеств S нам нужно найти следующее:
стоимость(i, S, j)=минимальная стоимость (i, S−{i}, j)+dist(i,j), где jεS и i≠j
Это означает путь с минимальной стоимостью для начала в i, прохождения через подмножество городов один раз и возвращения в город j. Учитывая, что путешествие начинается в городе 1, оптимальная стоимость пути будет равна стоимости(1, {другие города}, 1).
Давайте выясним, как мы можем этого добиться:
Теперь S = {1, 2, 3, 4}. Есть четыре элемента. Следовательно, количество подмножеств будет 2 ^ 4 или 16. Эти подмножества —
1) |С| = Ноль:
{Φ}
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) |С| = Ф:
стоимость (2, Φ, 1) = dist(2, 1) = 10
стоимость (3, Φ, 1) = dist(3, 1) = 15
стоимость (4, Φ, 1) = dist(4, 1) = 20
2) |С| = 1:
стоимость (2, {3}, 1) = dist(2, 3) + стоимость (3, Φ, 1) = 35+15 = 50
стоимость (2, {4}, 1) = dist(2, 4) + стоимость (4, Φ, 1) = 25+20 = 45
стоимость (3, {2}, 1) = dist(3, 2) + стоимость (2, Φ, 1) = 35+10 = 45
стоимость (3, {4}, 1) = dist(3, 4) + стоимость (4, Φ, 1) = 30+20 = 50
стоимость (4, {2}, 1) = dist(4, 2) + стоимость (2, Φ, 1) = 25+10 = 35
стоимость (4, {3}, 1) = dist(4, 3) + стоимость (3, Φ, 1) = 30+15 = 45
3) |С| = 2:
стоимость (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
стоимость (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
стоимость (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:
стоимость (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 Є S and i ≠ 1
Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j}
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)
Реализация на C/C++
Вот реализация в C++:
#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;
while(next_permutation(vertex.begin(), vertex.end()))
{
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);
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
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
next_permutation=permutations(vertex)
for i in next_permutation:
current_cost = 0
k = s
for j in i:
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-сложной.
Хотя в последние годы были опубликованы некоторые из следующих решений, которые в определенной степени снизили сложность:
- Классическая симметричная задача TSP решается методом нулевого суффикса.
- Алгоритм оптимизации на основе биогеографии основан на стратегии миграции для решения задач оптимизации, которые можно планировать как TSP.
- Многоцелевой эволюционный алгоритм предназначен для решения множественных задач TSP на основе NSGA-II.
- Мультиагентная система решает задачу TSP N городов с фиксированными ресурсами.
Применение задачи коммивояжера
Задача коммивояжера (TSP) применяется в реальном мире как в чистом, так и в модифицированном виде. Некоторые из них:
- Планирование, логистика и производство микрочипов: Проблемы со вставкой чипов естественным образом возникают в индустрии микрочипов. Эти проблемы можно спланировать как проблемы коммивояжера.
- секвенирование ДНК: Небольшую модификацию задачи коммивояжера можно использовать при секвенировании ДНК. Здесь города представляют собой фрагменты ДНК, а расстояние представляет собой меру сходства между двумя фрагментами ДНК.
- Астрономия: Задача коммивояжера применяется астрономами, чтобы минимизировать время, затрачиваемое на наблюдение различных источников.
- Задача оптимального управления: Коммивояжер Формулировку задачи можно применить к задачам оптимального управления. Могут быть добавлены еще несколько ограничений.
Анализ сложности TSP
- Сложность времени: Всего 2N подзадачи для каждого узла. Таким образом, общее количество подзадач будет N*2.N. Для решения каждой из подзадач требуется линейное время. Если исходный узел не указан, нам придется выполнить циклы для N узлов.
Таким образом, общая временная сложность оптимального решения будет равна Число узлов * Количество подзадач * время решения каждой подзадачи. Временную сложность можно определить как O(N2 * 2^Н).
- Космическая сложность: Подход динамического программирования использует память для хранения C(S, i), где S — подмножество набора вершин. Всего их 2N подмножества для каждого узла. Таким образом, пространственная сложность составляет O(2^N).
Далее вы узнаете о Сито Эратосфена Алгоритм
