Проблема комівояжера: Python, C++ Алгоритм
Сара Чен
Що таке проблема комівояжера (TSP)?
Задача комівояжера (TSP) — класична комбінаторна задача теоретичної інформатики. У задачі пропонується знайти найкоротший шлях у графі з умовою відвідування всіх вузлів лише один раз і повернення до початкового міста.
Постановка задачі містить список міст разом із відстанями між кожним містом.
Мета: Щоб почати з початкового міста, відвідайте інші міста лише один раз і поверніться до вихідного міста знову. Наша мета — знайти найкоротший можливий шлях для проходження маршруту туди й назад.
Приклад TSP
Тут подано графік, де 1, 2, 3 і 4 представляють міста, а вага, пов’язана з кожним краєм, представляє відстань між цими містами.
Мета полягає в тому, щоб знайти найкоротший шлях для туру, який починається з початкового міста, перетинає графік, відвідуючи інші міста або вузли лише один раз, і повертається до початкового міста.
Для наведеного вище графіка оптимальним маршрутом є слідування шляху мінімальних витрат: 1-2-4-3-1. І цей найкоротший маршрут коштував би 10+25+30+15 =80
Різні рішення проблеми комівояжера
Задача комівояжера (TSP) класифікується як NP-складна задача через відсутність поліноміального алгоритму часу. Складність експоненціально зростає зі збільшенням кількості міст.
Існує кілька способів вирішення проблеми комівояжера (tsp). Деякі популярні рішення:
Підхід грубої сили є наївним методом для вирішення проблем комівояжера. У цьому підході ми спочатку обчислюємо всі можливі шляхи, а потім порівнюємо їх. Кількість шляхів у графі, що складається з n міст, дорівнює n! Вирішити проблему комівояжера за допомогою цього підходу грубої сили обчислювально дуже дорого.
Метод розгалужень і меж: У цьому підході проблема розбивається на підпроблеми. Рішення цих окремих підпроблем забезпечить оптимальне рішення.
У цьому підручнику буде продемонстровано підхід до динамічного програмування, рекурсивну версію цього методу розгалужень і меж, для вирішення проблеми комівояжера.
Динамічне програмування є таким методом пошуку оптимальних рішень шляхом аналізу всіх можливих маршрутів. Це один із точних методів вирішення проблем комівояжера за рахунок відносно вищих витрат, ніж жадібні методи які забезпечують майже оптимальне рішення.
Обчислювальна складність цього підходу полягає в тому O(N^2 * 2^N) який обговорюється далі в цій статті.
Метод найближчого сусіда це евристичний жадібний підхід, де ми вибираємо найближчий сусідній вузол. Цей підхід обчислюється дешевше, ніж динамічний підхід. Але це не дає гарантії оптимального рішення. Цей метод використовується для наближених до оптимальних рішень.
Алгоритм задачі комівояжера
Ми будемо використовувати підхід динамічного програмування для вирішення проблеми комівояжера (TSP).
Перш ніж почати роботу з алгоритмом, давайте познайомимося з деякими термінами:
- Граф G=(V, E), який є набором вершин і ребер.
- V — множина вершин.
- E — множина ребер.
- Вершини з'єднуються через ребра.
- Dist(i,j) позначає невід’ємну відстань між двома вершинами, i та j.
Припустімо, що S є підмножиною міст і належить до {1, 2, 3, …, n}, де 1, 2, 3…n – міста, а i, j – два міста в цій підмножині. Тепер вартість (i, S, j) визначається таким чином, як довжина найкоротшого шляху відвідування вузла в S, який рівно один раз має початкову та кінцеву точки як i та j відповідно.
Наприклад, вартість (1, {2, 3, 4}, 1) позначає довжину найкоротшого шляху, де:
- Початкове місто 1
- Міста 2, 3 і 4 відвідуються лише один раз
- Кінцева точка - 1
Алгоритм динамічного програмування буде таким:
- Встановіть cost(i, , i) = 0, що означає, що ми починаємо і закінчуємо в i, а вартість дорівнює 0.
- Коли |S| > 1, ми визначаємо cost(i, S, 1) = ∝, де i !=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, встановимо вартість відстані (i, S, 1) = ∝. Тут вартість (i, S, j) означає, що ми починаємо з міста i, відвідуємо міста S один раз, і тепер ми знаходимося в місті j. Ми встановили цю вартість шляху як нескінченність, оскільки ми ще не знаємо відстані. Отже, значення будуть такими:
Вартість (2, {3, 4}, 1) = ∝ ; позначення вказує на те, що ми починаємо з міста 2, проходимо через міста 3, 4 і досягаємо 1. А вартість шляху нескінченна. Так само-
вартість (3, {2, 4}, 1) = ∝
вартість (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, оптимальна вартість шляху буде = вартість (1, {інші міста}, 1).
Давайте дізнаємося, як ми можемо цього досягти:
Тепер S = {1, 2, 3, 4}. Є чотири елементи. Отже, кількість підмножин буде 2^4 або 16. Ці підмножини є-
1) |S| = Null:
{Φ}
2) |S| = 1:
{{1}, {2}, {3}, {4}}
3) |S| = 2:
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |S| = 3:
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |S| = 4:
{{1, 2, 3, 4}}
Оскільки ми починаємо з 1, ми можемо відкинути підмножини, що містять місто 1.
Алгоритм розрахунку:
1) |S| = Φ:
вартість (2, Φ, 1) = dist(2, 1) = 10
вартість (3, Φ, 1) = dist(3, 1) = 15
вартість (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 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) |S| = 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) |S| = 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
- Складність часу: Всього їх 2 XNUMXN підзадачі для кожного вузла. Отже, загальна кількість підпроблем буде N*2N. Для вирішення кожної з підпроблем потрібен лінійний час. Якщо вихідний вузол не вказано, ми повинні запустити цикли для N вузлів.
Таким чином, загальна складність часу для оптимального рішення буде кількістю вузлів * кількістю підпроблем * часом вирішення кожної підпроблеми. Часову складність можна визначити як O(N2 * 2^N).
- Складність простору: Підхід динамічного програмування використовує пам'ять для зберігання C(S, i), де S є підмножиною набору вершин. Всього їх 2N підмножини для кожного вузла. Отже, просторова складність дорівнює O(2^N).
Далі ви дізнаєтеся про Алгоритм «Решето Ератосфена».
