Problema del viajante de comercio (TSP):
Dado un conjunto de ciudades y la distancia entre cada par de ciudades, el problema es encontrar la ruta más corta posible que visite cada ciudad exactamente una vez y regrese al punto de partida. Tenga en cuenta la diferencia entre el ciclo hamiltoniano y TSP. El problema del ciclo hamiltoniano consiste en encontrar si existe un recorrido que visite cada ciudad exactamente una vez. Aquí sabemos que el Tour Hamiltoniano existe (porque el gráfico está completo) y de hecho existen muchos tours de este tipo, el problema es encontrar un Ciclo Hamiltoniano de peso mínimo.
Por ejemplo, considere el gráfico que se muestra en la figura del lado derecho. Un recorrido de TSP en el gráfico es 1-2-4-3-1. El costo del recorrido es 10+25+30+15, que es 80. El problema es un famoso problema NP-difícil. No existe una solución conocida en tiempo polinomial para este problema. Las siguientes son diferentes soluciones para el problema del viajante.
Solución ingenua:
1) Considere la ciudad 1 como punto de inicio y fin.
2) ¡Genera todo (n-1)! Permutaciones de ciudades.
3) Calcule el costo de cada permutación y realice un seguimiento de la permutación de costo mínimo.
4) Devolver la permutación con coste mínimo.
Complejidad del tiempo: ?(n!)
Programación dinámica:
Sea el conjunto de vértices dado {1, 2, 3, 4,….n}. Consideremos 1 como punto inicial y final de salida. Para todos los demás vértices I (distintos de 1), encontramos la ruta de costo mínimo con 1 como punto inicial, I como punto final y todos los vértices aparecen exactamente una vez. Supongamos que el costo de este camino cuesta (i), y el costo del Ciclo correspondiente costaría (i) + dist(i, 1) donde dist(i, 1) es la distancia de I a 1. Finalmente, devolvemos el mínimo de todos los valores [costo(i) + dist(i, 1)]. Esto parece simple hasta ahora.
Ahora la pregunta es ¿cómo obtener el costo (i)? Para calcular el costo (i) usando programación dinámica, necesitamos tener alguna relación recursiva en términos de subproblemas.
Definamos un término C(S, i) sea el costo de la ruta de costo mínimo que visita cada vértice en el conjunto S exactamente una vez, comenzando en 1 y terminando en i . Comenzamos con todos los subconjuntos de tamaño 2 y calculamos C(S, i) para todos los subconjuntos donde S es el subconjunto, luego calculamos C(S, i) para todos los subconjuntos S de tamaño 3 y así sucesivamente. Tenga en cuenta que 1 debe estar presente en cada subconjunto.
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ón se muestra la solución de programación dinámica para el problema utilizando un enfoque recursivo+memorizado de arriba hacia abajo: –
leer archivos json
Para mantener los subconjuntos, podemos usar máscaras de bits para representar los nodos restantes en nuestro subconjunto. Dado que los bits son más rápidos de operar y solo hay unos pocos nodos en el gráfico, es mejor usar máscaras de bits.
apache
Por ejemplo: -
10100 representa el nodo 2 y el nodo 4 se dejan configurados para ser procesados
010010 representa el nodo 1 y el 4 se dejan en el subconjunto.
NOTA: - ignore el bit 0 ya que nuestro gráfico está basado 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
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
lista ordenar java
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> |
>
mientras bucle java
>
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
número a cadena java
>// 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> |
>
>Producción
The cost of most efficient tour = 80>
Complejidad del tiempo: O(n2*2norte) donde O(norte* 2norte)son el número máximo de subproblemas/estados únicos y O(n) para la transición (a través del bucle for como en el código) en todos los estados.
Espacio auxiliar: O(n*2norte), donde n es el número de nodos/ciudades aquí.
Para un conjunto de tamaño n, consideramos n-2 subconjuntos, cada uno de ellos de tamaño n-1, de modo que todos los subconjuntos no tengan el n-ésimo. Usando la relación de recurrencia anterior, podemos escribir una solución basada en programación dinámica. Hay como máximo O(n*2norte) subproblemas, y cada uno toma un tiempo lineal para resolverse. Por lo tanto, el tiempo total de ejecución es O(n2*2norte). La complejidad del tiempo es mucho menor que O(n!) pero sigue siendo exponencial. El espacio requerido también es exponencial. Por tanto, este enfoque tampoco es factible incluso para un número ligeramente mayor de vértices. Pronto discutiremos algoritmos aproximados para el problema del viajante.
Artículo siguiente: El problema del viajante | Conjunto 2
Referencias:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf