Problem trgovačkog putnika: Python, C++ Algoritam
Sarah Chen
Što je problem trgovačkog putnika (TSP)?
Problem trgovačkog putnika (TSP) klasični je kombinatorički problem teorijske računalne znanosti. Problem traži pronalaženje najkraćeg puta u grafu uz uvjet da se posjećuju svi čvorovi samo jednom i vraća se u ishodišni grad.
Izjava problema daje popis gradova zajedno s udaljenostima između svakog grada.
Cilj: Da biste krenuli od izvornog grada, posjetite druge gradove samo jednom i ponovno se vratite u izvorni grad. Naš cilj je pronaći najkraći mogući put za završetak povratne rute.
Primjer TSP-a
Ovdje je dan grafikon gdje 1, 2, 3 i 4 predstavljaju gradove, a težina povezana sa svakim rubom predstavlja udaljenost između tih gradova.
Cilj je pronaći najkraći mogući put za obilazak koji počinje od ishodišnog grada, prelazi graf dok samo jednom posjećuje ostale gradove ili čvorove i vraća se u izvorni grad.
Za gornji grafikon, optimalna ruta je slijediti putanju minimalnih troškova: 1-2-4-3-1. A ova najkraća ruta bi koštala 10+25+30+15 =80
Različita rješenja problema trgovačkog putnika
Problem trgovačkog putnika (TSP) klasificira se kao NP-teški problem jer nema polinomijalni vremenski algoritam. Složenost eksponencijalno raste povećanjem broja gradova.
Postoji više načina za rješavanje problema trgovačkog putnika (tsp). Neka popularna rješenja su:
Pristup grube sile je naivna metoda za rješavanje problema trgovačkog putnika. U ovom pristupu prvo izračunavamo sve moguće putove, a zatim ih uspoređujemo. Broj staza u grafu koji se sastoji od n gradova je n! Računalno je vrlo skupo riješiti problem trgovačkog putnika u ovom brutalnom pristupu.
Metoda grananja i povezivanja: Problem je u ovom pristupu podijeljen na podprobleme. Rješenje tih pojedinačnih podproblema dalo bi optimalno rješenje.
Ovaj vodič će demonstrirati pristup dinamičkom programiranju, rekurzivnu verziju ove metode grananja i povezivanja, za rješavanje problema trgovačkog putnika.
Dinamičko programiranje je takva metoda za traženje optimalnih rješenja analizom svih mogućih ruta. To je jedna od točnih metoda rješenja koja rješava probleme trgovačkih putnika kroz relativno veće troškove od pohlepne metode koji pružaju gotovo optimalno rješenje.
Računalna složenost ovog pristupa je O(N^2 * 2^N) o čemu se govori kasnije u ovom članku.
Metoda najbližeg susjeda je heuristički temeljen pohlepan pristup gdje biramo najbliži susjedni čvor. Ovaj pristup je računski jeftiniji od dinamičkog pristupa. Ali to ne daje jamstvo optimalnog rješenja. Ova se metoda koristi za gotovo optimalna rješenja.
Algoritam za problem trgovačkog putnika
Koristit ćemo pristup dinamičkog programiranja za rješavanje problema trgovačkog putnika (TSP).
Prije pokretanja algoritma, upoznajmo se s nekim terminologijama:
- Graf G=(V, E), koji je skup vrhova i bridova.
- V je skup vrhova.
- E je skup bridova.
- Vrhovi su povezani bridovima.
- Dist(i,j) označava nenegativnu udaljenost između dva vrha, i i j.
Pretpostavimo da je S podskup gradova i da pripada {1, 2, 3, …, n} gdje su 1, 2, 3…n gradovi, a i, j su dva grada u tom podskupu. Sada je cijena(i, S, j) definirana na takav način kao duljina najkraćeg puta koji posjećuje čvor u S, koji točno jednom ima početnu i završnu točku kao i odnosno j.
Na primjer, cijena (1, {2, 3, 4}, 1) označava duljinu najkraćeg puta gdje je:
- Početni grad je 1
- Gradovi 2, 3 i 4 posjećuju se samo jednom
- Završna točka je 1
Algoritam dinamičkog programiranja bio bi:
- Postavite cost(i, , i) = 0, što znači da počinjemo i završavamo na i, a trošak je 0.
- Kada |S| > 1, definiramo trošak(i, S, 1) = ∝ gdje je i !=1 . Budući da u početku ne znamo točnu cijenu dolaska od grada i do grada 1 kroz druge gradove.
- Sada, moramo početi u 1 i završiti obilazak. Moramo odabrati sljedeći grad na takav način-
trošak(i, S, j)=min trošak (i, S−{i}, j)+dist(i,j) gdje su i∈S i i≠j
Za danu sliku, matrica susjedstva bila bi sljedeća:
| 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 |
Pogledajmo kako funkcionira naš algoritam:
Korak 1) Razmatramo da naše putovanje započne u gradu 1, posjeti druge gradove jednom i vrati se u grad 1.
Korak 2) S je podskup gradova. Prema našem algoritmu, za sve |S| > 1, postavit ćemo cijenu udaljenosti(i, S, 1) = ∝. Ovdje trošak(i, S, j) znači da počinjemo u gradu i, posjećujemo gradove S jednom, a sada smo u gradu j. Postavili smo ovu cijenu puta kao beskonačnu jer još ne znamo udaljenost. Dakle, vrijednosti će biti sljedeće:
Trošak (2, {3, 4}, 1) = ∝; oznaka označava da počinjemo od grada 2, prolazimo kroz gradove 3, 4 i dolazimo do 1. A cijena puta je beskonačna. Slično-
trošak(3, {2, 4}, 1) = ∝
trošak(4, {2, 3}, 1) = ∝
Korak 3) Sada, za sve podskupove od S, moramo pronaći sljedeće:
trošak(i, S, j)=min trošak (i, S−{i}, j)+dist(i,j), gdje j∈S i i≠j
To znači put minimalne cijene za početak od i, prolazak kroz podskup gradova jednom i povratak u grad j. Uzimajući u obzir da putovanje počinje u gradu 1, optimalni trošak puta bio bi= trošak(1, {ostali gradovi}, 1).
Otkrijmo kako to možemo postići:
Sada je S = {1, 2, 3, 4}. Postoje četiri elementa. Stoga će broj podskupova biti 2^4 ili 16. Ti podskupovi su-
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}}
Kako počinjemo od 1, mogli bismo odbaciti podskupove koji sadrže grad 1.
Izračun algoritma:
1) |S| = Φ:
trošak (2, Φ, 1) = dist(2, 1) = 10
trošak (3, Φ, 1) = dist(3, 1) = 15
trošak (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
trošak (2, {3}, 1) = dist(2, 3) + trošak (3, Φ, 1) = 35+15 = 50
trošak (2, {4}, 1) = dist(2, 4) + trošak (4, Φ, 1) = 25+20 = 45
trošak (3, {2}, 1) = dist(3, 2) + trošak (2, Φ, 1) = 35+10 = 45
trošak (3, {4}, 1) = dist(3, 4) + trošak (4, Φ, 1) = 30+20 = 50
trošak (4, {2}, 1) = dist(4, 2) + trošak (2, Φ, 1) = 25+10 = 35
trošak (4, {3}, 1) = dist(4, 3) + trošak (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
trošak (2, {3, 4}, 1) = min [ dist[2,3]+trošak(3,{4},1) = 35+50 = 85,
dist[2,4]+Cost(4,{3},1) = 25+45 = 70 ] = 70
trošak (3, {2, 4}, 1) = min [ dist[3,2]+trošak(2,{4},1) = 35+45 = 80,
dist[3,4]+Cost(4,{2},1) = 30+35 = 65 ] = 65
trošak (4, {2, 3}, 1) = min [ dist[4,2]+trošak(2,{3},1) = 25+50 = 75
dist[4,3]+Cost(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3:
trošak (1, {2, 3, 4}, 1) = min [ dist[1,2]+trošak(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
Dakle, optimalno rješenje bi bilo 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)
Implementacija u C/C++
Evo implementacije u 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;
}
Izlaz:
80
Implementacija u 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))
Izlaz:
80
Akademska rješenja za TSP
Računalni znanstvenici proveli su godine tražeći poboljšani polinomski vremenski algoritam za problem trgovačkog putnika. Do sada je problem još uvijek NP-težak.
Iako su posljednjih godina objavljena neka od sljedećih rješenja koja su do određenog stupnja smanjila složenost:
- Klasični simetrični TSP rješava se metodom nultog sufiksa.
- Optimizacijski algoritam temeljen na biogeografiji temelji se na strategiji migracije za rješavanje problema optimizacije koji se mogu planirati kao TSP.
- Multi-Objective Evolutionary Algorithm dizajniran je za rješavanje višestrukih TSP-ova na temelju NSGA-II.
- Sustav s više agenata rješava TSP N gradova s fiksnim resursima.
Primjena problema trgovačkog putnika
Problem trgovačkog putnika (TSP) primjenjuje se u stvarnom svijetu u svom najčišćem i modificiranom obliku. Neki od njih su:
- Planiranje, logistika i proizvodnja mikročipova: Problemi s umetanjem čipa prirodno se javljaju u industriji mikročipova. Ti se problemi mogu planirati kao problemi trgovačkog putnika.
- sekvenciranje DNA: Mala izmjena problema trgovačkog putnika može se koristiti u sekvenciranju DNK. Ovdje gradovi predstavljaju fragmente DNK, a udaljenost predstavlja mjeru sličnosti između dva fragmenta DNK.
- Astronomija: Problem trgovačkog putnika primjenjuju astronomi kako bi smanjili vrijeme provedeno u promatranju različitih izvora.
- Problem optimalnog upravljanja: Formulacija problema trgovačkog putnika može se primijeniti u problemima optimalnog upravljanja. Može biti dodano nekoliko drugih ograničenja.
Analiza složenosti TSP-a
- Složenost vremena: Ukupno ih je 2N podprobleme za svaki čvor. Tako bi ukupan broj podproblema bio N*2N. Svaki od podproblema zahtijeva linearno vrijeme za rješavanje. Ako izvorni čvor nije naveden, moramo pokrenuti petlje za N čvorova.
Dakle, ukupna vremenska složenost za optimalno rješenje bila bi broj čvorova * broj podproblema * vrijeme za rješavanje svakog podproblema. Vremenska složenost može se definirati kao O(N2 * 2^N).
- Složenost prostora: Pristup dinamičkog programiranja koristi memoriju za pohranu C(S, i), gdje je S podskup skupa vrhova. Ima ih ukupno 2N podskupove za svaki čvor. Dakle, složenost prostora je O(2^N).
Zatim ćete naučiti o Algoritam Eratostenovog sita
