DAA - Problema del vendedor ambulante

Planteamiento del problema

Un viajero necesita visitar todas las ciudades de una lista, donde se conocen las distancias entre todas las ciudades y cada ciudad debe visitarse una sola vez. ¿Cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen?

Solución

El problema del vendedor ambulante es el problema computacional más notorio. Podemos utilizar un enfoque de fuerza bruta para evaluar cada recorrido posible y seleccionar el mejor. porn número de vértices en un gráfico, hay (n - 1)! número de posibilidades.

En lugar de utilizar la fuerza bruta mediante un enfoque de programación dinámica, la solución se puede obtener en menos tiempo, aunque no existe un algoritmo de tiempo polinomial.

Consideremos un gráfico G = (V, E), dónde V es un conjunto de ciudades y Ees un conjunto de bordes ponderados. Un bordee(u, v) representa esos vértices u y vestan conectados. Distancia entre vérticesu y v es d(u, v), que no debe ser negativo.

Supongamos que hemos comenzado en la ciudad 1 y después de visitar algunas ciudades ahora estamos en la ciudad j. Por lo tanto, este es un recorrido parcial. Ciertamente necesitamos saberj, ya que esto determinará qué ciudades son las más convenientes para visitar a continuación. También necesitamos conocer todas las ciudades visitadas hasta ahora, para no repetir ninguna de ellas. Por tanto, este es un subproblema apropiado.

Para un subconjunto de ciudades S Є {1, 2, 3, ... , n} eso incluye 1y j Є S, dejar C(S, j) ser la longitud de la ruta más corta que visita cada nodo en S exactamente una vez, comenzando en 1 y termina en j.

Cuando |S| > 1, definimosC(S, 1) = ∝ ya que la ruta no puede comenzar y terminar en 1.

Ahora, expresemos C(S, j)en términos de subproblemas más pequeños. Tenemos que empezar en1 y terminar en j. Debemos seleccionar la siguiente ciudad de tal manera que

$$ C (S, j) = min \: C (S - \ lbrace j \ rbrace, i) + d (i, j) \: donde \: i \ en S \: y \: i \ neq jc ( S, j) = minC (s- \ lbrace j \ rbrace, i) + d (i, j) \: donde \: i \ en S \: y \: i \ neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Análisis

Hay como máximo $ 2 ^ nn $ subproblemas y cada uno requiere un tiempo lineal para resolverlo. Por lo tanto, el tiempo total de ejecución es $ O (2 ^ nn ^ 2) $.

Ejemplo

En el siguiente ejemplo, ilustraremos los pasos para resolver el problema del viajante.

A partir del gráfico anterior, se prepara la siguiente tabla.

S = Φ

$$ \ Costo pequeño (2, \ Phi, 1) = d (2,1) = 5 \ Costo pequeño (2, \ Phi, 1) = d (2,1) = 5 $$

$$ \ Costo pequeño (3, \ Phi, 1) = d (3,1) = 6 \ Costo pequeño (3, \ Phi, 1) = d (3,1) = 6 $$

$$ \ Costo pequeño (4, \ Phi, 1) = d (4,1) = 8 \ Costo pequeño (4, \ Phi, 1) = d (4,1) = 8 $$

S = 1

$$ \ small Cost (i, s) = min \ lbrace Cost (j, s - (j)) + d [i, j] \ rbrace \ small Cost (i, s) = min \ lbrace Cost (j, s ) - (j)) + d [i, j] \ rbrace $$

$$ \ small Cost (2, \ lbrace 3 \ rbrace, 1) = d [2,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15cost (2, \ lbrace3 \ rbrace, 1) = d [2,3] + costo (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small Cost (2, \ lbrace 4 \ rbrace, 1) = d [2,4] + Cost (4, \ Phi, 1) = 10 + 8 = 18cost (2, \ lbrace4 \ rbrace, 1) = d [2,4] + costo (4, \ Phi, 1) = 10 + 8 = 18 $$

$$ \ small Cost (3, \ lbrace 2 \ rbrace, 1) = d [3,2] + Cost (2, \ Phi, 1) = 13 + 5 = 18cost (3, \ lbrace2 \ rbrace, 1) = d [3,2] + costo (2, \ Phi, 1) = 13 + 5 = 18 $$

$$ \ small Cost (3, \ lbrace 4 \ rbrace, 1) = d [3,4] + Cost (4, \ Phi, 1) = 12 + 8 = 20cost (3, \ lbrace4 \ rbrace, 1) = d [3,4] + costo (4, \ Phi, 1) = 12 + 8 = 20 $$

$$ \ small Cost (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15cost (4, \ lbrace3 \ rbrace, 1) = d [4,3] + costo (3, \ Phi, 1) = 9 + 6 = 15 $$

$$ \ small Cost (4, \ lbrace 2 \ rbrace, 1) = d [4,2] + Cost (2, \ Phi, 1) = 8 + 5 = 13cost (4, \ lbrace2 \ rbrace, 1) = d [4,2] + costo (2, \ Phi, 1) = 8 + 5 = 13 $$

S = 2

$$ \ small Cost (2, \ lbrace 3, 4 \ rbrace, 1) = \ begin {cases} d [2, 3] + Cost (3, \ lbrace 4 \ rbrace, 1) = 9 + 20 = 29 \ \ d [2, 4] + Costo (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 = 25 \ small Cost (2, \ lbrace 3,4 \ rbrace, 1) \\\ lbrace d [ 2,3] + \ small cost (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ small Cost (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 \ end {casos} = 25 $$

$$ \ small Cost (3, \ lbrace 2, 4 \ rbrace, 1) = \ begin {cases} d [3, 2] + Cost (2, \ lbrace 4 \ rbrace, 1) = 13 + 18 = 31 \ \ d [3, 4] + Costo (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 = 25 \ small Cost (3, \ lbrace 2,4 \ rbrace, 1) \\\ lbrace d [ 3,2] + \ small cost (2, \ lbrace4 \ rbrace, 1) = 13 + 18 = 31d [3,4] + \ small Cost (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 \ end {casos} = 25 $$

$$ \ small Cost (4, \ lbrace 2, 3 \ rbrace, 1) = \ begin {cases} d [4, 2] + Cost (2, \ lbrace 3 \ rbrace, 1) = 8 + 15 = 23 \ \ d [4, 3] + Costo (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 = 23 \ small Cost (4, \ lbrace 2,3 \ rbrace, 1) \\\ lbrace d [ 4,2] + \ small cost (2, \ lbrace3 \ rbrace, 1) = 8 + 15 = 23d [4,3] + \ small Cost (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 \ end {casos} = 23 $$

S = 3

$$ \ small Cost (1, \ lbrace 2, 3, 4 \ rbrace, 1) = \ begin {cases} d [1, 2] + Cost (2, \ lbrace 3, 4 \ rbrace, 1) = 10 + 25 = 35 \\ d [1, 3] + Costo (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + Costo (4, \ lbrace 2, 3 \ rbrace, 1) = 20 + 23 = 43 = 35 cost (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + cost (2, \ lbrace 3,4 \ rbrace , 1) = 10 + 25 = 35 \\ d [1,3] + costo (3, \ lbrace 2,4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1,4] + costo (4 , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ end {cases} $$

La ruta de costo mínimo es 35.

Comience desde el costo {1, {2, 3, 4}, 1}, obtenemos el valor mínimo para d [1, 2]. Cuandos = 3, seleccione la ruta de 1 a 2 (el costo es 10) y luego retroceda. Cuandos = 2, obtenemos el valor mínimo para d [4, 2]. Seleccione la ruta de 2 a 4 (el costo es 10) y luego retroceda.

Cuando s = 1, obtenemos el valor mínimo para d [4, 3]. Seleccionando la ruta 4 a 3 (el costo es 9), luego iremos a luego iremos as = Φpaso. Obtenemos el valor mínimo parad [3, 1] (el costo es 6).