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.

Doel: 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.

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

Travelling Salesman Problem (TSP) is geclassificeerd als een NP-hard probleem omdat er geen polynomiaal tijdalgoritme is. De complexiteit neemt exponentieel toe naarmate het aantal steden toeneemt.

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 rekenkundige complexiteit van deze aanpak is O(N^2 * 2^N) Dit wordt later in dit artikel besproken.

De dichtstbijzijnde buurmethode is een heuristische, hebzuchtige benadering waarbij we de dichtstbijzijnde buurnode kiezen. Deze benadering is rekenkundig minder duur 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 er als volgt uitzien:

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 afstand cost(i, S, 1) = ∝ in. Hier betekent cost(i, S, j) dat we beginnen bij stad i, de steden van S eenmaal bezoeken en nu zijn we bij stad j. We stellen deze padkosten in op oneindig omdat we de afstand nog niet weten. Dus de waarden zullen als volgt zijn:

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) Voor alle deelverzamelingen van S moeten we nu het volgende vinden:

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:

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

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:

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:

Academische oplossingen voor TSP

Computerwetenschappers hebben jarenlang gezocht naar een verbeterd polynomiaal tijdalgoritme voor het Travelling Salesman Problem. Tot nu toe is het probleem nog steeds NP-moeilijk.

De afgelopen jaren zijn er enkele van de volgende oplossingen gepubliceerd die de complexiteit enigszins hebben verminderd:

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 handelsreizigersprobleem wordt door astronomen gebruikt om de tijd die ze besteden 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

Tijdscomplexiteit: Er zijn er in totaal 2^Nsubproblemen voor elk knooppunt. Het totale aantal subproblemen zou dus N*2 zijn^N. 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 tijdcomplexiteit voor een optimale oplossing zou zijn: Aantal knooppunten * Aantal subproblemen * tijd om elk subprobleem op te lossen. De tijdcomplexiteit kan worden gedefinieerd als O(N² * 2^N).
Ruimtecomplexiteit: 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 2^Nsubsets voor elk knooppunt. Dus de ruimtecomplexiteit is O(2^N).

Vervolgens leer je meer over Zeef van Eratosthenes-algoritme

Je houdt misschien van: