Problema del venedor ambulant (TSP):
Tenint en compte un conjunt de ciutats i la distància entre cada parell de ciutats, el problema és trobar la ruta més curta possible que visiti cada ciutat exactament una vegada i torni al punt de partida. Observeu la diferència entre el cicle hamiltonià i el TSP. El problema del cicle hamiltonià consisteix a trobar si existeix un recorregut que visiti cada ciutat exactament una vegada. Aquí sabem que existeix el Tour Hamiltonià (perquè el gràfic és complet) i, de fet, existeixen molts d'aquests recorreguts, el problema és trobar un Cicle Hamiltonià de pes mínim.
Per exemple, considereu el gràfic que es mostra a la figura de la dreta. Un recorregut TSP al gràfic és 1-2-4-3-1. El cost de l'excursió és de 10+25+30+15, que és de 80. El problema és un famós problema NP-hard. No hi ha una solució coneguda en temps polinomial per a aquest problema. A continuació es mostren diferents solucions per al problema del venedor ambulant.
Solució ingènua:
1) Considereu la ciutat 1 com a punt inicial i final.
2) Genera tots (n-1)! Permutacions de ciutats.
3) Calculeu el cost de cada permutació i feu un seguiment de la permutació de cost mínim.
4) Retorna la permutació amb un cost mínim.
Complexitat temporal: ?(n!)
Programació dinàmica:
Sigui el conjunt donat de vèrtexs {1, 2, 3, 4,….n}. Considerem 1 com el punt inicial i final de la sortida. Per a cada altre vèrtex I (que no sigui 1), trobem el camí del cost mínim amb 1 com a punt de partida, I com a punt final i tots els vèrtexs apareixen exactament una vegada. Sigui el cost d'aquest camí (i), i el cost del Cicle corresponent costaria (i) + dist(i, 1) on dist(i, 1) és la distància de I a 1. Finalment, retornem el mínim de tots els valors [cost(i) + dist(i, 1)]. Això sembla senzill fins ara.
Ara la pregunta és com obtenir el cost (i)? Per calcular el cost(i) mitjançant la programació dinàmica, hem de tenir alguna relació recursiva en termes de subproblemes.
Definim un terme C(S, i) sigui el cost del camí de cost mínim que visita cada vèrtex del conjunt S exactament una vegada, començant a 1 i acabant a i . Comencem amb tots els subconjunts de mida 2 i calculem C(S, i) per a tots els subconjunts on S és el subconjunt, després calculem C(S, i) per a tots els subconjunts S de mida 3 i així successivament. Tingueu en compte que 1 ha d'estar present a cada subconjunt.
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.> A continuació es mostra la solució de programació dinàmica per al problema utilitzant un enfocament recursiu de dalt a baix + memoritzat:
int per duplicar
Per mantenir els subconjunts podem utilitzar les màscares de bits per representar els nodes restants del nostre subconjunt. Com que els bits són més ràpids d'operar i només hi ha pocs nodes al gràfic, és millor utilitzar màscares de bits.
com desreferenciar un punter a c
Per exemple: -
10100 representa el node 2 i el node 4 es deixen en conjunt per ser processats
010010 representa que el node 1 i 4 queden al subconjunt.
NOTA: ignoreu el bit 0 ja que el nostre gràfic està basat en 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
disseny de quadrícula
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> |
>
>
Python 3
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)> |
>
string.format java
>
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> |
>
>
índex de javaSortida
The cost of most efficient tour = 80>
Complexitat temporal: O(n2*2n) on O(n* 2n)són el nombre màxim de subproblemes/estats únics i O(n) per a la transició (a través del bucle for com en el codi) en tots els estats.
Espai auxiliar: O(n*2n), on n és el nombre de nodes/ciutats aquí.
Per a un conjunt de mida n, considerem n-2 subconjunts cadascun de mida n-1 de manera que tots els subconjunts no tenen n-és. Utilitzant la relació de recurrència anterior, podem escriure una solució basada en programació dinàmica. Hi ha com a màxim O(n*2n) subproblemes, i cadascun triga un temps lineal a resoldre. Per tant, el temps total de funcionament és O(n2*2n). La complexitat temporal és molt menor que O(n!), però encara és exponencial. L'espai requerit també és exponencial. Per tant, aquest enfocament també és inviable fins i tot per a un nombre lleugerament superior de vèrtexs. Aviat parlarem d'algorismes aproximats per al problema del venedor ambulant.
Article següent: Problema del venedor ambulant | Set 2
Referències:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf