Problem des Handlungsreisenden (TSP):
Bei einer Reihe von Städten und der Entfernung zwischen jedem Städtepaar besteht das Problem darin, die kürzestmögliche Route zu finden, die jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt. Beachten Sie den Unterschied zwischen Hamilton-Zyklus und TSP. Das Problem des Hamilton-Zyklus besteht darin, herauszufinden, ob es eine Tour gibt, die jede Stadt genau einmal besucht. Hier wissen wir, dass es eine Hamilton-Tour gibt (weil die Grafik vollständig ist) und tatsächlich gibt es viele solcher Touren. Das Problem besteht darin, einen Hamilton-Zyklus mit minimalem Gewicht zu finden.
Betrachten Sie beispielsweise die in der Abbildung auf der rechten Seite gezeigte Grafik. Eine TSP-Tour in der Grafik ist 1-2-4-3-1. Die Kosten für die Tour betragen 10+25+30+15, also 80. Das Problem ist ein bekanntes NP-schweres Problem. Für dieses Problem gibt es keine polynomiellzeitliche bekannte Lösung. Im Folgenden finden Sie verschiedene Lösungen für das Problem des Handlungsreisenden.
Naive Lösung:
1) Betrachten Sie Stadt 1 als Start- und Endpunkt.
2) Erzeuge alle (n-1)! Permutationen von Städten.
3) Berechnen Sie die Kosten jeder Permutation und behalten Sie die Mindestkostenpermutation im Auge.
4) Geben Sie die Permutation mit minimalen Kosten zurück.
Zeitkomplexität: ?(n!)
Dynamische Programmierung:
Die gegebene Menge an Eckpunkten sei {1, 2, 3, 4,….n}. Betrachten wir 1 als Start- und Endpunkt der Ausgabe. Für jeden anderen Scheitelpunkt I (außer 1) finden wir den Pfad mit minimalen Kosten mit 1 als Startpunkt, I als Endpunkt und allen Scheitelpunkten, die genau einmal vorkommen. Angenommen, die Kosten dieses Pfads kosten (i), und die Kosten des entsprechenden Zyklus würden (i) + dist(i, 1) kosten, wobei dist(i, 1) der Abstand von I nach 1 ist. Schließlich geben wir die zurück Minimum aller [cost(i) + dist(i, 1)]-Werte. Das sieht bisher einfach aus.
Nun stellt sich die Frage, wie man die Kosten(i) ermittelt. Um die Kosten (i) mithilfe der dynamischen Programmierung zu berechnen, benötigen wir eine rekursive Beziehung in Bezug auf Teilprobleme.
Lassen Sie uns einen Begriff definieren C(S, i) seien die Kosten des Pfads mit minimalen Kosten, der jeden Scheitelpunkt in der Menge S genau einmal besucht, beginnend bei 1 und endend bei i . Wir beginnen mit allen Teilmengen der Größe 2 und berechnen C(S, i) für alle Teilmengen, wobei S die Teilmenge ist, dann berechnen wir C(S, i) für alle Teilmengen S der Größe 3 und so weiter. Beachten Sie, dass 1 in jeder Teilmenge vorhanden sein muss.
If size of S is 2, then S must be {1, i}, C(S, i) = dist(1, i) Else if size of S is greater than 2. C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.> Nachfolgend finden Sie die dynamische Programmierlösung für das Problem unter Verwendung eines rekursiven und auswendig gelernten Top-Down-Ansatzes: –
scan.nextstring Java
Zur Pflege der Teilmengen können wir die Bitmasken verwenden, um die verbleibenden Knoten in unserer Teilmenge darzustellen. Da Bits schneller zu verarbeiten sind und es nur wenige Knoten im Diagramm gibt, ist die Verwendung von Bitmasken besser.
JSON-Dateien lesen
Zum Beispiel: -
10100 stellt dar, dass Knoten 2 und Knoten 4 zur Verarbeitung im Satz verbleiben
010010 stellt dar, dass Knoten 1 und 4 in der Teilmenge verbleiben.
HINWEIS: Ignorieren Sie das 0. Bit, da unser Diagramm auf 1 basiert
C++
#include> using> namespace> std;> // there are four nodes in example graph (graph is 1-based)> const> int> n = 4;> // give appropriate maximum to avoid overflow> const> int> MAX = 1000000;> // dist[i][j] represents shortest distance to go from i to j> // this matrix can be calculated for any given graph using> // all-pair shortest path algorithms> int> dist[n + 1][n + 1] = {> >{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },> >{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },> >{ 0, 20, 25, 30, 0 },> };> // memoization for top down recursion> int> memo[n + 1][1 << (n + 1)];> int> fun(>int> i,>int> mask)> > >// base case> >// if only ith bit and 1st bit is set in our mask,> >// it implies we have visited all other nodes already> >if> (mask == ((1 << i)> // Driver program to test above logic> int> main()> {> >int> ans = MAX;> >for> (>int> i = 1; i <= n; i++)> >// try to go from node 1 visiting all nodes in> >// between to i then return from i taking the> >// shortest route to 1> >ans = std::min(ans, fun(i, (1 << (n + 1)) - 1)> >+ dist[i][1]);> >printf>(>'The cost of most efficient tour = %d'>, ans);> >return> 0;> }> // This code is contributed by Serjeel Ranjan> |
>
>
Java
import> java.io.*;> import> java.util.*;> public> class> TSE {> >// there are four nodes in example graph (graph is> >// 1-based)> >static> int> n =>4>;> >// give appropriate maximum to avoid overflow> >static> int> MAX =>1000000>;> >// dist[i][j] represents shortest distance to go from i> >// to j this matrix can be calculated for any given> >// graph using all-pair shortest path algorithms> >static> int>[][] dist = {> >{>0>,>0>,>0>,>0>,>0> }, {>0>,>0>,>10>,>15>,>20> },> >{>0>,>10>,>0>,>25>,>25> }, {>0>,>15>,>25>,>0>,>30> },> >{>0>,>20>,>25>,>30>,>0> },> >};> >// memoization for top down recursion> >static> int>[][] memo =>new> int>[n +>1>][>1> << (n +>1>)];> >static> int> fun(>int> i,>int> mask)> >> >// base case> >// if only ith bit and 1st bit is set in our mask,> >// it implies we have visited all other nodes> >// already> >if> (mask == ((>1> << i)> >// Driver program to test above logic> >public> static> void> main(String[] args)> >{> >int> ans = MAX;> >for> (>int> i =>1>; i <= n; i++)> >// try to go from node 1 visiting all nodes in> >// between to i then return from i taking the> >// shortest route to 1> >ans = Math.min(ans, fun(i, (>1> << (n +>1>)) ->1>)> >+ dist[i][>1>]);> >System.out.println(> >'The cost of most efficient tour = '> + ans);> >}> }> // This code is contributed by Serjeel Ranjan> |
>
>
Python3
Wie groß ist mein Monitorbildschirm?
n>=> 4> # there are four nodes in example graph (graph is 1-based)> # dist[i][j] represents shortest distance to go from i to j> # this matrix can be calculated for any given graph using> # all-pair shortest path algorithms> dist>=> [[>0>,>0>,>0>,>0>,>0>], [>0>,>0>,>10>,>15>,>20>], [> >0>,>10>,>0>,>25>,>25>], [>0>,>15>,>25>,>0>,>30>], [>0>,>20>,>25>,>30>,>0>]]> # memoization for top down recursion> memo>=> [[>->1>]>*>(>1> << (n>+>1>))>for> _>in> range>(n>+>1>)]> def> fun(i, mask):> ># base case> ># if only ith bit and 1st bit is set in our mask,> ># it implies we have visited all other nodes already> >if> mask>=>=> ((>1> << i) |>3>):> >return> dist[>1>][i]> ># memoization> >if> memo[i][mask] !>=> ->1>:> >return> memo[i][mask]> >res>=> 10>*>*>9> # result of this sub-problem> ># we have to travel all nodes j in mask and end the path at ith node> ># so for every node j in mask, recursively calculate cost of> ># travelling all nodes in mask> ># except i and then travel back from node j to node i taking> ># the shortest path take the minimum of all possible j nodes> >for> j>in> range>(>1>, n>+>1>):> >if> (mask & (>1> << j)) !>=> 0> and> j !>=> i>and> j !>=> 1>:> >res>=> min>(res, fun(j, mask & (~(>1> << i)))>+> dist[j][i])> >memo[i][mask]>=> res># storing the minimum value> >return> res> # Driver program to test above logic> ans>=> 10>*>*>9> for> i>in> range>(>1>, n>+>1>):> ># try to go from node 1 visiting all nodes in between to i> ># then return from i taking the shortest route to 1> >ans>=> min>(ans, fun(i, (>1> << (n>+>1>))>->1>)>+> dist[i][>1>])> print>(>'The cost of most efficient tour = '> +> str>(ans))> # This code is contributed by Serjeel Ranjan> |
>
>
C#
using> System;> class> TSE> {> >// there are four nodes in example graph (graph is> >// 1-based)> >static> int> n = 4;> >// give appropriate maximum to avoid overflow> >static> int> MAX = 1000000;> >// dist[i][j] represents shortest distance to go from i> >// to j this matrix can be calculated for any given> >// graph using all-pair shortest path algorithms> >static> int>[, ] dist = { { 0, 0, 0, 0, 0 },> >{ 0, 0, 10, 15, 20 },> >{ 0, 10, 0, 25, 25 },> >{ 0, 15, 25, 0, 30 },> >{ 0, 20, 25, 30, 0 } };> >// memoization for top down recursion> >static> int>[, ] memo =>new> int>[(n + 1), (1 << (n + 1))];> >static> int> fun(>int> i,>int> mask)> > 3))> >return> dist[1, i];> > >// memoization> >if> (memo[i, mask] != 0)> >return> memo[i, mask];> >int> res = MAX;>// result of this sub-problem> >// we have to travel all nodes j in mask and end the> >// path at ith node so for every node j in mask,> >// recursively calculate cost of travelling all> >// nodes in mask> >// except i and then travel back from node j to node> >// i taking the shortest path take the minimum of> >// all possible j nodes> >for> (>int> j = 1; j <= n; j++)> >if> ((mask & (1 << j)) != 0 && j != i && j != 1)> >res = Math.Min(res,> >fun(j, mask & (~(1 << i)))> >+ dist[j, i]);> >return> memo[i, mask] = res;> >> >// Driver program to test above logic> >public> static> void> Main()> >{> >int> ans = MAX;> >for> (>int> i = 1; i <= n; i++)> >// try to go from node 1 visiting all nodes in> >// between to i then return from i taking the> >// shortest route to 1> >ans = Math.Min(ans, fun(i, (1 << (n + 1)) - 1)> >+ dist[i, 1]);> >Console.WriteLine(> >'The cost of most efficient tour = '> + ans);> >}> }> // This code is contributed by Tapesh(tapeshdua420)> |
Konvertieren Sie einen String in int Java
>
>
Javascript
>// JavaScript code for the above approach> >// there are four nodes in example graph (graph is 1-based)> >let n = 4;> > >// give appropriate maximum to avoid overflow> >let MAX = 1000000;> >// dist[i][j] represents shortest distance to go from i to j> >// this matrix can be calculated for any given graph using> >// all-pair shortest path algorithms> >let dist = [> >[0, 0, 0, 0, 0], [0, 0, 10, 15, 20],> >[0, 10, 0, 25, 25], [0, 15, 25, 0, 30],> >[0, 20, 25, 30, 0],> >];> >// memoization for top down recursion> >let memo =>new> Array(n + 1);> >for> (let i = 0; i memo[i] = new Array(1 << (n + 1)).fill(0) } function fun(i, mask) // base case // if only ith bit and 1st bit is set in our mask, // it implies we have visited all other nodes already if (mask == ((1 << i) // Driver program to test above logic let ans = MAX; for (let i = 1; i <= n; i++) // try to go from node 1 visiting all nodes in // between to i then return from i taking the // shortest route to 1 ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1) + dist[i][1]); console.log('The cost of most efficient tour ' + ans); // This code is contributed by Potta Lokesh> |
Java-Sammlung
>
>Ausgabe
The cost of most efficient tour = 80>
Zeitkomplexität: O(n2*2N) wo O(n* 2N)sind die maximale Anzahl eindeutiger Teilprobleme/Zustände und O(n) für den Übergang (durch die for-Schleife wie im Code) in jedem Zustand.
Hilfsraum: O(n*2N), wobei n hier die Anzahl der Knoten/Städte ist.
Für eine Menge der Größe n betrachten wir n-2 Teilmengen mit jeweils der Größe n-1, sodass nicht alle Teilmengen das n-te enthalten. Mithilfe der obigen Wiederholungsbeziehung können wir eine dynamische, programmbasierte Lösung schreiben. Es gibt höchstens O(n*2N) Teilprobleme, und jedes einzelne benötigt lineare Zeit zur Lösung. Die Gesamtlaufzeit beträgt daher O(n2*2N). Die Zeitkomplexität ist viel geringer als bei O(n!), ist aber immer noch exponentiell. Auch der Platzbedarf ist exponentiell. Daher ist dieser Ansatz auch für eine etwas höhere Anzahl von Eckpunkten nicht durchführbar. Wir werden demnächst Näherungsalgorithmen für das Problem des Handlungsreisenden diskutieren.
Nächster Artikel: Problem des Handlungsreisenden | Satz 2
Verweise:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf