Problem komiwojażera: Python, C++ Algorytm
Sara Chen
Na czym polega problem komiwojażera (TSP)?
Problem komiwojażera (TSP) to klasyczny problem kombinatoryki informatyki teoretycznej. Problem polega na znalezieniu najkrótszej ścieżki w grafie pod warunkiem odwiedzenia wszystkich węzłów tylko raz i powrotu do miasta początkowego.
Opis problemu zawiera listę miast wraz z odległościami pomiędzy nimi.
Cel: Aby rozpocząć od miasta początkowego, odwiedź inne miasta tylko raz i ponownie wróć do pierwotnego miasta. Naszym celem jest znalezienie najkrótszej możliwej ścieżki, aby ukończyć trasę w obie strony.
Przykład TSP
Poniżej podano wykres, w którym liczby 1, 2, 3 i 4 reprezentują miasta, a waga przypisana każdej krawędzi reprezentuje odległość między tymi miastami.
Celem jest znalezienie najkrótszej możliwej ścieżki dla wycieczki, która rozpoczyna się od miasta początkowego, przechodzi przez wykres, odwiedzając tylko raz inne miasta lub węzły, i wraca do miasta początkowego.
Dla powyższego wykresu optymalną trasą jest podążanie ścieżką minimalnego kosztu: 1-2-4-3-1. A ta najkrótsza trasa będzie kosztować 10+25+30+15 = 80
Różne rozwiązania problemu komiwojażera
Problem komiwojażera (TSP) jest klasyfikowany jako problem NP-trudny, ponieważ nie ma algorytmu wielomianowego. Złożoność wzrasta wykładniczo wraz ze wzrostem liczby miast.
Istnieje wiele sposobów rozwiązania problemu komiwojażera (tsp). Niektóre popularne rozwiązania to:
Podejście brutalnej siły jest metodą naiwną do rozwiązywania problemów komiwojażera. W tym podejściu najpierw obliczamy wszystkie możliwe ścieżki, a następnie je porównujemy. Liczba ścieżek w grafie składającym się z n miast wynosi n! Rozwiązanie problemu komiwojażera przy użyciu tej metody brutalnej siły jest bardzo kosztowne obliczeniowo.
Metoda rozgałęzień i wiązań: W tym podejściu problem jest dzielony na podproblemy. Rozwiązanie tych poszczególnych podproblemów zapewniłoby rozwiązanie optymalne.
W tym samouczku zaprezentowane zostanie podejście do programowania dynamicznego, rekurencyjna wersja tej metody rozgałęzionej, służące do rozwiązania problemu komiwojażera.
Programowanie dynamiczne to taka metoda poszukiwania optymalnych rozwiązań poprzez analizę wszystkich możliwych tras. Jest to jedna z dokładnych metod rozwiązywania problemów komiwojażera przy stosunkowo wyższych kosztach niż chciwe metody które zapewniają rozwiązanie niemal optymalne.
Złożoność obliczeniowa tego podejścia wynosi O(N^2 * 2^N) co zostanie omówione dalej w tym artykule.
Metoda najbliższego sąsiada jest heurystycznym podejściem zachłannym, w którym wybieramy najbliższy węzeł sąsiada. To podejście jest obliczeniowo mniej kosztowne niż podejście dynamiczne. Ale nie daje gwarancji optymalnego rozwiązania. Ta metoda jest używana do rozwiązań zbliżonych do optymalnych.
Algorytm problemu komiwojażera
Do rozwiązania problemu komiwojażera (TSP) zastosujemy podejście programowania dynamicznego.
Przed rozpoczęciem algorytmu zapoznajmy się z niektórymi terminologiami:
- Graf G=(V, E), który jest zbiorem wierzchołków i krawędzi.
- V jest zbiorem wierzchołków.
- E jest zbiorem krawędzi.
- Wierzchołki są połączone krawędziami.
- Dist(i,j) oznacza nieujemną odległość pomiędzy dwoma wierzchołkami, i oraz j.
Załóżmy, że S jest podzbiorem miast i należy do {1, 2, 3,…, n}, gdzie 1, 2, 3…n to miasta, a i, j to dwa miasta w tym podzbiorze. Teraz koszt(i, S, j) definiuje się w taki sposób, jak długość najkrótszej ścieżki odwiedzającej węzeł w S, który dokładnie raz ma punkt początkowy i końcowy odpowiednio i i j.
Na przykład koszt (1, {2, 3, 4}, 1) oznacza długość najkrótszej ścieżki, gdzie:
- Miasto początkowe to 1
- Miasta 2, 3 i 4 odwiedza się tylko raz
- Punktem końcowym jest 1
Algorytm programowania dynamicznego wyglądałby następująco:
- Ustaw koszt(i, , i) = 0, co oznacza, że zaczynamy i kończymy na i, a koszt wynosi 0.
- Kiedy |S| > 1, definiujemy koszt(i, S, 1) = ∝ gdzie i !=1 . Ponieważ początkowo nie znamy dokładnego kosztu dotarcia do miasta i do miasta 1 przez inne miasta.
- Teraz musimy zacząć od 1 i zakończyć wycieczkę. Musimy wybrać kolejne miasto w taki sposób-
koszt(i, S, j)=min koszt (i, S−{i}, j)+odległość(i,j) gdzie i∈S oraz i≠j
Dla podanego rysunku macierz sąsiedztwa wyglądałaby następująco:
| odległość(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 |
Zobaczmy jak działa nasz algorytm:
Krok 1) Rozważamy rozpoczęcie podróży w mieście 1, odwiedzenie raz innych miast i powrót do miasta 1.
Krok 2) S jest podzbiorem miast. Zgodnie z naszym algorytmem, dla wszystkich |S| > 1, ustalimy koszt odległości cost(i, S, 1) = ∝. Tutaj cost(i, S, j) oznacza, że zaczynamy w mieście i, odwiedzając miasta S raz, a teraz jesteśmy w mieście j. Ustalamy ten koszt ścieżki jako nieskończoność, ponieważ nie znamy jeszcze odległości. Wartości będą więc następujące:
Koszt (2, {3, 4}, 1) = ∝ ; zapis oznacza, że zaczynamy od miasta 2, przechodzimy przez miasta 3, 4 i docieramy do 1. Koszt ścieżki jest nieskończony. Podobnie-
koszt(3, {2, 4}, 1) = ∝
koszt(4, {2, 3}, 1) = ∝
Krok 3) Teraz dla wszystkich podzbiorów S musimy znaleźć następujące dane:
koszt(i, S, j)=min koszt (i, S−{i}, j)+odległość(i,j), gdzie j∈S i i≠j
Oznacza to ścieżkę minimalnego kosztu rozpoczęcia w i, jednokrotnego przejścia przez podzbiór miast i powrotu do miasta j. Biorąc pod uwagę, że podróż rozpoczyna się w mieście 1, optymalny koszt trasy będzie wynosić= koszt(1, {inne miasta}, 1).
Dowiedzmy się, jak możemy to osiągnąć:
Teraz S = {1, 2, 3, 4}. Istnieją cztery elementy. Zatem liczba podzbiorów będzie wynosić 2^4 lub 16. Podzbiory te to:
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}}
Ponieważ zaczynamy od 1, możemy odrzucić podzbiory zawierające miasto 1.
Obliczenie algorytmu:
1) |S| = Φ:
koszt (2, Φ, 1) = odległość (2, 1) = 10
koszt (3, Φ, 1) = odległość (3, 1) = 15
koszt (4, Φ, 1) = odległość (4, 1) = 20
2) |S| = 1:
koszt (2, {3}, 1) = odległość (2, 3) + koszt (3, Φ, 1) = 35+15 = 50
koszt (2, {4}, 1) = odległość (2, 4) + koszt (4, Φ, 1) = 25+20 = 45
koszt (3, {2}, 1) = odległość (3, 2) + koszt (2, Φ, 1) = 35+10 = 45
koszt (3, {4}, 1) = odległość (3, 4) + koszt (4, Φ, 1) = 30+20 = 50
koszt (4, {2}, 1) = odległość (4, 2) + koszt (2, Φ, 1) = 25+10 = 35
koszt (4, {3}, 1) = odległość (4, 3) + koszt (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
koszt (2, {3, 4}, 1) = min [odległość[2,3]+koszt(3,{4},1) = 35+50 = 85,
dyst[2,4]+koszt(4,{3},1) = 25+45 = 70 ] = 70
koszt (3, {2, 4}, 1) = min [odległość[3,2]+koszt(2,{4},1) = 35+45 = 80,
dyst[3,4]+koszt(4,{2},1) = 30+35 = 65 ] = 65
koszt (4, {2, 3}, 1) = min [odległość[4,2]+koszt(2,{3},1) = 25+50 = 75
dyst[4,3]+koszt(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3:
koszt (1, {2, 3, 4}, 1) = min [ odległość[1,2]+koszt(2,{3,4},1) = 10+70 = 80
dyst[1,3]+koszt(3,{2,4},1) = 15+65 = 80
dyst[1,4]+koszt(4,{2,3},1) = 20+75 = 95 ] = 80
Zatem optymalnym rozwiązaniem byłoby 1-2-4-3-1
Pseudo kod
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)
Implementacja w C/C++
Oto implementacja w 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;
}
Wyjście:
80
wdrożenie w 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))
Wyjście:
80
Rozwiązania akademickie dla TSP
Informatycy spędzili lata na poszukiwaniu ulepszonego algorytmu wielomianowego dla problemu komiwojażera. Do tej pory problem ten jest nadal NP-trudny.
Chociaż w ostatnich latach opublikowano kilka z poniższych rozwiązań, które w pewnym stopniu ograniczyły złożoność:
- Klasyczny symetryczny TSP jest rozwiązywany metodą zerowego przyrostka.
- Algorytm optymalizacji oparty na biogeografii opiera się na strategii migracji w celu rozwiązania problemów optymalizacyjnych, które można zaplanować jako TSP.
- Wieloobiektowy algorytm ewolucyjny przeznaczony jest do rozwiązywania wielu problemów TSP w oparciu o NSGA-II.
- System wieloagentowy rozwiązuje TSP N miast o stałych zasobach.
Zastosowanie problemu komiwojażera
Problem komiwojażera (TSP) ma zastosowanie w świecie rzeczywistym zarówno w najczystszej, jak i zmodyfikowanej formie. Niektóre z nich to:
- Planowanie, logistyka i produkcja mikrochipów: Problemy z osadzaniem chipów pojawiają się naturalnie w branży mikrochipów. Problemy te można zaplanować jako problemy komiwojażera.
- Sekwencjonowanie DNA: W sekwencjonowaniu DNA można zastosować niewielką modyfikację problemu komiwojażera. Tutaj miasta reprezentują fragmenty DNA, a odległość reprezentuje miarę podobieństwa między dwoma fragmentami DNA.
- Astronomia:Astronomowie stosują problem komiwojażera w celu zminimalizowania czasu spędzanego na obserwacji różnych źródeł.
- Problem optymalnego sterowania: Problem komiwojażera Sformułowanie problemu można zastosować w problemach optymalnego sterowania. Może zostać dodanych kilka innych ograniczeń.
Analiza złożoności TSP
- Złożoność czasowa: Jest ich w sumie 2N podproblemy dla każdego węzła. Zatem całkowita liczba podproblemów wyniesie N*2N. Rozwiązanie każdego z podproblemów wymaga liniowego czasu. Jeśli węzeł początkowy nie jest określony, musimy uruchomić pętle dla N węzłów.
Tak więc całkowita złożoność czasowa dla optymalnego rozwiązania będzie równa: Liczba węzłów * Liczba podproblemów * czas rozwiązania każdego podproblemu. Złożoność czasowa może być zdefiniowana jako O(N2 *2^N).
- Złożoność przestrzeni: Podejście do programowania dynamicznego wykorzystuje pamięć do przechowywania C(S, i), gdzie S jest podzbiorem zbioru wierzchołków. W sumie jest 2N podzbiory dla każdego węzła. Zatem złożoność przestrzenna wynosi O(2^N).
Następnie dowiesz się o Algorytm sita Eratostenesa