Ceļojošā pārdevēja problēma (TSP):
Ņemot vērā pilsētu kopu un attālumu starp katru pilsētu pāri, problēma ir atrast īsāko iespējamo maršrutu, kas apmeklē katru pilsētu tieši vienu reizi un atgriežas sākuma punktā. Ņemiet vērā atšķirību starp Hamiltona ciklu un TSP. Hamiltona cikla problēma ir noskaidrot, vai pastāv ekskursija, kas apmeklē katru pilsētu tieši vienu reizi. Šeit mēs zinām, ka Hamiltona tūre pastāv (jo grafiks ir pilnīgs), un patiesībā pastāv daudzas šādas ekskursijas, problēma ir atrast minimālo svaru Hamiltona ciklu.
Piemēram, ņemiet vērā diagrammu, kas parādīta attēlā labajā pusē. TSP ceļvedis grafikā ir 1-2-4-3-1. Ekskursijas izmaksas ir 10+25+30+15, kas ir 80. Problēma ir slavena NP-hard problēma. Šai problēmai nav polinoma laika zināma risinājuma. Tālāk ir sniegti dažādi risinājumi ceļojošā pārdevēja problēmai.
Naivs risinājums:
1) Apsveriet pilsētu 1 par sākuma un beigu punktu.
2) Ģenerē visu (n-1)! Pilsētu permutācijas.
3) Aprēķiniet katras permutācijas izmaksas un sekojiet līdzi minimālo izmaksu permutācijai.
4) Atgrieziet permutāciju ar minimālām izmaksām.
Laika sarežģītība: ?(n!)
Dinamiskā programmēšana:
Lai dotā virsotņu kopa būtu {1, 2, 3, 4,….n}. Apskatīsim 1 kā izvades sākuma un beigu punktu. Katrai otrai virsotnei I (izņemot 1) mēs atrodam minimālo izmaksu ceļu ar 1 kā sākuma punktu, I kā beigu punktu un visas virsotnes parādās tieši vienu reizi. Ļaujiet šī ceļa izmaksām (i) un atbilstošā cikla izmaksām (i) + dist(i, 1), kur dist(i, 1) ir attālums no I līdz 1. Visbeidzot, mēs atgriežam visu [izmaksas(i) + dist(i, 1)] vērtību minimums. Tas pagaidām izskatās vienkārši.
Tagad jautājums ir, kā iegūt izmaksu (i)? Lai aprēķinātu izmaksas(i), izmantojot dinamisko programmēšanu, mums ir nepieciešama kāda rekursīva attiecība apakšproblēmu izteiksmē.
Definēsim terminu C(S, i) ir izmaksas par minimālo izmaksu ceļu, kas apmeklē katru S kopas virsotni tieši vienu reizi, sākot ar 1 un beidzot ar i . Mēs sākam ar visām 2. izmēra apakškopām un aprēķinām C(S, i) visām apakškopām, kur S ir apakškopa, tad mēs aprēķinām C(S, i) visām 3. izmēra apakškopām S un tā tālāk. Ņemiet vērā, ka 1 ir jābūt katrā apakškopā.
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.> Tālāk ir sniegts problēmas dinamiskās programmēšanas risinājums, izmantojot lejupejošu rekursīvo + atmiņā saglabāto pieeju: -
css necaurredzamības pāreja
Apakškopu uzturēšanai mēs varam izmantot bitmaskas, lai attēlotu atlikušos mezglus mūsu apakškopā. Tā kā biti darbojas ātrāk un grafikā ir tikai daži mezgli, labāk ir izmantot bitmaskas.
labākais smaids pasaulē
Piemēram: -
10100 apzīmē mezglu 2, un mezgls 4 ir atstāts komplektā, lai tos apstrādātu
010010 apzīmē mezglu 1 un 4 ir atstāti apakškopā.
PIEZĪME: - ignorējiet 0. bitu, jo mūsu diagramma ir balstīta uz 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> |
savienība pret arodbiedrību visiem
>
>
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#
sakārtots masīvu saraksts 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> |
>
>Izvade
The cost of most efficient tour = 80>
Laika sarežģītība: O(n2*2n) kur O(n*2n)ir maksimālais unikālo apakšproblēmu/stāvokļu skaits un O(n) pārejai (caur cilpai kā kodā) visos stāvokļos.
Papildtelpa: O(n*2n), kur n ir mezglu/pilsētu skaits šeit.
n lieluma kopai mēs uzskatām, ka n-2 apakškopas katra ar lielumu n-1 tā, ka visās apakškopās nav n-tās. Izmantojot iepriekš minēto atkārtošanās relāciju, mēs varam uzrakstīt uz dinamisku programmēšanu balstītu risinājumu. Ir ne vairāk kā O(n*2n) apakšproblēmas, un katras no tām atrisināšana prasa lineāru laiku. Tādējādi kopējais darbības laiks ir O (n2*2n). Laika sarežģītība ir daudz mazāka par O (n!), bet joprojām ir eksponenciāla. Nepieciešamā vieta ir arī eksponenciāla. Tātad šī pieeja nav iespējama pat nedaudz lielākam virsotņu skaitam. Drīzumā mēs apspriedīsim aptuvenos algoritmus ceļojošā pārdevēja problēmai.
Nākamais raksts: Ceļojošā pārdevēja problēma | 2. komplekts
git rebase
Atsauces:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf