Problem med resande säljare: Python, C++ Algoritm

By: Sarah Chen Sarah Chen
Hours Uppdaterad

Vad är problemet med resande säljare (TSP)?

Traveling Salesman Problem (TSP) är ett klassiskt kombinatoriskt problem inom teoretisk datavetenskap. Problemet kräver att hitta den kortaste vägen i en graf med villkoret att besöka alla noder bara en gång och återvända till ursprungsstaden.

Problemformuleringen ger en lista över städer tillsammans med avstånden mellan varje stad.

Mål: För att börja från ursprungsstaden, besök andra städer endast en gång och återvänd till den ursprungliga staden igen. Vårt mål är att hitta den kortaste möjliga vägen för att slutföra rundresan.

Exempel på TSP

Här ges en graf där 1, 2, 3 och 4 representerar städerna, och vikten associerad med varje kant representerar avståndet mellan dessa städer.

Exempel på TSP

Målet är att hitta den kortaste möjliga vägen för turen som startar från ursprungsstaden, korsar grafen medan du bara besöker de andra städerna eller noderna en gång, och återvänder till ursprungsstaden.

För diagrammet ovan är den optimala vägen att följa minimikostnadsvägen: 1-2-4-3-1. Och denna kortaste väg skulle kosta 10+25+30+15 =80

Olika lösningar på problem med resande säljare

Olika lösningar på problem med resande säljare

Traveling Salesman Problem (TSP) klassificeras som ett NP-hårt problem på grund av att det inte finns någon polynomisk tidsalgoritm. Komplexiteten ökar exponentiellt genom att antalet städer ökar.

Det finns flera sätt att lösa problemet med resande säljare (tsp). Några populära lösningar är:

Den brute force-metoden är den naiva metoden för att lösa problem med resande säljare. I detta tillvägagångssätt beräknar vi först alla möjliga vägar och jämför dem sedan. Antalet vägar i en graf som består av n städer är n! Det är beräkningsmässigt mycket dyrt att lösa problemet med resande säljare i denna brute force-strategi.

Gren-och-bunden-metoden: Problemet är uppdelat i delproblem i detta tillvägagångssätt. Lösningen av dessa individuella delproblem skulle ge en optimal lösning.

Denna handledning kommer att demonstrera ett dynamiskt programmeringssätt, den rekursiva versionen av denna gren-och-bundna-metod, för att lösa problemet med resande säljare.

Dynamisk programmering är en sådan metod för att söka optimala lösningar genom att analysera alla möjliga vägar. Det är en av de exakta lösningsmetoderna som löser problem med resande säljare genom relativt högre kostnader än giriga metoder som ger en nästan optimal lösning.

Beräkningskomplexiteten i detta tillvägagångssätt är O(N^2 * 2^N) som diskuteras senare i denna artikel.

Den närmaste granne metoden är ett heuristiskt baserat girigt tillvägagångssätt där vi väljer närmaste grannod. Detta tillvägagångssätt är beräkningsmässigt billigare än det dynamiska tillvägagångssättet. Men det ger ingen garanti för en optimal lösning. Denna metod används för nästan optimala lösningar.

Algoritm för resande säljareproblem

Vi kommer att använda den dynamiska programmeringsmetoden för att lösa Traveling Salesman Problem (TSP).

Innan vi startar algoritmen, låt oss bekanta oss med några terminologier:

  • En graf G=(V, E), som är en uppsättning av hörn och kanter.
  • V är uppsättningen av hörn.
  • E är uppsättningen av kanter.
  • Vertices är förbundna genom kanter.
  • Dist(i,j) anger det icke-negativa avståndet mellan två hörn, i och j.

Låt oss anta att S är delmängden av städer och tillhör {1, 2, 3, …, n} där 1, 2, 3...n är städerna och i, j är två städer i den delmängden. Nu definieras kostnad(i, S, j) på ett sådant sätt som längden på den kortaste vägbesöksnoden i S, som exakt en gång har start- och slutpunkten som i respektive j.

Till exempel, kostnad (1, {2, 3, 4}, 1) anger längden på den kortaste vägen där:

  • Startstad är 1
  • Städerna 2, 3 och 4 besöks endast en gång
  • Slutpunkten är 1

Den dynamiska programmeringsalgoritmen skulle vara:

  • Ange kostnad(i, , i) = 0, vilket betyder att vi börjar och slutar på i, och kostnaden är 0.
  • När |S| > 1, definierar vi kostnad(i, S, 1) = ∝ där i !=1 . För till en början vet vi inte den exakta kostnaden för att nå stad i till stad 1 genom andra städer.
  • Nu måste vi börja vid 1 och slutföra turnén. Vi måste välja nästa stad på ett sådant sätt-

kostnad(i, S, j)=min kostnad (i, S−{i}, j)+avstånd(i,j) där i∈S och i≠j

För den givna figuren skulle närliggande matris vara följande:

Algoritm för resande säljareproblem

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

Låt oss se hur vår algoritm fungerar:

Steg 1) Vi överväger att vår resa börjar vid stad 1, besöker andra städer en gång och återvänder till stad 1.

Steg 2) S är delmängden av städer. Enligt vår algoritm, för alla |S| > 1, ställer vi in ​​avståndskostnaden(i, S, 1) = ∝. Här betyder kostnad(i, S, j) att vi börjar vid stad i, besöker städerna S en gång, och nu är vi vid stad j. Vi sätter denna vägkostnad som oändlig eftersom vi inte vet avståndet ännu. Så värdena blir följande:

Kostnad (2, {3, 4}, 1) = ∝ ; notationen anger att vi börjar vid stad 2, går genom städer 3, 4 och når 1. Och vägkostnaden är oändlig. Liknande-

kostnad(3, {2, 4}, 1) = ∝

kostnad(4, {2, 3}, 1) = ∝

Steg 3) Nu, för alla delmängder av S, måste vi hitta följande:

kostnad(i, S, j)=min kostnad (i, S−{i}, j)+avstånd(i,j), där j∈S och i≠j

Det betyder den lägsta kostnadsvägen för att börja vid i, gå igenom delmängden av städer en gång och återvända till stad j. Med tanke på att resan börjar vid stad 1, skulle den optimala vägkostnaden vara = kostnad(1, {andra städer}, 1).

RELATERADE ARTIKLAR

Låt oss ta reda på hur vi kan uppnå det:

Nu är S = {1, 2, 3, 4}. Det finns fyra element. Följaktligen kommer antalet delmängder att vara 2^4 eller 16. Dessa delmängder är-

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}}

Eftersom vi börjar med 1 kan vi kassera delmängderna som innehåller stad 1.

Algoritmberäkningen:

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 optimala lösningen skulle vara 1-2-4-3-1

Algoritm för resande säljareproblem

Pseudokod

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++

Här är 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;
}

Produktion: 

80

Genomförande 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))

Produktion: 

80

Akademiska lösningar till TSP

Datavetare har ägnat år åt att leta efter en förbättrad polynomtidsalgoritm för resandeförsäljarproblemet. Fram till nu är problemet fortfarande NP-svårt.

Även om några av följande lösningar har publicerats under de senaste åren som har minskat komplexiteten till en viss grad:

  • Den klassiska symmetriska TSP löses med Zero Suffix Method.
  • Den biogeografibaserade optimeringsalgoritmen är baserad på migreringsstrategin för att lösa de optimeringsproblem som kan planeras som TSP.
  • Multi-Objective Evolutionary Algorithm är designad för att lösa flera TSP baserat på NSGA-II.
  • Multi-Agent System löser TSP för N städer med fasta resurser.

Tillämpning av resande säljareproblem

Traveling Salesman Problem (TSP) tillämpas i den verkliga världen i både sin renaste och modifierade form. Några av dessa är:

  • Planering, logistik och tillverkning av mikrochips: Problem med att införa chip uppstår naturligt i mikrochipsindustrin. Dessa problem kan planeras som resande säljarproblem.
  • DNA-sekvensering: En liten modifiering av resandeförsäljarproblemet kan användas vid DNA-sekvensering. Här representerar städerna DNA-fragmenten, och avståndet representerar likhetsmåttet mellan två DNA-fragment.
  • Astronomi: Problemet med resande försäljare tillämpas av astronomer för att minimera tiden för att observera olika källor.
  • Optimalt kontrollproblem: Resande säljare Problemformulering kan användas vid optimala kontrollproblem. Det kan läggas till flera andra begränsningar.

Komplexitetsanalys av TSP

  • Tidskomplexitet: Det finns totalt 2N delproblem för varje nod. Så det totala antalet delproblem skulle vara N*2N. Vart och ett av delproblemen kräver linjär tid att lösa. Om ursprungsnoden inte är specificerad måste vi köra loopar för N noder.

    Så den totala tidskomplexiteten för en optimal lösning skulle vara Antal noder * Antal delproblem * tid att lösa varje delproblem. Tidskomplexiteten kan definieras som O(N2 * 2^N).

  • Rymdkomplexitet: Den dynamiska programmeringsmetoden använder minne för att lagra C(S, i), där S är en delmängd av hörnuppsättningen. Det finns totalt 2N delmängder för varje nod. Så rymdkomplexiteten är O(2^N).

Därefter kommer du att lära dig om Sieve of Eratosthenes Algorithm

Du kanske gillar: