Problem des Handlungsreisenden: Python, C++ Algorithmus

Was ist das Travelling-Salesman-Problem (TSP)?

Das Travelling Salesman Problem (TSP) ist ein klassisches kombinatorisches Problem der theoretischen Informatik. Das Problem besteht darin, den kürzesten Weg in einem Diagramm zu finden, mit der Bedingung, alle Knoten nur einmal zu besuchen und zur Ursprungsstadt zurückzukehren.

Die Problemstellung enthält eine Liste von Städten sowie die Entfernungen zwischen den einzelnen Städten.

Ziel: Um von der Ausgangsstadt aus zu starten, besuchen Sie andere Städte nur einmal und kehren Sie dann wieder in die Ausgangsstadt zurück. Unser Ziel ist es, den kürzestmöglichen Weg zu finden, um die Hin- und Rückfahrt zu absolvieren.

Beispiel für TSP

Hier wird ein Diagramm angezeigt, in dem 1, 2, 3 und 4 die Städte darstellen und die mit jeder Kante verbundene Gewichtung die Entfernung zwischen diesen Städten darstellt.

Das Ziel besteht darin, den kürzestmöglichen Weg für die Tour zu finden, der in der Ursprungsstadt beginnt, den Graphen durchquert, die anderen Städte oder Knotenpunkte nur einmal besucht, und zur Ursprungsstadt zurückkehrt.

Für das obige Diagramm besteht die optimale Route darin, dem Pfad mit minimalen Kosten zu folgen: 1-2-4-3-1. Und dieser kürzeste Weg würde 10+25+30+15 =80 kosten

Verschiedene Lösungen für das Problem des Handlungsreisenden

Das Problem des Handlungsreisenden (Travelling Salesman Problem, TSP) wird als NP-schweres Problem eingestuft, da es keinen Algorithmus mit polynomischer Laufzeit gibt. Die Komplexität steigt exponentiell mit der Anzahl der Städte.

Es gibt mehrere Möglichkeiten, das Problem des Handlungsreisenden (tsp) zu lösen. Einige beliebte Lösungen sind:

Der Brute-Force-Ansatz ist die naive Methode zur Lösung von Handlungsreisendenproblemen. Bei diesem Ansatz berechnen wir zunächst alle möglichen Pfade und vergleichen sie dann. Die Anzahl der Pfade in einem Diagramm bestehend aus n Städten beträgt n! Es ist sehr rechenintensiv, das Problem des Handlungsreisenden mit diesem Brute-Force-Ansatz zu lösen.

Die Branch-and-Bound-Methode: Bei diesem Ansatz wird das Problem in Teilprobleme zerlegt. Die Lösung dieser einzelnen Teilprobleme würde eine optimale Lösung liefern.

In diesem Tutorial wird ein dynamischer Programmieransatz, die rekursive Version dieser Branch-and-Bound-Methode, zur Lösung des Problems des Handlungsreisenden demonstriert.

Dynamische Programmierung ist eine solche Methode zur Suche nach optimalen Lösungen durch die Analyse aller möglichen Routen. Es ist eine der exakten Lösungsmethoden, die Probleme von Handlungsreisenden mit relativ höheren Kosten löst als die gierige Methoden die eine nahezu optimale Lösung bieten.

Die Rechenkomplexität dieses Ansatzes ist O(N^2 * 2^N) was später in diesem Artikel besprochen wird.

Die Nearest-Neighbor-Methode ist ein heuristischer Greedy-Ansatz, bei dem wir den nächsten Nachbarknoten auswählen. Dieser Ansatz ist rechnerisch weniger aufwändig als der dynamische Ansatz. Er bietet jedoch keine Garantie für eine optimale Lösung. Diese Methode wird für nahezu optimale Lösungen verwendet.

Algorithmus für das Problem des Handlungsreisenden

Wir werden den dynamischen Programmieransatz verwenden, um das Traveling Salesman Problem (TSP) zu lösen.

Bevor wir mit dem Algorithmus beginnen, machen wir uns mit einigen Terminologien vertraut:

Ein Graph G=(V, E), der eine Menge von Eckpunkten und Kanten ist.
V ist die Menge der Eckpunkte.
E ist die Menge der Kanten.
Eckpunkte werden durch Kanten verbunden.
Dist(i,j) bezeichnet den nicht negativen Abstand zwischen zwei Eckpunkten i und j.

Nehmen wir an, dass S die Teilmenge der Städte ist und zu {1, 2, 3, …, n} gehört, wobei 1, 2, 3… n die Städte und i, j zwei Städte in dieser Teilmenge sind. Jetzt werden Kosten (i, S, j) so definiert, dass sie die Länge des kürzesten Weges sind, der den Knoten in S besucht, der genau einmal den Start- und Endpunkt i bzw. j hat.

Beispielsweise bezeichnen die Kosten (1, {2, 3, 4}, 1) die Länge des kürzesten Pfades, wobei:

Startstadt ist 1
Die Städte 2, 3 und 4 werden nur einmal besucht
Der Endpunkt ist 1

Der dynamische Programmieralgorithmus wäre:

Setzen Sie cost(i, , i) = 0, was bedeutet, dass wir bei i beginnen und enden und die Kosten 0 sind.
Wenn |S| > 1, wir definieren cost(i, S, 1) = ∝ wobei i !=1 . Denn zunächst kennen wir die genauen Kosten für die Verbindung von Stadt I zu Stadt 1 über andere Städte nicht.
Jetzt müssen wir bei 1 beginnen und die Tour abschließen. Wir müssen die nächste Stadt auf diese Weise auswählen:

cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j) wobei i∈S und i≠j

Für die gegebene Abbildung wäre die Adjazenzmatrix wie folgt:

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

Sehen wir uns an, wie unser Algorithmus funktioniert:

Schritt 1) Wir überlegen, unsere Reise in Stadt 1 zu beginnen, einmal andere Städte zu besuchen und zu Stadt 1 zurückzukehren.

Schritt 2) S ist die Teilmenge der Städte. Gemäß unserem Algorithmus setzen wir für alle |S| > 1 die Distanz cost(i, S, 1) = ∝. Hier bedeutet cost(i, S, j), dass wir in Stadt i starten, die Städte von S einmal besuchen und jetzt in Stadt j sind. Wir setzen diese Pfadkosten auf unendlich, da wir die Distanz noch nicht kennen. Die Werte sind also die folgenden:

Kosten (2, {3, 4}, 1) = ∝ ; Die Notation bedeutet, dass wir bei Stadt 2 beginnen, durch die Städte 3, 4 gehen und 1 erreichen. Und die Pfadkosten sind unendlich. Ähnlich-

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

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

Schritt 3) Nun müssen wir für alle Teilmengen von S Folgendes herausfinden:

cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j), wobei j∈S und i≠j

Das bedeutet den minimalen Kostenpfad für den Start bei i, das einmalige Durchlaufen der Teilmenge der Städte und die Rückkehr zur Stadt j. Wenn man bedenkt, dass die Reise in Stadt 1 beginnt, wären die optimalen Pfadkosten = cost(1, {andere Städte}, 1).

Finden wir heraus, wie wir das erreichen können:

Nun ist S = {1, 2, 3, 4}. Es gibt vier Elemente. Daher beträgt die Anzahl der Teilmengen 2^4 oder 16. Diese Teilmengen sind:

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:

Da wir bei 1 beginnen, könnten wir die Teilmengen, die Stadt 1 enthalten, verwerfen.

Der Berechnungsalgorithmus:

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

Die optimale Lösung wäre also 1-2-4-3-1

Pseudocode

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)

Implementierung in C/C++

Hier ist die Implementierung in 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;
}

Ausgang:

Umsetzung 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))

Ausgang:

Akademische Lösungen für TSP

Informatiker haben jahrelang nach einem verbesserten Algorithmus in polynomieller Zeit für das Problem des Handlungsreisenden gesucht. Bis heute ist das Problem immer noch NP-schwer.

Allerdings wurden in den letzten Jahren einige der folgenden Lösungen veröffentlicht, die die Komplexität bis zu einem gewissen Grad reduziert haben:

Der klassische symmetrische TSP wird durch die Zero-Suffix-Methode gelöst.
Der Biogeographie-basierte Optimierungsalgorithmus basiert auf der Migrationsstrategie zur Lösung der Optimierungsprobleme, die als TSP geplant werden können.
Der Multi-Objective Evolutionary Algorithmus ist für die Lösung mehrerer TSP basierend auf NSGA-II konzipiert.
Das Multi-Agent-System löst den TSP von N Städten mit festen Ressourcen.

Anwendung des Problems des Handlungsreisenden

Das Travelling-Salesman-Problem (TSP) wird in der realen Welt sowohl in seiner reinsten als auch in modifizierter Form angewendet. Einige davon sind:

Planung, Logistik und Herstellung von Mikrochips: In der Mikrochipindustrie treten natürlich Probleme beim Einsetzen von Chips auf. Diese Probleme können als Probleme des Handlungsreisenden geplant werden.
DNA-Sequenzierung: Eine geringfügige Modifikation des Problems des Handlungsreisenden kann bei der DNA-Sequenzierung verwendet werden. Hier stellen die Städte die DNA-Fragmente dar und die Entfernung stellt das Ähnlichkeitsmaß zwischen zwei DNA-Fragmenten dar.
Astronomie: Das Problem des Handlungsreisenden wird von Astronomen angewendet, um den Zeitaufwand für die Beobachtung verschiedener Quellen zu minimieren.
Optimales Kontrollproblem: Handlungsreisender Problemformulierung kann bei Optimalkontrollproblemen angewendet werden. Möglicherweise kommen noch weitere Einschränkungen hinzu.

Komplexitätsanalyse von TSP

Zeitliche Komplexität: Es gibt insgesamt 2^NTeilprobleme für jeden Knoten. Die Gesamtzahl der Teilprobleme wäre also N*2^N. Jedes der Teilprobleme erfordert lineare Zeit zur Lösung. Wenn der Ursprungsknoten nicht angegeben ist, müssen wir Schleifen für N Knoten ausführen.
Die gesamte zeitliche Komplexität für eine optimale Lösung wäre also die Anzahl der Knoten * Anzahl der Teilprobleme * Zeit zum Lösen jedes Teilproblems. Die zeitliche Komplexität kann definiert werden als O(N² * 2^N).
Raumkomplexität: Der dynamische Programmieransatz verwendet Speicher zum Speichern von C(S, i), wobei S eine Teilmenge der Scheitelpunktmenge ist. Es gibt insgesamt 2^NTeilmengen für jeden Knoten. Die Speicherkomplexität beträgt also O(2^N).

Als nächstes erfahren Sie mehr darüber Sieb des Eratosthenes-Algorithmus