Keliaujančio pardavėjo problema (TSP):
Atsižvelgiant į miestų rinkinį ir atstumą tarp kiekvienos miestų poros, problema yra rasti trumpiausią įmanomą maršrutą, kuris aplankytų kiekvieną miestą tiksliai vieną kartą ir sugrįžtų į pradinį tašką. Atkreipkite dėmesį į skirtumą tarp Hamiltono ciklo ir TSP. Hamiltono ciklo problema yra išsiaiškinti, ar yra kelionė, kuri aplankytų kiekvieną miestą tiksliai vieną kartą. Čia mes žinome, kad Hamiltono turas egzistuoja (nes grafikas yra baigtas), ir iš tikrųjų yra daug tokių kelionių, todėl problema yra rasti minimalų Hamiltono ciklą.
Pavyzdžiui, apsvarstykite diagramą, parodytą paveikslėlyje dešinėje. TSP turas diagramoje yra 1-2-4-3-1. Ekskursijos kaina yra 10+25+30+15, tai yra 80. Problema yra garsioji NP sudėtinga problema. Šios problemos daugianario laiko žinomo sprendimo nėra. Toliau pateikiami skirtingi keliaujančio pardavėjo problemos sprendimai.
Naivus sprendimas:
1) Laikykite 1 miestą pradžios ir pabaigos tašku.
2) Sugeneruoti viską (n-1)! Miestų permutacijos.
3) Apskaičiuokite kiekvienos permutacijos kainą ir stebėkite minimalių sąnaudų permutaciją.
4) Grąžinkite permutaciją su minimaliomis sąnaudomis.
Laiko sudėtingumas: ?(n!)
Dinaminis programavimas:
Tegul duotoji viršūnių aibė yra {1, 2, 3, 4,….n}. Išvesties pradžios ir pabaigos taškais laikykime 1. Kiekvienai kitai viršūnei I (išskyrus 1) randame minimalių išlaidų kelią, kurio pradžios taškas yra 1, pabaigos taškas I, o visos viršūnės pasirodo tiksliai vieną kartą. Tegul šio kelio kaina kainuotų (i), o atitinkamo ciklo kaina kainuotų (i) + dist(i, 1), kur dist(i, 1) yra atstumas nuo I iki 1. Galiausiai grąžiname visų [cost(i) + dist(i, 1)] reikšmių minimumas. Tai kol kas atrodo paprasta.
Dabar kyla klausimas, kaip gauti mokestį (i)? Norėdami apskaičiuoti išlaidas (i) naudodami dinaminį programavimą, turime turėti tam tikrą rekursinį ryšį, kalbant apie antrines problemas.
Apibrėžkime terminą C(S, i) yra minimalių sąnaudų kelio, aplankančio kiekvieną S aibės viršūnę, kaina lygiai vieną kartą, pradedant nuo 1 ir baigiant i . Pradedame nuo visų 2 dydžio poaibių ir apskaičiuojame C(S, i) visiems poaibiams, kur S yra poaibis, tada apskaičiuojame C(S, i) visiems 3 dydžio S poaibiams ir pan. Atminkite, kad 1 turi būti kiekviename pogrupyje.
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.> Žemiau pateikiamas dinaminis problemos programavimo sprendimas, naudojant rekursinį + atmintyje metodą iš viršaus į apačią: -
streptas
Norėdami išlaikyti poaibius, galime naudoti bitų kaukes, kad pavaizduotume likusius mūsų poaibio mazgus. Kadangi bitai veikia greičiau ir grafike yra tik keli mazgai, geriau naudoti bitų kaukes.
parametras apvalkalo scenarijuje
Pavyzdžiui: -
10100 reiškia 2 mazgą, o 4 mazgas paliktas rinkinyje, kurį reikia apdoroti
010010 reiškia 1 mazgą, o 4 paliekami poaibyje.
PASTABA: - nepaisykite 0-ojo bito, nes mūsų grafikas yra pagrįstas 1
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
shehzad poonawala
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#
string.replaceall java
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> |
>
>Išvestis
The cost of most efficient tour = 80>
Laiko sudėtingumas: O (n2*2n) kur O(n*2n)yra maksimalus unikalių subproblemų / būsenų skaičius ir O(n) perėjimui (per kilpą, kaip ir kode) kiekvienoje būsenoje.
Pagalbinė erdvė: O(n*2n), kur n yra mazgų / miestų skaičius čia.
mesti eilutę į int
n dydžio aibėje laikome n-2 poaibius, kurių kiekvienas yra n-1 dydžio, kad visuose poaibiuose nebūtų n-osios. Naudodami aukščiau pateiktą pasikartojimo ryšį, galime parašyti dinaminiu programavimu pagrįstą sprendimą. Daugiausia yra O(n*2n) subproblemas, ir kiekvienai iš jų išspręsti reikia tiesinio laiko. Taigi bendra veikimo trukmė yra O (n2*2n). Laiko sudėtingumas yra daug mažesnis nei O (n!), bet vis tiek eksponentinis. Reikalinga erdvė taip pat yra eksponentinė. Taigi šis metodas taip pat neįgyvendinamas net ir šiek tiek didesniam viršūnių skaičiui. Netrukus aptarsime apytikslius keliaujančio pardavėjo problemos algoritmus.
Kitas straipsnis: Keliaujančio pardavėjo problema | 2 rinkinys
Nuorodos:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf