Problém cestujúceho predajcu (TSP):
Vzhľadom na súbor miest a vzdialenosť medzi každou dvojicou miest je problém nájsť najkratšiu možnú trasu, ktorá navštívi každé mesto presne raz a vráti sa do východiskového bodu. Všimnite si rozdiel medzi Hamiltonovým cyklom a TSP. Problém hamiltonovského cyklu je nájsť, či existuje prehliadka, ktorá navštívi každé mesto práve raz. Tu vieme, že Hamiltonian Tour existuje (pretože graf je kompletný) av skutočnosti existuje veľa takýchto zájazdov, problém je nájsť minimálnu váhu Hamiltonian Cycle.
Zvážte napríklad graf zobrazený na obrázku na pravej strane. Prehliadka TSP v grafe je 1-2-4-3-1. Cena zájazdu je 10+25+30+15, čo je 80. Problémom je známy NP-ťažký problém. Pre tento problém neexistuje žiadne polynomiálne-časovo známe riešenie. Nasledujú rôzne riešenia problému cestujúceho predajcu.
Naivné riešenie:
1) Zvážte mesto 1 ako počiatočný a konečný bod.
2) Vygenerujte všetky (n-1)! Permutácie miest.
3) Vypočítajte náklady na každú permutáciu a sledujte permutáciu minimálnych nákladov.
4) Vráťte permutáciu s minimálnymi nákladmi.
Časová zložitosť: ?(n!)
Dynamické programovanie:
Nech je daná množina vrcholov {1, 2, 3, 4,….n}. Uvažujme 1 ako začiatočný a koncový bod výstupu. Pre každý druhý vrchol I (iný ako 1) nájdeme cestu minimálnych nákladov s 1 ako začiatočným bodom, I ako koncovým bodom a všetky vrcholy sa objavujú práve raz. Nech cena tejto cesty stojí (i) a cena zodpovedajúceho cyklu by stála (i) + dist(i, 1), kde dist(i, 1) je vzdialenosť od I do 1. Nakoniec vrátime minimum zo všetkých hodnôt [cost(i) + dist(i, 1)]. Zatiaľ to vyzerá jednoducho.
Teraz je otázkou, ako získať náklady (i)? Na výpočet nákladov (i) pomocou dynamického programovania potrebujeme mať nejaký rekurzívny vzťah z hľadiska čiastkových problémov.
Definujme pojem C(S, i) sú náklady na cestu s minimálnymi nákladmi, ktorá navštívi každý vrchol v množine S presne raz, počnúc 1 a končiac i . Začneme so všetkými podmnožinami veľkosti 2 a vypočítame C(S, i) pre všetky podmnožiny, kde S je podmnožina, potom vypočítame C(S, i) pre všetky podmnožiny S veľkosti 3 atď. Všimnite si, že 1 musí byť prítomná v každej podmnožine.
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.> Nižšie je uvedené riešenie dynamického programovania problému pomocou rekurzívneho a memoovaného prístupu zhora nadol: -
java escape znak
Na udržiavanie podmnožín môžeme použiť bitové masky na reprezentáciu zostávajúcich uzlov v našej podmnožine. Keďže bity sú rýchlejšie v prevádzke a v grafe je len málo uzlov, je lepšie použiť bitové masky.
kde je vložiť kľúč na klávesnici notebooku
Napríklad: -
10100 predstavuje uzol 2 a uzol 4 sú ponechané v množine na spracovanie
010010 predstavuje uzol 1 a uzol 4 ponechaný v podmnožine.
POZNÁMKA: - ignorujte 0. bit, pretože náš graf je založený 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
latexový stôl
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#
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)> |
>
>
skryté aplikácie v tomto zariadení
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> |
>
>Výkon
The cost of most efficient tour = 80>
Časová zložitosť: O(n2*2n) kde O(n* 2n)sú maximálny počet jedinečných podproblémov/stavov a O(n) pre prechod (cez cyklus for ako v kóde) v každom stave.
vlastnosti série panda
Pomocný priestor: O(n*2n), kde n je počet uzlov/miest tu.
Pre množinu veľkosti n uvažujeme n-2 podmnožiny každej veľkosti n-1 tak, že všetky podmnožiny nemajú n-tu. Pomocou vyššie uvedeného vzťahu opakovania môžeme napísať riešenie založené na dynamickom programovaní. Existuje najviac O(n*2n) podproblémy a každý z nich potrebuje lineárny čas na vyriešenie. Celkový čas chodu je teda O(n2*2n). Časová zložitosť je oveľa menšia ako O(n!), ale stále exponenciálna. Požadovaný priestor je tiež exponenciálny. Takže tento prístup je tiež nerealizovateľný aj pre mierne vyšší počet vrcholov. Čoskoro budeme diskutovať o približných algoritmoch pre problém obchodného cestujúceho.
Ďalší článok: Problém obchodného cestujúceho | Súprava 2
Referencie:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf