Traveling Salesman Problem (TSP):
Givet et sæt byer og afstanden mellem hvert par byer, er problemet at finde den kortest mulige rute, der besøger hver by nøjagtigt én gang og vender tilbage til udgangspunktet. Bemærk forskellen mellem Hamiltonian Cycle og TSP. Hamiltons cykelproblem er at finde ud af, om der findes en tur, der besøger hver by nøjagtigt én gang. Her ved vi, at Hamiltonian Tour eksisterer (fordi grafen er komplet), og faktisk findes der mange sådanne ture, problemet er at finde en Hamiltonian Cycle med minimumvægt.
Overvej f.eks. grafen vist i figuren til højre. En TSP-tur i grafen er 1-2-4-3-1. Omkostningerne ved turen er 10+25+30+15, hvilket er 80. Problemet er et berømt NP-hårdt problem. Der er ingen polynomial-time know-løsning på dette problem. Følgende er forskellige løsninger på problemet med rejsende sælger.
Naiv løsning:
1) Betragt by 1 som start- og slutpunkt.
2) Generer alle (n-1)! Permutationer af byer.
3) Beregn prisen på hver permutation og hold styr på minimumsomkostningspermutationen.
4) Returner permutationen med minimale omkostninger.
Tidskompleksitet: ?(n!)
Dynamisk programmering:
Lad det givne sæt af hjørner være {1, 2, 3, 4,….n}. Lad os betragte 1 som start- og slutpunkt for output. For hvert andet knudepunkt I (bortset fra 1) finder vi minimumsomkostningsstien med 1 som udgangspunkt, I som slutpunkt, og alle knudepunkter vises nøjagtigt én gang. Lad prisen for denne vej koste (i), og prisen for den tilsvarende cyklus ville koste (i) + dist(i, 1), hvor dist(i, 1) er afstanden fra I til 1. Til sidst returnerer vi minimum af alle [cost(i) + dist(i, 1)] værdier. Dette ser simpelt ud indtil videre.
Nu er spørgsmålet, hvordan man får omkostninger(i)? For at beregne omkostningerne(i) ved hjælp af dynamisk programmering, er vi nødt til at have en rekursiv relation med hensyn til delproblemer.
Lad os definere et udtryk C(S, i) være prisen for den minimale omkostningssti, der besøger hvert toppunkt i sæt S nøjagtigt én gang, startende ved 1 og slutter ved i . Vi starter med alle delmængder af størrelse 2 og beregner C(S, i) for alle delmængder, hvor S er delmængden, derefter beregner vi C(S, i) for alle delmængder S af størrelse 3 og så videre. Bemærk, at 1 skal være til stede i hver delmængde.
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øsning til problemet ved hjælp af top-down rekursiv+memoiseret tilgang: -
søgemaskine og eksempler
For at vedligeholde delmængderne kan vi bruge bitmaskerne til at repræsentere de resterende noder i vores delmængde. Da bits er hurtigere at betjene, og der kun er få noder i grafen, er bitmasker bedre at bruge.
nginx variabler
For eksempel: -
10100 repræsenterer node 2 og node 4 efterlades i sæt til at blive behandlet
010010 repræsenterer node 1, og 4 er tilbage i undersæt.
BEMÆRK:- ignorer den 0. bit, da vores graf er 1-baseret
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
mysql ændre kolonnetype
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
et array i java
>// 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>
Tidskompleksitet: O(n2*2n) hvor O(n* 2n)er det maksimale antal unikke underproblemer/tilstande og O(n) for overgang (gennem for loop som i kode) i hver stat.
Hjælpeplads: O(n*2n), hvor n er antallet af noder/byer her.
For et sæt af størrelse n betragter vi n-2 delmængder hver af størrelse n-1, således at alle delmængder ikke har n'te i sig. Ved at bruge ovenstående gentagelsesrelation kan vi skrive en dynamisk programmeringsbaseret løsning. Der er højst O(n*2n) underproblemer, og hver enkelt tager lineær tid at løse. Den samlede køretid er derfor O(n2*2n). Tidskompleksiteten er meget mindre end O(n!), men stadig eksponentiel. Den nødvendige plads er også eksponentiel. Så denne tilgang er også umulig selv for et lidt højere antal hjørner. Vi vil snart diskutere omtrentlige algoritmer til problemet med rejsende sælger.
Næste artikel: Rejsende sælgerproblem | Sæt 2
Referencer:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf