Problem trgovskega potnika (TSP):
Glede na nabor mest in razdaljo med vsakim parom mest je problem najti najkrajšo možno pot, ki vsako mesto obišče točno enkrat in se vrne na začetno točko. Upoštevajte razliko med Hamiltonovim ciklom in TSP. Problem Hamiltonovega cikla je ugotoviti, ali obstaja tura, ki vsako mesto obišče natanko enkrat. Tukaj vemo, da obstaja Hamiltonova tura (ker je graf popoln) in dejansko obstaja veliko takšnih tur, problem je najti Hamiltonov cikel z najmanjšo težo.
Na primer, razmislite o grafu, prikazanem na sliki na desni strani. Obisk TSP na grafu je 1-2-4-3-1. Cena potovanja je 10+25+30+15, kar je 80. Težava je slavni NP-težki problem. Za to težavo ni rešitve, ki bi poznala polinomski čas. Sledijo različne rešitve za problem trgovskega potnika.
Naivna rešitev:
1) Mesto 1 upoštevajte kot začetno in končno točko.
2) Ustvari vse (n-1)! Permutacije mest.
3) Izračunajte stroške vsake permutacije in spremljajte najnižjo ceno permutacije.
4) Vrnite permutacijo z minimalnimi stroški.
Časovna zahtevnost: ?(n!)
Dinamično programiranje:
Naj bo podana množica vozlišč {1, 2, 3, 4,….n}. Vzemimo 1 kot začetno in končno točko izhoda. Za vsako drugo vozlišče I (razen 1) najdemo pot najmanjše cene z 1 kot začetno točko, I kot končno točko in vse točke, ki se pojavijo natanko enkrat. Naj strošek te poti stane (i), strošek ustreznega cikla pa stane (i) + dist(i, 1), kjer je dist(i, 1) razdalja od I do 1. Končno vrnemo najmanjša od vseh vrednosti [cost(i) + dist(i, 1)]. Zaenkrat je to videti preprosto.
Zdaj je vprašanje, kako pridobiti stroške (i)? Za izračun stroškov(i) z uporabo dinamičnega programiranja moramo imeti neko rekurzivno relacijo v smislu podproblemov.
Določimo izraz C(S, i) je strošek poti z minimalnimi stroški, ki obišče vsako vozlišče v množici S natanko enkrat, z začetkom pri 1 in koncem pri i . Začnemo z vsemi podmnožicami velikosti 2 in izračunamo C(S, i) za vse podmnožice, kjer je S podmnožica, nato izračunamo C(S, i) za vse podmnožice S velikosti 3 in tako naprej. Upoštevajte, da mora biti 1 prisoten v vsaki podnaboru.
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.> Spodaj je rešitev dinamičnega programiranja za problem z uporabo rekurzivnega + memoiziranega pristopa od zgoraj navzdol: -
pretvorba nfa v dfa
Za vzdrževanje podnaborov lahko uporabimo bitne maske za predstavitev preostalih vozlišč v našem podnaboru. Ker je delovanje bitov hitrejše in je v grafu le malo vozlišč, je bolje uporabiti bitne maske.
kaj je sklad v Javi
Na primer: –
10100 predstavlja vozlišče 2 in vozlišče 4 ostane v nizu za obdelavo
010010 predstavlja vozlišče 1, 4 pa ostane v podnaboru.
OPOMBA:- ignorirajte 0. bit, ker naš graf temelji na 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
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
kopica in kopica sort
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> |
>
ime mesta v ZDA
>
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)> |
>
>
Javascript
pretvorbo niza v datum
>// 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> |
>
>Izhod
The cost of most efficient tour = 80>
Časovna zahtevnost: O(n2*2n) kjer je O(n* 2n)sta največje število edinstvenih podproblemov/stanj in O(n) za prehod (skozi zanko for kot v kodi) v vsakem stanju.
Pomožni prostor: O(n*2n), kjer je n število vozlišč/mest tukaj.
Za niz velikosti n upoštevamo n-2 podmnožic, od katerih ima vsaka velikost n-1, tako da vse podmnožice nimajo nth v sebi. Z uporabo zgornje relacije ponavljanja lahko napišemo rešitev, ki temelji na dinamičnem programiranju. Obstaja največ O(n*2n) podproblemov, vsaka pa za rešitev potrebuje linearni čas. Skupni čas delovanja je torej O(n2*2n). Časovna kompleksnost je veliko manjša od O(n!), vendar še vedno eksponentna. Potreben prostor je prav tako eksponenten. Torej je tudi ta pristop neizvedljiv tudi za nekoliko večje število vozlišč. Kmalu bomo razpravljali o približnih algoritmih za problem trgovskega potnika.
Naslednji članek: Problem trgovskega potnika | Komplet 2
Reference:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf