Handelsreiziger Probleem: Python, C++-algoritme

Wat is het Travelling Salesman Problem (TSP)?

Travelling Salesman Problem (TSP) is een klassiek combinatorisch probleem uit de theoretische informatica. Het probleem vraagt ​​om het kortste pad in een grafiek te vinden met als voorwaarde dat je alle knooppunten slechts één keer bezoekt en terugkeert naar de oorspronkelijke stad.

De probleemstelling geeft een lijst met steden en de afstanden tussen elke stad.

Doelstelling: Om vanuit de oorspronkelijke stad te beginnen, bezoekt u slechts één keer andere steden en keert u vervolgens weer terug naar de oorspronkelijke stad. Ons doel is om het kortst mogelijke pad te vinden om de heen- en terugreis te voltooien.

Voorbeeld van TSP

Hier wordt een grafiek gegeven waarin 1, 2, 3 en 4 de steden vertegenwoordigen, en het gewicht dat bij elke rand hoort, vertegenwoordigt de afstand tussen die steden.

Voorbeeld van TSP

Het doel is om het kortst mogelijke pad te vinden voor de tour die begint bij de stad van herkomst, de grafiek doorkruist terwijl je slechts één keer de andere steden of knooppunten bezoekt, en terugkeert naar de stad van herkomst.

Voor de bovenstaande grafiek is de optimale route het volgen van het minimale kostenpad: 1-2-4-3-1. En deze kortste route zou 10+25+30+15 =80 kosten

Verschillende oplossingen voor het handelsreizigersprobleem

Verschillende oplossingen voor het handelsreizigersprobleem

Travelling Salesman Problem (TSP) is geclassificeerd als een NP-moeilijk probleem omdat er geen polynoom tijdalgoritme is. De complexDe stad neemt exponentieel toe door het aantal steden te vergroten.

Er zijn meerdere manieren om het handelsreizigersprobleem (tsp) op te lossen. Enkele populaire oplossingen zijn:

De brute force-aanpak is de naïeve methode voor het oplossen van handelsreizigersproblemen. Bij deze aanpak berekenen we eerst alle mogelijke paden en vergelijken ze vervolgens. Het aantal paden in een grafiek bestaande uit n steden is n! Het is computationeel erg duur om het handelsreizigersprobleem op te lossen met deze brute force-benadering.

De branch-and-bound-methode: Bij deze aanpak wordt het probleem opgesplitst in deelproblemen. De oplossing van die individuele deelproblemen zou een optimale oplossing opleveren.

Deze tutorial demonstreert een dynamische programmeeraanpak, de recursieve versie van deze branch-and-bound-methode, om het handelsreizigersprobleem op te lossen.

Dynamisch programmeren is zo'n methode om optimale oplossingen te zoeken door alle mogelijke routes te analyseren. Het is een van de exacte oplossingsmethoden die problemen van handelsreizigers oplost tegen relatief hogere kosten dan de hebzuchtige methoden die een vrijwel optimale oplossing bieden.

De computationele complexDe kracht van deze aanpak is O(N^2 * 2^N) waarover wordt gesproken later in dit artikel.

De nearest buurmethode is een op heuristiek gebaseerde hebzuchtige benadering waarbij we voor het ne kiezenarest buurknooppunt. Deze benadering is computationeel goedkoper dan de dynamische benadering. Maar het biedt geen garantie voor een optimale oplossing. Deze methode wordt gebruikt voor bijna optimale oplossingen.

Algoritme voor het handelsreizigersprobleem

We zullen de dynamische programmeerbenadering gebruiken om het Traveling Salesman Problem (TSP) op te lossen.

Laten we, voordat we met het algoritme beginnen, kennis maken met enkele terminologieën:

  • Een grafiek G=(V, E), die een reeks hoekpunten en randen is.
  • V is de verzameling hoekpunten.
  • E is de verzameling randen.
  • Hoekpunten zijn verbonden via randen.
  • Dist(i,j) geeft de niet-negatieve afstand aan tussen twee hoekpunten, i en j.

Laten we aannemen dat S de deelverzameling van steden is en behoort tot {1, 2, 3, …, n} waarbij 1, 2, 3…n de steden zijn en i, j twee steden in die deelverzameling zijn. Nu wordt cost(i, S, j) op zo'n manier gedefinieerd als de lengte van het kortste pad dat een knooppunt in S bezoekt, dat precies één keer het begin- en eindpunt heeft als respectievelijk i en j.

Kosten (1, {2, 3, 4}, 1) geven bijvoorbeeld de lengte van het kortste pad aan, waarbij:

  • Startstad is 1
  • Steden 2, 3 en 4 worden slechts één keer bezocht
  • Het eindpunt is 1

Het dynamische programmeeralgoritme zou zijn:

  • Stel cost(i, , i) = 0 in, wat betekent dat we beginnen en eindigen bij i, en dat de kosten 0 zijn.
  • Wanneer |S| > 1, definiëren we kosten(i, S, 1) = ∝ waarbij i !=1 . Omdat we in eerste instantie niet de exacte kosten kennen om stad i naar stad 1 te bereiken via andere steden.
  • Nu moeten we bij 1 beginnen en de tour voltooien. We moeten de volgende stad op zo'n manier selecteren:

kosten(i, S, j)=min kosten (i, S−{i}, j)+dist(i,j) waarbij i∈S en i≠j

Voor de gegeven figuur zou de aangrenzende matrix de volgende zijnwing:

Algoritme voor het handelsreizigersprobleem

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

Laten we eens kijken hoe ons algoritme werkt:

Stap 1) We overwegen onze reis te starten in stad 1, een keer andere steden te bezoeken en terug te keren naar stad 1.

Stap 2) S is de subset van steden. Volgens ons algoritme, voor alle |S| > 1, stellen we de afstandskosten (i, S, 1) = ∝ in. Kosten(i, S, j) betekent hier dat we beginnen bij stad i, één keer de steden S bezoeken, en nu zijn we bij stad j. We stellen deze padkosten in op oneindig omdat we de afstand nog niet kennen. Dus de waarden zijn de volgendewing:

Kosten (2, {3, 4}, 1) = ∝ ; de notatie geeft aan dat we beginnen bij stad 2, door steden 3, 4 gaan en 1 bereiken. En de padkosten zijn oneindig. Op dezelfde manier-

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

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

Stap 3) Nu moeten we voor alle deelverzamelingen van S het volgende vindenwing:

kosten(i, S, j)=min kosten (i, S−{i}, j)+dist(i,j), waarbij j∈S en i≠j

Dat betekent het minimale kostenpad om bij i te beginnen, één keer door de subset van steden te gaan en terug te keren naar stad j. Gezien het feit dat de reis begint bij stad 1, zouden de optimale padkosten = kosten(1, {andere steden}, 1).

Laten we eens kijken hoe we dat kunnen bereiken:

Nu S = {1, 2, 3, 4}. Er zijn vier elementen. Het aantal subsets is dus 2^4 of 16. Die subsets zijn-

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

Omdat we bij 1 beginnen, kunnen we de subsets met stad 1 weggooien.

De algoritmeberekening:

1) |S| = Φ:

kosten (2, Φ, 1) = dist(2, 1) = 10

kosten (3, Φ, 1) = dist(3, 1) = 15

kosten (4, Φ, 1) = dist(4, 1) = 20

2) |S| = 1:

kosten (2, {3}, 1) = dist(2, 3) + kosten (3, Φ, 1) = 35+15 = 50

kosten (2, {4}, 1) = dist(2, 4) + kosten (4, Φ, 1) = 25+20 = 45

kosten (3, {2}, 1) = dist(3, 2) + kosten (2, Φ, 1) = 35+10 = 45

kosten (3, {4}, 1) = dist(3, 4) + kosten (4, Φ, 1) = 30+20 = 50

kosten (4, {2}, 1) = dist(4, 2) + kosten (2, Φ, 1) = 25+10 = 35

kosten (4, {3}, 1) = dist(4, 3) + kosten (3, Φ, 1) = 30+15 = 45

3) |S| = 2:

kosten (2, {3, 4}, 1) = min [ dist[2,3]+Kosten(3,{4},1) = 35+50 = 85,

dist[2,4]+Kosten(4,{3},1) = 25+45 = 70 ] = 70

kosten (3, {2, 4}, 1) = min [ dist[3,2]+Kosten(2,{4},1) = 35+45 = 80,

dist[3,4]+Kosten(4,{2},1) = 30+35 = 65 ] = 65

kosten (4, {2, 3}, 1) = min [ dist[4,2]+Kosten(2,{3},1) = 25+50 = 75

dist[4,3]+Kosten(3,{2},1) = 30+45 = 75 ] = 75

4) |S| = 3:

kosten (1, {2, 3, 4}, 1) = min [ dist[1,2]+Kosten(2,{3,4},1) = 10+70 = 80

dist[1,3]+Kosten(3,{2,4},1) = 15+65 = 80

dist[1,4]+Kosten(4,{2,3},1) = 20+75 = 95 ] = 80

De optimale oplossing zou dus zijn 1-2-4-3-1

Algoritme voor het handelsreizigersprobleem

Pseudo-code

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) 

Implementatie in C/C++

Hier is de implementatie binnen 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

Implementatie in 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

Academische oplossingen voor TSP

Computerwetenschappers hebben er jaren over gedaanarching voor een verbeterd polynomiaal tijdalgoritme voor het handelsreizigersprobleem. Tot nu toe is het probleem nog steeds NP-hard.

Hoewel een deel van de following Er zijn de afgelopen jaren oplossingen gepubliceerd die de complextot op zekere hoogte:

  • De klassieke symmetrische TSP wordt opgelost door de Zero Suffix-methode.
  • Het op biogeografie gebaseerde optimalisatie-algoritme is gebaseerd op de migratiestrategie om de optimalisatieproblemen op te lossen die als TSP kunnen worden gepland.
  • Multi-Objective Evolutionary Algorithm is ontworpen voor het oplossen van meerdere TSP's op basis van NSGA-II.
  • Het Multi-Agent Systeem lost de TSP van N steden op met vaste middelen.

Toepassing van het handelsreizigersprobleem

Travelling Salesman Problem (TSP) wordt in de echte wereld zowel in de puurste als in de gewijzigde vorm toegepast. Sommige daarvan zijn:

  • Planning, logistiek en productie van microchips: Problemen met het inbrengen van chips komen van nature voor in de microchipindustrie. Deze problemen kunnen worden gepland als handelsreizigersproblemen.
  • DNA sequencing: Een kleine wijziging van het handelsreizigersprobleem kan worden gebruikt bij DNA-sequencing. Hier vertegenwoordigen de steden de DNA-fragmenten en vertegenwoordigt de afstand de mate van gelijkenis tussen twee DNA-fragmenten.
  • Astronomie: Het Traveling Salesman Problem wordt door astronomen toegepast om de tijd die besteed wordt aan het observeren van verschillende bronnen te minimaliseren.
  • Optimaal controleprobleem: Handelsreiziger Probleemformulering kan worden toegepast bij optimale controleproblemen. Er kunnen nog een aantal andere beperkingen worden toegevoegd.

complexiteitsanalyse van TSP

  • Tijd Complexiteit: Er zijn er in totaal 2N subproblemen voor elk knooppunt. Het totale aantal subproblemen zou dus N*2 zijnN. Elk van de deelproblemen vereist lineaire tijd om op te lossen. Als het oorsprongsknooppunt niet is opgegeven, moeten we lussen uitvoeren voor N knooppunten.

    Dus de totale tijd complexDe waarde voor een optimale oplossing zou het aantal knooppunten * aantal subproblemen * de tijd zijn om elk subprobleem op te lossen. De tijd complexiteit kan worden gedefinieerd als O(N2 * 2^N).

  • Ruimte Complexiteit: De dynamische programmeerbenadering maakt gebruik van geheugen om C(S, i) op ​​te slaan, waarbij S een subset is van de set hoekpunten. Er zijn er in totaal 2N subsets voor elk knooppunt. Dus de ruimte complexiteit is O(2^N).

Vervolgens leer je meer over Zeef van Eratosthenes-algoritme