Problem med resande säljare (TSP):
Med tanke på en uppsättning städer och avståndet mellan varje par av städer, är problemet att hitta den kortaste möjliga vägen som besöker varje stad exakt en gång och återvänder till startpunkten. Observera skillnaden mellan Hamiltonian Cycle och TSP. Hamiltons cykelproblem är att ta reda på om det finns en tur som besöker varje stad exakt en gång. Här vet vi att Hamiltonian Tour existerar (eftersom grafen är komplett) och i själva verket finns många sådana turer, problemet är att hitta en Hamiltonian Cycle med minsta vikt.
Tänk till exempel på grafen som visas i figuren till höger. En TSP-tur i grafen är 1-2-4-3-1. Kostnaden för turen är 10+25+30+15 vilket är 80. Problemet är ett känt NP-hårt problem. Det finns ingen polynom-tid vet lösning för detta problem. Följande är olika lösningar på problemet med resande säljare.
Naiv lösning:
1) Betrakta stad 1 som start- och slutpunkt.
2) Generera alla (n-1)! Permutationer av städer.
3) Beräkna kostnaden för varje permutation och håll reda på minimikostnadspermutationen.
4) Returnera permutationen med lägsta kostnad.
Tidskomplexitet: ?(n!)
Dynamisk programmering:
Låt den givna uppsättningen av hörn vara {1, 2, 3, 4,….n}. Låt oss betrakta 1 som start- och slutpunkt för utdata. För vartannat vertex I (annat än 1) hittar vi minimikostnadsvägen med 1 som startpunkt, I som slutpunkt och alla hörn visas exakt en gång. Låt kostnaden för denna väg kosta (i), och kostnaden för motsvarande cykel skulle kosta (i) + dist(i, 1) där dist(i, 1) är avståndet från I till 1. Slutligen returnerar vi minimum av alla [cost(i) + dist(i, 1)] värden. Det här ser enkelt ut än så länge.
Nu är frågan hur man får kostnad(i)? För att beräkna kostnaden(i) med hjälp av dynamisk programmering måste vi ha en rekursiv relation i termer av delproblem.
Låt oss definiera en term C(S, i) vara kostnaden för den lägsta kostnadsvägen som besöker varje hörn i set S exakt en gång, med början på 1 och slutar vid i . Vi börjar med alla delmängder av storlek 2 och beräknar C(S, i) för alla delmängder där S är delmängden, sedan beräknar vi C(S, i) för alla delmängder S av storlek 3 och så vidare. Observera att 1 måste finnas i varje delmängd.
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.> Nedan är den dynamiska programmeringslösningen för problemet med uppifrån och ned rekursiv+memoiserad metod: -
gimp-teckensnittslista
För att underhålla delmängderna kan vi använda bitmaskerna för att representera de återstående noderna i vår delmängd. Eftersom bitar är snabbare att använda och det bara finns få noder i grafen är bitmasker bättre att använda.
infoga i tangentbordet
Till exempel: -
10100 representerar nod 2 och nod 4 lämnas i set för att bearbetas
010010 representerar nod 1 och 4 är kvar i delmängd.
OBS:- ignorera den 0:e biten eftersom vår graf är 1-baserad
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
powershell större än eller lika
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
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#
konvertera sträng till int
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)> |
>
>
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> |
>
>Produktion
The cost of most efficient tour = 80>
Tidskomplexitet: O(n2*2n) där O(n* 2n)är maximalt antal unika underproblem/tillstånd och O(n) för övergång (genom för loop som i kod) i varje tillstånd.
Hjälputrymme: O(n*2n), där n är antalet noder/städer här.
om av rudyard kipling sammanfattning
För en uppsättning av storlek n betraktar vi n-2 delmängder var och en av storlek n-1 så att alla delmängder inte har n:te i sig. Med hjälp av ovanstående återkommande relation kan vi skriva en dynamisk programmeringsbaserad lösning. Det finns högst O(n*2n) delproblem, och var och en tar linjär tid att lösa. Den totala körtiden är därför O(n2*2n). Tidskomplexiteten är mycket mindre än O(n!) men fortfarande exponentiell. Det utrymme som krävs är också exponentiellt. Så detta tillvägagångssätt är också omöjligt även för ett något högre antal hörn. Vi kommer snart att diskutera ungefärliga algoritmer för resandeförsäljarproblemet.
Nästa artikel: Problem med resande säljare | Set 2
Referenser:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf