Problema vânzătorului călători (TSP):
Având în vedere un set de orașe și distanța dintre fiecare pereche de orașe, problema este de a găsi cel mai scurt traseu posibil care vizitează fiecare oraș exact o dată și se întoarce la punctul de plecare. Observați diferența dintre Ciclul Hamiltonian și TSP. Problema ciclului hamiltonian este de a afla dacă există un tur care vizitează fiecare oraș exact o dată. Aici știm că există turul Hamiltonian (pentru că graficul este complet) și, de fapt, există multe astfel de tururi, problema este să găsim o greutate minimă a Ciclului Hamiltonian.
De exemplu, luați în considerare graficul prezentat în figura din partea dreaptă. Un tur TSP din grafic este 1-2-4-3-1. Costul turului este 10+25+30+15, adică 80. Problema este o problemă faimoasă NP-hard. Nu există o soluție cunoscută în timp polinomial pentru această problemă. Următoarele sunt diferite soluții pentru problema vânzătorului ambulant.
Soluție naivă:
1) Considerați orașul 1 ca punct de plecare și de sfârșit.
2) Generați toate (n-1)! Permutări ale orașelor.
3) Calculați costul fiecărei permutări și urmăriți permutarea costului minim.
4) Returnați permutarea cu cost minim.
Complexitatea timpului: ?(n!)
Programare dinamică:
Fie mulțimea dată de vârfuri {1, 2, 3, 4,….n}. Să considerăm 1 ca punct de început și de sfârșit al ieșirii. Pentru fiecare alt vârf I (altul decât 1), găsim calea costului minim cu 1 ca punct de plecare, I ca punct de sfârșit și toate vârfurile care apar exact o dată. Fie costul acestei căi costă (i), iar costul ciclului corespunzător ar costa (i) + dist(i, 1) unde dist(i, 1) este distanța de la I la 1. În cele din urmă, returnăm minim al tuturor valorilor [cost(i) + dist(i, 1)]. Acest lucru pare simplu până acum.
Acum întrebarea este cum să obțineți costul (i)? Pentru a calcula costul(i) folosind programarea dinamică, trebuie să avem o relație recursivă în termeni de sub-probleme.
Să definim un termen C(S, i) este costul căii costului minim care vizitează fiecare vârf din mulțimea S exact o dată, începând de la 1 și terminând la i . Începem cu toate submulțimile de dimensiunea 2 și calculăm C(S, i) pentru toate submulțimile unde S este submulțimea, apoi calculăm C(S, i) pentru toate submulțimile S de dimensiunea 3 și așa mai departe. Rețineți că 1 trebuie să fie prezent în fiecare subset.
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.> Mai jos este soluția de programare dinamică pentru problemă folosind abordarea recursiv+de sus în jos: -
mvc java
Pentru a menține subseturile, putem folosi măștile de biți pentru a reprezenta nodurile rămase din subsetul nostru. Deoarece biții sunt mai rapid de acționat și există doar câteva noduri în grafic, este mai bine să utilizați biți.
ce este awt
De exemplu: -
10100 reprezintă nodul 2 și nodul 4 sunt lăsate în set pentru a fi procesate
010010 reprezintă nodul 1 și 4 sunt lăsați în subset.
NOTĂ:- ignorați al 0-lea bit deoarece graficul nostru este bazat pe 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
Actrița Sai Pallavi
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)> |
>
>
sensul dhl
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> |
>
>Ieșire
The cost of most efficient tour = 80>
Complexitatea timpului: O(n2*2n) unde O(n* 2n)sunt numărul maxim de subprobleme/stări unice și O(n) pentru tranziție (prin bucla for ca în cod) în fiecare stare.
arraylist sortată
Spațiu auxiliar: O(n*2n), unde n este numărul de noduri/orașe aici.
Pentru o mulțime de mărimea n, considerăm n-2 submulțimi fiecare cu dimensiunea n-1 astfel încât toate submulțimile să nu aibă n-a în ele. Folosind relația de recurență de mai sus, putem scrie o soluție dinamică bazată pe programare. Există cel mult O(n*2n) subprobleme, iar fiecare dintre ele necesită timp liniar pentru a se rezolva. Timpul total de rulare este prin urmare O(n2*2n). Complexitatea timpului este mult mai mică decât O(n!), dar totuși exponențială. Spațiul necesar este și el exponențial. Deci, această abordare este, de asemenea, imposibilă chiar și pentru un număr puțin mai mare de vârfuri. În curând vom discuta despre algoritmi aproximativi pentru problema vânzătorului ambulant.
Articolul următor: Problema vânzătorului ambulant | Setul 2
Referinte:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf