Problema vânzătorului călător: Python, C++ Algoritm
Sarah Chen
Ce este problema vânzătorului ambulant (TSP)?
Travelling Salesman Problem (TSP) este o problemă clasică de combinatorie a informaticii teoretice. Problema cere să găsiți cea mai scurtă cale într-un grafic cu condiția de a vizita toate nodurile o singură dată și de a reveni la orașul de origine.
Declarația problemei oferă o listă de orașe împreună cu distanțele dintre fiecare oraș.
Obiectiv: Pentru a începe din orașul de origine, vizitați alte orașe o singură dată și reveniți din nou la orașul inițial. Ținta noastră este să găsim cea mai scurtă cale posibilă pentru a finaliza traseul dus-întors.
Exemplu de TSP
Aici este dat un grafic unde 1, 2, 3 și 4 reprezintă orașele, iar ponderea asociată cu fiecare margine reprezintă distanța dintre acele orașe.
Scopul este de a găsi cea mai scurtă cale posibilă pentru turul care pornește din orașul de origine, traversează graficul în timp ce vizitează o singură dată celelalte orașe sau noduri și se întoarce la orașul de origine.
Pentru graficul de mai sus, ruta optimă este să urmați calea costului minim: 1-2-4-3-1. Și această rută cea mai scurtă ar costa 10+25+30+15 =80
Diferite soluții la problema vânzătorului călători
Problema vânzătorului călător (TSP) este clasificată ca o problemă NP-hard datorită faptului că nu are un algoritm de timp polinomial. Complexitatea crește exponențial prin creșterea numărului de orașe.
Există mai multe moduri de a rezolva problema vânzătorului ambulant (tsp). Câteva soluții populare sunt:
Abordarea forței brute este metoda naivă pentru rezolvarea problemelor vânzătorilor ambulanți. În această abordare, mai întâi calculăm toate căile posibile și apoi le comparăm. Numărul de căi dintr-un grafic format din n orașe este n! Este foarte costisitor din punct de vedere computațional să rezolvi problema vânzătorului ambulant în această abordare cu forța brută.
Metoda de ramificare și legare: Problema este împărțită în sub-probleme în această abordare. Rezolvarea acestor sub-probleme individuale ar oferi o soluție optimă.
Acest tutorial va demonstra o abordare de programare dinamică, versiunea recursivă a acestei metode branch-and-bound, pentru a rezolva problema vânzătorului ambulant.
Programare dinamică este o astfel de metodă de căutare a soluțiilor optime prin analiza tuturor rutelor posibile. Este una dintre metodele exacte de rezolvare care rezolvă problemele vânzătorilor călători prin costuri relativ mai mari decât cele metode lacome care oferă o soluție aproape optimă.
Complexitatea computațională a acestei abordări este O(N^2 * 2^N) despre care se discută mai târziu în acest articol.
Metoda celui mai apropiat vecin este o abordare lacomă bazată pe euristică în care alegem cel mai apropiat nod vecin. Această abordare este mai puțin costisitoare din punct de vedere computațional decât abordarea dinamică. Dar nu oferă garanția unei soluții optime. Această metodă este utilizată pentru soluții aproape optime.
Algoritm pentru problema vânzătorului ambulant
Vom folosi abordarea de programare dinamică pentru a rezolva problema Travelling Salesman (TSP).
Înainte de a începe algoritmul, să ne familiarizăm cu câteva terminologii:
- Un grafic G=(V, E), care este un set de vârfuri și muchii.
- V este mulțimea de vârfuri.
- E este mulțimea muchiilor.
- Vârfurile sunt conectate prin margini.
- Dist(i,j) denotă distanța nenegativă dintre două vârfuri, i și j.
Să presupunem că S este submulțimea orașelor și aparține lui {1, 2, 3, …, n} unde 1, 2, 3…n sunt orașele și i, j sunt două orașe din acea submulțime. Acum costul (i, S, j) este definit în așa fel ca lungimea celui mai scurt nod care vizitează calea din S, care are exact o dată punctul de început și de sfârșit ca i și, respectiv, j.
De exemplu, costul (1, {2, 3, 4}, 1) denotă lungimea celei mai scurte căi unde:
- Orașul de pornire este 1
- Orașele 2, 3 și 4 sunt vizitate o singură dată
- Punctul final este 1
Algoritmul de programare dinamică ar fi:
- Setați cost(i, , i) = 0, ceea ce înseamnă că începem și se termină la i, iar costul este 0.
- Când |S| > 1, definim cost(i, S, 1) = ∝ unde i !=1 . Pentru că inițial, nu știm costul exact pentru a ajunge la orașul i până la orașul 1 prin alte orașe.
- Acum, trebuie să începem la 1 și să încheiem turul. Trebuie să alegem următorul oraș în așa fel -
cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j) unde i∈S și i≠j
Pentru figura dată, matricea de adiacență ar fi următoarea:
| 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 |
Să vedem cum funcționează algoritmul nostru:
Pas 1) Luăm în considerare călătoria noastră începând din orașul 1, să vizităm alte orașe o dată și să ne întoarcem în orașul 1.
Pas 2) S este submulțimea orașelor. Conform algoritmului nostru, pentru toate |S| > 1, vom stabili costul distanței (i, S, 1) = ∝. Aici cost(i, S, j) înseamnă că începem din orașul i, vizitând orașele din S o dată, iar acum suntem în orașul j. Am stabilit acest cost de cale la infinit pentru că nu știm încă distanța. Deci valorile vor fi următoarele:
Cost (2, {3, 4}, 1) = ∝ ; notația denotă că începem cu orașul 2, trecem prin orașele 3, 4 și ajungem la 1. Și costul căii este infinit. În mod similar-
cost(3, {2, 4}, 1) = ∝
cost(4, {2, 3}, 1) = ∝
Pas 3) Acum, pentru toate submulțimile lui S, trebuie să găsim următoarele:
cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j), unde j∈S și i≠j
Aceasta înseamnă calea costului minim pentru începerea de la i, trecerea prin subsetul de orașe o dată și revenirea la orașul j. Având în vedere că călătoria începe din orașul 1, costul optim al traseului ar fi= cost(1, {alte orașe}, 1).
Să aflăm cum am putea realiza asta:
Acum S = {1, 2, 3, 4}. Sunt patru elemente. Prin urmare, numărul de subseturi va fi 2^4 sau 16. Acele subseturi sunt-
1) |S| = nul:
{Φ}
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}}
Deoarece începem de la 1, am putea elimina subseturile care conțin orașul 1.
Calculul algoritmului:
1) |S| = Φ:
cost (2, Φ, 1) = dist(2, 1) = 10
cost (3, Φ, 1) = dist(3, 1) = 15
cost (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
cost (2, {3}, 1) = dist(2, 3) + cost (3, Φ, 1) = 35+15 = 50
cost (2, {4}, 1) = dist(2, 4) + cost (4, Φ, 1) = 25+20 = 45
cost (3, {2}, 1) = dist(3, 2) + cost (2, Φ, 1) = 35+10 = 45
cost (3, {4}, 1) = dist(3, 4) + cost (4, Φ, 1) = 30+20 = 50
cost (4, {2}, 1) = dist(4, 2) + cost (2, Φ, 1) = 25+10 = 35
cost (4, {3}, 1) = dist(4, 3) + cost (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
cost (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
cost (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
cost (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:
cost (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
Deci soluția optimă ar fi 1-2-4-3-1
Pseudo cod
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)
Implementare in C/C++
Iată implementarea în 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;
}
ieșire:
80
Implementarea în 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))
ieșire:
80
Soluții academice pentru TSP
Informaticienii au petrecut ani de zile căutând un algoritm de timp polinomial îmbunătățit pentru problema vânzătorului călător. Până acum, problema este încă NP-grea.
Deși unele dintre următoarele soluții au fost publicate în ultimii ani, care au redus complexitatea într-o anumită măsură:
- TSP simetric clasic este rezolvat prin Metoda Sufixului Zero.
- Algoritmul de optimizare bazat pe biogeografie se bazează pe strategia de migrare pentru a rezolva problemele de optimizare care pot fi planificate ca TSP.
- Algoritmul evolutiv multi-obiectiv este conceput pentru rezolvarea mai multor TSP pe baza NSGA-II.
- Sistemul Multi-Agent rezolvă TSP-ul a N orașe cu resurse fixe.
Aplicarea problemei vânzătorului călători
Travelling Salesman Problem (TSP) este aplicat în lumea reală atât în cele mai pure forme, cât și în cele mai modificate. Unele dintre acestea sunt:
- Planificare, logistică și producție de microcipuri: Problemele de inserare a cipurilor apar în mod natural în industria microcipurilor. Aceste probleme pot fi planificate ca probleme de vânzător ambulant.
- Secvențierea ADN-ului: Modificarea ușoară a problemei vânzătorului ambulant poate fi utilizată în secvențierea ADN-ului. Aici, orașele reprezintă fragmentele de ADN, iar distanța reprezintă măsura de similitudine dintre două fragmente de ADN.
- Astronomie: Problema vânzătorului călător este aplicată de astronomi pentru a minimiza timpul petrecut observând diverse surse.
- Problemă de control optim: Travelling Salesman Formularea problemei poate fi aplicată în probleme de control optim. S-ar putea să fie adăugate câteva alte constrângeri.
Analiza complexității TSP
- Complexitatea timpului: În total sunt 2N subprobleme pentru fiecare nod. Deci numărul total de subprobleme ar fi N*2N. Fiecare dintre sub-probleme necesită timp liniar pentru rezolvare. Dacă nodul de origine nu este specificat, trebuie să rulăm bucle pentru N noduri.
Deci, complexitatea totală a timpului pentru o soluție optimă ar fi Numărul de noduri * Numărul de subprobleme * timpul de rezolvare a fiecărei subprobleme. Complexitatea timpului poate fi definită ca O(N2 * 2^N).
- Complexitatea spațială: Abordarea de programare dinamică folosește memoria pentru a stoca C(S, i), unde S este o submulțime a setului de vârfuri. Există un total de 2N subseturi pentru fiecare nod. Deci, complexitatea spațiului este O(2^N).
În continuare, veți afla despre Algoritmul Sita lui Eratosthenes
