Traveling Salesman Problem (TSP):
Gitt et sett med byer og avstanden mellom hvert par av byer, er problemet å finne den korteste mulige ruten som besøker hver by nøyaktig én gang og går tilbake til utgangspunktet. Legg merke til forskjellen mellom Hamiltonian Cycle og TSP. Hamiltons syklusproblem er å finne ut om det finnes en tur som besøker hver by nøyaktig én gang. Her vet vi at Hamiltonian Tour eksisterer (fordi grafen er komplett) og faktisk eksisterer mange slike turer, problemet er å finne en Hamiltonian Cycle med minimum vekt.
Tenk for eksempel på grafen vist i figuren til høyre. En TSP-tur i grafen er 1-2-4-3-1. Kostnaden for turen er 10+25+30+15 som er 80. Problemet er et kjent NP-hardt problem. Det er ingen polynomisk-tid kjent løsning for dette problemet. Følgende er forskjellige løsninger på problemet med reisende selger.
Naiv løsning:
1) Betrakt by 1 som start- og sluttpunkt.
2) Generer alle (n-1)! Permutasjoner av byer.
3) Beregn kostnadene for hver permutasjon og hold styr på minimumskostnadspermutasjonen.
4) Returner permutasjonen med minimumskostnad.
Tidskompleksitet: ?(n!)
Dynamisk programmering:
La det gitte settet med toppunkter være {1, 2, 3, 4,….n}. La oss vurdere 1 som start- og sluttpunkt for utdata. For hvert annet toppunkt I (annet enn 1), finner vi minimumskostnadsbanen med 1 som startpunkt, I som sluttpunkt, og alle toppunkter vises nøyaktig én gang. La kostnaden for denne banen koste (i), og kostnaden for den tilsvarende syklusen vil koste (i) + dist(i, 1) der dist(i, 1) er avstanden fra I til 1. Til slutt returnerer vi minimum av alle [cost(i) + dist(i, 1)] verdier. Dette ser enkelt ut så langt.
Nå er spørsmålet hvordan få kostnad(i)? For å beregne kostnaden(i) ved hjelp av dynamisk programmering, må vi ha en rekursiv relasjon når det gjelder delproblemer.
La oss definere et begrep C(S, i) være kostnaden for minimumskostnadsbanen som besøker hvert toppunkt i sett S nøyaktig én gang, starter på 1 og slutter på i . Vi starter med alle delmengder av størrelse 2 og beregner C(S, i) for alle delmengder der S er delmengden, deretter beregner vi C(S, i) for alle delmengder S av størrelse 3 og så videre. Merk at 1 må være til stede i hvert delsett.
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.> Nedenfor er den dynamiske programmeringsløsningen for problemet ved å bruke ovenfra og ned rekursiv+memoisert tilnærming:-
hvordan lese csv-filen i java
For å opprettholde delsettene kan vi bruke bitmaskene til å representere de gjenværende nodene i delsettet vårt. Siden bits er raskere å betjene og det bare er få noder i grafen, er bitmasker bedre å bruke.
java scan.nextstring
For eksempel: -
10100 representerer node 2 og node 4 er igjen i sett for å bli behandlet
010010 representerer node 1 og 4 er igjen i delsett.
MERK:- ignorer den 0. biten siden grafen vår er 1-basert
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
analysere streng til int
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)> |
amrita rao skuespiller
>
>
Javascript
mysql ikke lik
>// 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> |
>
>Produksjon
The cost of most efficient tour = 80>
Tidskompleksitet : O(n2*2n) hvor O(n* 2n)er maksimalt antall unike underproblemer/tilstander og O(n) for overgang (gjennom for loop som i kode) i hver stat.
Auxiliary Space: O(n*2n), hvor n er antall noder/byer her.
For et sett med størrelse n, vurderer vi n-2 delmengder hver av størrelse n-1 slik at alle delmengder ikke har nth i seg. Ved å bruke gjentakelsesrelasjonen ovenfor kan vi skrive en dynamisk programmeringsbasert løsning. Det er høyst O(n*2n) delproblemer, og hver enkelt tar lineær tid å løse. Den totale kjøretiden er derfor O(n2*2n). Tidskompleksiteten er mye mindre enn O(n!), men fortsatt eksponentiell. Plassen som kreves er også eksponentiell. Så denne tilnærmingen er også umulig selv for et litt høyere antall hjørner. Vi skal snart diskutere omtrentlige algoritmer for reisende selgerproblem.
Neste artikkel: Reisende selgerproblem | Sett 2
Referanser:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf