algorithm
Reisender Verkäufer
Suche…
Bemerkungen
Das Problem des reisenden Verkäufers besteht darin, die minimalen Kosten für das Durchlaufen von N Knoten genau einmal pro Knoten zu ermitteln. Die Reise von Scheitelpunkt i zum Scheitelpunkt j kostet cost[i][j] .
Es gibt zwei Arten von Algorithmen, um dieses Problem zu lösen: Exakte Algorithmen und Approximationsalgorithmen
Genaue Algorithmen
- Brute-Force-Algorithmus
- Dynamischer Programmieralgorithmus
Approximationsalgorithmen
Hinzugefügt werden
Brute-Force-Algorithmus
Ein Pfad durch jeden Knoten genau einmal ist gleichbedeutend mit der Anordnung des Scheitelpunkts. Um die minimalen Kosten für das einmalige Durchlaufen jedes Scheitelpunkts genau zu berechnen, können wir also jeden einzelnen der N! Permutationen der Zahlen von 1 bis N
Psuedocode
minimum = INF
for all permutations P
current = 0
for i from 0 to N-2
current = current + cost[P[i]][P[i+1]] <- Add the cost of going from 1 vertex to the next
current = current + cost[P[N-1]][P[0]] <- Add the cost of going from last vertex to the first
if current < minimum <- Update minimum if necessary
minimum = current
output minimum
Zeitkomplexität
Es gibt N! Permutationen zum Durchlaufen und die Kosten für jeden Pfad werden in O(N) berechnet. Daher benötigt dieser Algorithmus O(N * N!) Zeit, um die genaue Antwort auszugeben.
Dynamischer Programmieralgorithmus
Beachten Sie, dass, wenn wir den Pfad berücksichtigen (in Reihenfolge):
(1,2,3,4,6,0,5,7)
und der Weg
(1,2,3,5,0,6,7,4)
Die Kosten für den Übergang vom Scheitelpunkt 1 zum Scheitelpunkt 2 zum Scheitelpunkt 3 bleiben gleich. Warum muss er neu berechnet werden? Dieses Ergebnis kann zur späteren Verwendung gespeichert werden.
Sei dp[bitmask][vertex] die minimalen Kosten für das Durchlaufen aller Scheitelpunkte, deren entsprechendes Bit in der bitmask auf 1 und am vertex endet. Zum Beispiel:
dp[12][2]
12 = 1 1 0 0
^ ^
vertices: 3 2 1 0
Da 12 1100 binär darstellt, repräsentiert dp[12][2] das Durchlaufen der Scheitelpunkte 2 und 3 im Graphen, wobei der Pfad am Scheitelpunkt 2 endet.
Daher können wir den folgenden Algorithmus verwenden (C ++ - Implementierung):
int cost[N][N]; //Adjust the value of N if needed
int memo[1 << N][N]; //Set everything here to -1
int TSP(int bitmask, int pos){
int cost = INF;
if (bitmask == ((1 << N) - 1)){ //All vertices have been explored
return cost[pos][0]; //Cost to go back
}
if (memo[bitmask][pos] != -1){ //If this has already been computed
return memo[bitmask][pos]; //Just return the value, no need to recompute
}
for (int i = 0; i < N; ++i){ //For every vertex
if ((bitmask & (1 << i)) == 0){ //If the vertex has not been visited
cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]); //Visit the vertex
}
}
memo[bitmask][pos] = cost; //Save the result
return cost;
}
//Call TSP(1,0)
Diese Zeile kann etwas verwirrend sein, lassen Sie sie langsam durchgehen:
cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);
Hier bitmask | (1 << i) setzt das i-te Bit der bitmask auf 1, was bedeutet, dass der i-te Scheitelpunkt besucht wurde. Das i hinter dem Komma steht für das neue pos in diesem Funktionsaufruf, das den neuen "letzten" Scheitelpunkt darstellt. cost[pos][i] ist , die Kosten des Reisens von Vertex hinzufügen pos nach Knoten i .
Diese Zeile soll also den cost auf den minimal möglichen Wert für das Reisen zu jedem anderen noch nicht besuchten Scheitelpunkt aktualisieren.
Zeitkomplexität
Die Funktion TSP(bitmask,pos) hat 2^N Werte für bitmask und N Werte für pos . Jede Funktion benötigt O(N) Zeit (die for Schleife). Somit benötigt diese Implementierung O(N^2 * 2^N) Zeit, um die genaue Antwort auszugeben.