Rejsende sælger problem: Python, C++ Algoritme
Sarah Chen
Hvad er Traveling Salesman Problem (TSP)?
Traveling Salesman Problem (TSP) er et klassisk kombinatorisk problem inden for teoretisk datalogi. Problemet beder om at finde den korteste vej i en graf med betingelsen om kun at besøge alle noderne én gang og vende tilbage til oprindelsesbyen.
Problemformuleringen giver en liste over byer sammen med afstandene mellem hver by.
Formål: For at starte fra oprindelsesbyen skal du kun besøge andre byer én gang og vende tilbage til den oprindelige by igen. Vores mål er at finde den kortest mulige vej for at fuldføre rundtursruten.
Eksempel på TSP
Her er givet en graf, hvor 1, 2, 3 og 4 repræsenterer byerne, og vægten forbundet med hver kant repræsenterer afstanden mellem disse byer.
Målet er at finde den kortest mulige vej for turen, der starter fra oprindelsesbyen, krydser grafen, mens du kun besøger de andre byer eller knudepunkter én gang, og vender tilbage til oprindelsesbyen.
For ovenstående graf er den optimale rute at følge minimumsomkostningsstien: 1-2-4-3-1. Og denne korteste rute ville koste 10+25+30+15 =80
Forskellige løsninger på rejsende sælgerproblem
Traveling Salesman Problem (TSP) er klassificeret som et NP-hårdt problem på grund af ingen polynomiel tidsalgoritme. Kompleksiteten øges eksponentielt ved at øge antallet af byer.
Der er flere måder at løse problemet med den rejsende sælger på (tsk). Nogle populære løsninger er:
Den brute force-tilgang er den naive metode til løsning af rejsende sælgerproblemer. I denne tilgang beregner vi først alle mulige stier og sammenligner dem derefter. Antallet af stier i en graf bestående af n byer er n! Det er beregningsmæssigt meget dyrt at løse problemet med den rejsende sælger i denne brute force-tilgang.
Gren-og-bund-metoden: Problemet er opdelt i delproblemer i denne tilgang. Løsningen af disse individuelle delproblemer ville give en optimal løsning.
Denne tutorial vil demonstrere en dynamisk programmeringstilgang, den rekursive version af denne branch-and-bound-metode, for at løse problemet med den rejsende sælger.
Dynamisk programmering er sådan en metode til at søge optimale løsninger ved at analysere alle mulige ruter. Det er en af de nøjagtige løsningsmetoder, der løser rejsende sælgerproblemer gennem relativt højere omkostninger end grådige metoder som giver en næsten optimal løsning.
Den beregningsmæssige kompleksitet af denne tilgang er O(N^2 * 2^N) som diskuteres senere i denne artikel.
Den nærmeste nabo metode er en heuristisk-baseret grådig tilgang, hvor vi vælger den nærmeste naboknude. Denne tilgang er beregningsmæssigt billigere end den dynamiske tilgang. Men det giver ikke garanti for en optimal løsning. Denne metode bruges til næsten optimale løsninger.
Algoritme for rejsende sælgerproblem
Vi vil bruge den dynamiske programmeringstilgang til at løse Traveling Salesman Problem (TSP).
Før du starter algoritmen, lad os stifte bekendtskab med nogle terminologier:
- En graf G=(V, E), som er et sæt af hjørner og kanter.
- V er mængden af toppunkter.
- E er sættet af kanter.
- Hjørner er forbundet gennem kanter.
- Dist(i,j) angiver den ikke-negative afstand mellem to toppunkter, i og j.
Lad os antage, at S er delmængden af byer og hører til {1, 2, 3, …, n} hvor 1, 2, 3…n er byerne og i, j er to byer i den delmængde. Nu er cost(i, S, j) defineret på en sådan måde som længden af den korteste vejbesøgsknude i S, som nøjagtigt én gang har start- og slutpunktet som henholdsvis i og j.
For eksempel angiver pris (1, {2, 3, 4}, 1) længden af den korteste vej, hvor:
- Startby er 1
- By 2, 3 og 4 besøges kun én gang
- Slutpunktet er 1
Den dynamiske programmeringsalgoritme ville være:
- Indstil pris(i, , i) = 0, hvilket betyder, at vi starter og slutter ved i, og prisen er 0.
- Når |S| > 1, definerer vi cost(i, S, 1) = ∝ hvor i !=1 . For i første omgang kender vi ikke de nøjagtige omkostninger for at nå by i til by 1 gennem andre byer.
- Nu skal vi starte kl. 1 og fuldføre turen. Vi skal vælge den næste by på en sådan måde-
cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j) hvor i∈S og i≠j
For den givne figur ville tilstødende matrix være følgende:
| 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 |
Lad os se, hvordan vores algoritme fungerer:
Trin 1) Vi overvejer vores rejse, der starter ved by 1, besøger andre byer én gang og vender tilbage til by 1.
Trin 2) S er delmængden af byer. Ifølge vores algoritme, for alle |S| > 1, vil vi indstille afstandsomkostningerne (i, S, 1) = ∝. Her betyder cost(i, S, j) at vi starter ved by i, besøger byerne S én gang, og nu er vi ved by j. Vi sætter denne vejpris som uendelig, fordi vi ikke kender afstanden endnu. Så værdierne vil være følgende:
Pris (2, {3, 4}, 1) = ∝ ; notationen angiver, at vi starter ved by 2, går gennem byer 3, 4 og når 1. Og vejomkostningerne er uendelige. På samme måde-
pris(3, {2, 4}, 1) = ∝
pris(4, {2, 3}, 1) = ∝
Trin 3) For alle delmængder af S skal vi nu finde følgende:
cost(i, S, j)=min cost (i, S−{i}, j)+distance(i,j), hvor j∈S og i≠j
Det betyder minimumsomkostningsstien for at starte ved i, gå gennem delmængden af byer én gang og vende tilbage til by j. I betragtning af, at rejsen starter ved by 1, ville den optimale stiomkostning være = cost(1, {andre byer}, 1).
Lad os finde ud af, hvordan vi kunne opnå det:
Nu er S = {1, 2, 3, 4}. Der er fire elementer. Derfor vil antallet af delmængder være 2^4 eller 16. Disse delmængder er-
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}}
Da vi starter ved 1, kunne vi kassere de delmængder, der indeholder by 1.
Algoritmeberegningen:
1) |S| = Φ:
pris (2, Φ, 1) = dist(2, 1) = 10
pris (3, Φ, 1) = dist(3, 1) = 15
pris (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
pris (2, {3}, 1) = dist(2, 3) + pris (3, Φ, 1) = 35+15 = 50
pris (2, {4}, 1) = dist(2, 4) + pris (4, Φ, 1) = 25+20 = 45
pris (3, {2}, 1) = dist(3, 2) + pris (2, Φ, 1) = 35+10 = 45
pris (3, {4}, 1) = dist(3, 4) + pris (4, Φ, 1) = 30+20 = 50
pris (4, {2}, 1) = dist(4, 2) + pris (2, Φ, 1) = 25+10 = 35
pris (4, {3}, 1) = dist(4, 3) + pris (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
pris (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
pris (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
pris (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:
pris (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
Så den optimale løsning ville være 1-2-4-3-1
Pseudo-kode
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)
Implementering i C/C++
Her er implementeringen i 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;
}
Output:
80
Gennemførelse i 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))
Output:
80
Akademiske løsninger til TSP
Dataloger har brugt årevis på at søge efter en forbedret polynomiel tidsalgoritme til Travelling Salesman Problem. Indtil nu er problemet stadig NP-hårdt.
Selvom nogle af følgende løsninger blev offentliggjort i de senere år, som har reduceret kompleksiteten til en vis grad:
- Den klassiske symmetriske TSP løses ved Zero Suffix Method.
- Den biogeografi-baserede optimeringsalgoritme er baseret på migrationsstrategien for at løse de optimeringsproblemer, der kan planlægges som TSP.
- Multi-Objective Evolutionary Algorithm er designet til at løse flere TSP baseret på NSGA-II.
- Multi-Agent System løser TSP for N byer med faste ressourcer.
Anvendelse af rejsende sælgerproblem
Traveling Salesman Problem (TSP) anvendes i den virkelige verden i både dens reneste og modificerede former. Nogle af dem er:
- Planlægning, logistik og fremstilling af mikrochips: Chipindsættelsesproblemer opstår naturligvis i mikrochipindustrien. Disse problemer kan planlægges som rejsende sælgerproblemer.
- DNA-sekventering: En lille ændring af problemet med rejsende sælger kan bruges i DNA-sekventering. Her repræsenterer byerne DNA-fragmenterne, og afstanden repræsenterer lighedsmålet mellem to DNA-fragmenter.
- Astronomi: The Travelling Salesman Problem anvendes af astronomer for at minimere den tid, der bruges på at observere forskellige kilder.
- Optimalt kontrolproblem: Rejsende sælger Problemformulering kan anvendes ved optimale kontrolproblemer. Der kan være tilføjet flere andre begrænsninger.
Kompleksitetsanalyse af TSP
- Tidskompleksitet: Der er i alt 2N underproblemer for hver node. Så det samlede antal underproblemer ville være N*2N. Hvert af underproblemerne kræver lineær tid at løse. Hvis oprindelsesknuden ikke er angivet, skal vi køre sløjfer for N knudepunkter.
Så den samlede tidskompleksitet for en optimal løsning ville være Antal knudepunkter * Antal underproblemer * Tid til at løse hvert underproblem. Tidskompleksiteten kan defineres som O(N2 * 2^N).
- Rumkompleksitet: Den dynamiske programmeringstilgang bruger hukommelse til at lagre C(S, i), hvor S er en delmængde af toppunkterne. Der er i alt 2N undersæt for hver node. Så rumkompleksiteten er O(2^N).
Dernæst vil du lære om Sigte af Eratosthenes-algoritmen
