Проблем с пътуващия търговец: 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 са два града в това подмножество. Сега cost(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) = ∝. Тук 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, трябва да намерим следното:
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| = нула:
{Φ}
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
- Времева сложност: Има общо 2N подпроблеми за всеки възел. Така че общият брой подпроблеми ще бъде N*2N. Всеки от подпроблемите изисква линейно време за решаване. Ако началният възел не е посочен, трябва да стартираме цикли за N възела.
Така че общата времева сложност за оптимално решение ще бъде Броят на възлите * Броят на подпроблемите * времето за решаване на всеки подпроблем. Времевата сложност може да се дефинира като O(N2 * 2^N).
- Космическа сложност: Подходът на динамичното програмиране използва памет за съхраняване на C(S, i), където S е подмножество от набора от върхове. Има общо 2 брN подмножества за всеки възел. И така, пространствената сложност е O(2^N).
След това ще научите за Алгоритъмът Сито на Ератостен
