Reisende selgerproblem: Python, C++ Algoritme
Hva er Traveling Salesman Problem (TSP)?
Traveling Salesman Problem (TSP) er et klassisk kombinatorisk problem innen teoretisk informatikk. Problemet ber om å finne den korteste veien i en graf med betingelsen om å besøke alle nodene bare én gang og returnere til opprinnelsesbyen.
Problemstillingen gir en liste over byer sammen med avstandene mellom hver by.
Målet: For å starte fra opprinnelsesbyen, besøk andre byer bare én gang, og gå tilbake til den opprinnelige byen igjen. Målet vårt er å finne kortest mulig vei for å fullføre tur-retur-ruten.
Eksempel på TSP
Her er det gitt en graf der 1, 2, 3 og 4 representerer byene, og vekten knyttet til hver kant representerer avstanden mellom disse byene.
Målet er å finne kortest mulig vei for turen som starter fra opprinnelsesbyen, krysser grafen mens du bare besøker de andre byene eller nodene én gang, og går tilbake til opprinnelsesbyen.
For grafen ovenfor er den optimale ruten å følge minimumskostnadsbanen: 1-2-4-3-1. Og denne korteste ruten vil koste 10+25+30+15 =80
Forskjellige løsninger på reisende selgerproblem
Traveling Salesman Problem (TSP) er klassifisert som et NP-hardt problem på grunn av at det ikke har noen polynomisk tidsalgoritme. Kompleksiteten øker eksponentielt ved å øke antall byer.
Det er flere måter å løse problemet med reisende selger (ts). Noen populære løsninger er:
Den brute force-tilnærmingen er den naive metoden for å løse reisende selgerproblemer. I denne tilnærmingen beregner vi først alle mulige veier og sammenligner dem deretter. Antall stier i en graf som består av n byer er n! Det er beregningsmessig veldig dyrt å løse det reisende selgerproblemet i denne brute force-tilnærmingen.
Gren-og-bundet metoden: Problemet er brutt ned i delproblemer i denne tilnærmingen. Løsningen av de individuelle delproblemene vil gi en optimal løsning.
Denne opplæringen vil demonstrere en dynamisk programmeringstilnærming, den rekursive versjonen av denne branch-and-bound-metoden, for å løse det reisende selgerproblemet.
Dynamisk programmering er en slik metode for å søke optimale løsninger ved å analysere alle mulige ruter. Det er en av de eksakte løsningsmetodene som løser reisende selgerproblemer gjennom relativt høyere kostnader enn grådige metoder som gir en nesten optimal løsning.
Beregningskompleksiteten til denne tilnærmingen er O(N^2 * 2^N) som diskuteres senere i denne artikkelen.
Den nærmeste nabometoden er en heuristisk-basert grådig tilnærming der vi velger nærmeste nabonode. Denne tilnærmingen er beregningsmessig rimeligere enn den dynamiske tilnærmingen. Men det gir ingen garanti for en optimal løsning. Denne metoden brukes til nærmest optimale løsninger.
Algoritme for reisende selgerproblem
Vi vil bruke den dynamiske programmeringsmetoden for å løse Traveling Salesman Problem (TSP).
Før du starter algoritmen, la oss bli kjent med noen terminologier:
- En graf G=(V, E), som er et sett med hjørner og kanter.
- V er settet med toppunkter.
- E er settet med kanter.
- Topppunkter er forbundet gjennom kanter.
- Dist(i,j) angir den ikke-negative avstanden mellom to toppunkter, i og j.
La oss anta at S er delmengden av byer og tilhører {1, 2, 3, …, n} der 1, 2, 3…n er byene og i, j er to byer i den delmengden. Nå er kostnad(i, S, j) definert på en slik måte som lengden på den korteste veibesøksnoden i S, som nøyaktig én gang har start- og sluttpunktet som i og j.
For eksempel angir kostnad (1, {2, 3, 4}, 1) lengden på den korteste banen der:
- Startby er 1
- Byene 2, 3 og 4 besøkes bare én gang
- Sluttpunktet er 1
Den dynamiske programmeringsalgoritmen vil være:
- Sett kostnad(i, , i) = 0, som betyr at vi starter og slutter på i, og kostnaden er 0.
- Når |S| > 1, definerer vi kostnad(i, S, 1) = ∝ hvor i !=1 . For i utgangspunktet vet vi ikke den nøyaktige kostnaden for å nå by i til by 1 gjennom andre byer.
- Nå må vi starte klokken 1 og fullføre turen. Vi må velge neste by på en slik måte-
kostnad(i, S, j)=min kostnad (i, S−{i}, j)+avstand(i,j) hvor i∈S og i≠j
For den gitte figuren vil tilstøtningsmatrisen 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 |
La oss se hvordan algoritmen vår fungerer:
Trinn 1) Vi vurderer vår reise som starter ved by 1, besøker andre byer én gang og går tilbake til by 1.
Trinn 2) S er delmengden av byer. I henhold til vår algoritme, for alle |S| > 1, vil vi sette avstandskostnaden(i, S, 1) = ∝. Her betyr cost(i, S, j) at vi starter ved by i, besøker byene S en gang, og nå er vi ved by j. Vi setter denne veikostnaden som uendelig fordi vi ikke vet avstanden ennå. Så verdiene vil være følgende:
Kostnad (2, {3, 4}, 1) = ∝ ; notasjonen angir at vi starter ved by 2, går gjennom byer 3, 4 og når 1. Og veikostnaden er uendelig. På samme måte-
cost(3, {2, 4}, 1) = ∝
cost(4, {2, 3}, 1) = ∝
Trinn 3) Nå, for alle delmengder av S, må vi finne følgende:
kostnad(i, S, j)=min kostnad (i, S−{i}, j)+avstand(i,j), hvor j∈S og i≠j
Det betyr minimumskostnadsbanen for å starte ved i, gå gjennom delsettet av byer én gang og gå tilbake til by j. Tatt i betraktning at reisen starter ved by 1, vil den optimale rutekostnaden være = kostnad(1, {andre byer}, 1).
La oss finne ut hvordan vi kan oppnå det:
Nå er S = {1, 2, 3, 4}. Det er fire elementer. Derfor vil antallet undersett være 2^4 eller 16. Disse undersettene er-
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}}
Ettersom vi starter på 1, kan vi forkaste delsettene som inneholder by 1.
Algoritmeberegningen:
1) |S| = Φ:
kostnad (2, Φ, 1) = dist(2, 1) = 10
kostnad (3, Φ, 1) = dist(3, 1) = 15
kostnad (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
kostnad (2, {3}, 1) = dist(2, 3) + kostnad (3, Φ, 1) = 35+15 = 50
kostnad (2, {4}, 1) = dist(2, 4) + kostnad (4, Φ, 1) = 25+20 = 45
kostnad (3, {2}, 1) = dist(3, 2) + kostnad (2, Φ, 1) = 35+10 = 45
kostnad (3, {4}, 1) = dist(3, 4) + kostnad (4, Φ, 1) = 30+20 = 50
kostnad (4, {2}, 1) = dist(4, 2) + kostnad (2, Φ, 1) = 25+10 = 35
kostnad (4, {3}, 1) = dist(4, 3) + kostnad (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
kostnad (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
kostnad (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
kostnad (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:
kostnad (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øsningen vil være 1-2-4-3-1
Pseudokode
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; }
Utgang:
80
Gjennomføring 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))
Utgang:
80
Akademiske løsninger til TSP
Dataforskere har brukt år på å søke etter en forbedret polynomisk tidsalgoritme for Traveling Salesman Problem. Til nå er problemet fortsatt NP-hardt.
Selv om noen av følgende løsninger ble publisert de siste årene som har redusert kompleksiteten til en viss grad:
- Den klassiske symmetriske TSP løses med Zero Suffix Method.
- Den biogeografibaserte optimaliseringsalgoritmen er basert på migrasjonsstrategien for å løse optimaliseringsproblemene som kan planlegges som TSP.
- Multi-Objective Evolutionary Algorithm er designet for å løse flere TSP basert på NSGA-II.
- Multi-Agent System løser TSP for N byer med faste ressurser.
Anvendelse av Traveling Salesman Problem
Traveling Salesman Problem (TSP) brukes i den virkelige verden i både sine reneste og modifiserte former. Noen av disse er:
- Planlegging, logistikk og produksjon av mikrobrikker: Brikkeinnsettingsproblemer oppstår naturlig i mikrobrikkeindustrien. Disse problemene kan planlegges som omreisende selgerproblemer.
- DNA-sekvense: Liten modifikasjon av problemet med reisende selger kan brukes i DNA-sekvensering. Her representerer byene DNA-fragmentene, og avstanden representerer likhetsmålet mellom to DNA-fragmenter.
- Astronomi: The Travelling Salesman Problem brukes av astronomer for å minimere tiden brukt på å observere ulike kilder.
- Optimalt kontrollproblem: Omreisende selger Problemformulering kan brukes ved optimale kontrollproblemer. Det kan være flere andre begrensninger lagt til.
Kompleksitetsanalyse av TSP
- Tidskompleksitet: Det er totalt 2N underproblemer for hver node. Så det totale antallet delproblemer vil være N*2N. Hvert av delproblemene krever lineær tid å løse. Hvis opprinnelsesnoden ikke er spesifisert, må vi kjøre løkker for N noder.
Så den totale tidskompleksiteten for en optimal løsning vil være antall noder * Antall delproblemer * tid for å løse hvert delproblem. Tidskompleksiteten kan defineres som O(N2 * 2^N).
- Romkompleksitet: Den dynamiske programmeringstilnærmingen bruker minne til å lagre C(S, i), der S er en delmengde av toppunktsettet. Det er totalt 2N delsett for hver node. Så romkompleksiteten er O(2^N).
Deretter vil du lære om Sil av Eratosthenes-algoritmen