Problema del vendedor ambulante: Python, C++ Algoritmo

¿Qué es el problema del viajante (TSP)?

El problema del viajante (TSP) es un problema combinatorio clásico de la informática teórica. El problema pide encontrar el camino más corto en un gráfico con la condición de visitar todos los nodos una sola vez y regresar a la ciudad de origen.

El planteamiento del problema proporciona una lista de ciudades junto con las distancias entre cada ciudad.

Objetivo: Para comenzar desde la ciudad de origen, visite otras ciudades solo una vez y regrese a la ciudad original nuevamente. Nuestro objetivo es encontrar el camino más corto posible para completar la ruta de ida y vuelta.

Ejemplo de TSP

Aquí se proporciona un gráfico donde 1, 2, 3 y 4 representan las ciudades, y el peso asociado con cada borde representa la distancia entre esas ciudades.

El objetivo es encontrar el camino más corto posible para el recorrido que comienza desde la ciudad de origen, atraviesa el gráfico visitando las otras ciudades o nodos solo una vez y regresa a la ciudad de origen.

Para el gráfico anterior, la ruta óptima es seguir la ruta de costo mínimo: 1-2-4-3-1. Y esta ruta más corta costaría 10+25+30+15 =80

Diferentes soluciones al problema del viajante

El problema del viajante de comercio (TSP) se clasifica como un problema NP-hard debido a que no tiene un algoritmo de tiempo polinomial. La complejidad aumenta exponencialmente al aumentar el número de ciudades.

Hay varias formas de resolver el problema del viajante (cucharadita). Algunas soluciones populares son:

El enfoque de la fuerza bruta es el método ingenuo. para resolver problemas de vendedores ambulantes. En este enfoque, primero calculamos todos los caminos posibles y luego los comparamos. El número de caminos en un gráfico que consta de n ciudades es n! Es computacionalmente muy costoso resolver el problema del viajante con este enfoque de fuerza bruta.

El método de ramificación y encuadernación: En este enfoque, el problema se divide en subproblemas. La solución de esos subproblemas individuales proporcionaría una solución óptima.

Este tutorial demostrará un enfoque de programación dinámica, la versión recursiva de este método de ramificación y vinculación, para resolver el problema del viajante.

Programación dinámica es un método de este tipo para buscar soluciones óptimas analizando todas las rutas posibles. Es uno de los métodos de solución exactos que resuelven los problemas de los vendedores ambulantes a un costo relativamente más alto que el métodos codiciosos que proporcionan una solución casi óptima.

La complejidad computacional de este enfoque es O(norte^2 * 2^norte) que se analiza más adelante en este artículo.

El método del vecino más cercano es un enfoque voraz basado en heurísticas en el que elegimos el nodo vecino más cercano. Este enfoque es computacionalmente menos costoso que el enfoque dinámico, pero no ofrece la garantía de una solución óptima. Este método se utiliza para soluciones casi óptimas.

Algoritmo para el problema del viajante

Utilizaremos el enfoque de programación dinámica para resolver el problema del viajante (TSP).

Antes de comenzar con el algoritmo, familiaricémonos con algunas terminologías:

• Un gráfico G=(V, E), que es un conjunto de vértices y aristas.
• V es el conjunto de vértices.
• E es el conjunto de aristas.
• Los vértices están conectados a través de aristas.
• Dist(i,j) denota la distancia no negativa entre dos vértices, i y j.

Supongamos que S es el subconjunto de ciudades y pertenece a {1, 2, 3,…, n} donde 1, 2, 3…n son las ciudades e i, j son dos ciudades en ese subconjunto. Ahora el costo (i, S, j) se define de tal manera como la longitud del camino más corto que visita el nodo en S, que tiene exactamente una vez el punto inicial y final como i y j respectivamente.

Por ejemplo, el costo (1, {2, 3, 4}, 1) denota la longitud del camino más corto donde:

• La ciudad inicial es 1.
• Las ciudades 2, 3 y 4 se visitan solo una vez
• El punto final es 1.

El algoritmo de programación dinámica sería:

• Establezca el costo (i, , i) = 0, lo que significa que comenzamos y terminamos en i, y el costo es 0.
• Cuando |S| > 1, definimos costo(i, S, 1) = ∝ donde i !=1 . Porque inicialmente, no sabemos el costo exacto para llegar de la ciudad i a la ciudad 1 a través de otras ciudades.
• Ahora debemos comenzar en 1 y completar el recorrido. Necesitamos seleccionar la siguiente ciudad de tal manera:

costo(i, S, j)=costo mínimo (i, S−{i}, j)+dist(i,j) donde i∈S e i≠j

Para la figura dada, la matriz de adyacencia sería la siguiente:

dist(yo,j)	1	2	3	4
1	0	10	15	20
2	10	0	35	25
3	15	35	0	30
4	20	25	30	0

Veamos cómo funciona nuestro algoritmo:

Paso 1) Estamos considerando nuestro viaje comenzando en la ciudad 1, visitar otras ciudades una vez y regresar a la ciudad 1.

Paso 2) S es el subconjunto de ciudades. Según nuestro algoritmo, para todo |S| > 1, fijaremos el coste de distancia (i, S, 1) = ∝. Aquí, coste (i, S, j) significa que empezamos en la ciudad i, visitamos las ciudades de S una vez y ahora estamos en la ciudad j. Fijamos este coste de ruta como infinito porque aún no conocemos la distancia. Por tanto, los valores serán los siguientes:

Costo (2, {3, 4}, 1) = ∝ ; la notación indica que comenzamos en la ciudad 2, pasamos por las ciudades 3, 4 y llegamos a 1. Y el costo del camino es infinito. Similarmente-

costo(3, {2, 4}, 1) = ∝

costo(4, {2, 3}, 1) = ∝

Paso 3) Ahora, para todos los subconjuntos de S, necesitamos encontrar lo siguiente:

costo(i, S, j)=costo mínimo (i, S−{i}, j)+dist(i,j), donde j∈S e i≠j

Eso significa la ruta de costo mínimo para comenzar en i, pasar por el subconjunto de ciudades una vez y regresar a la ciudad j. Considerando que el viaje comienza en la ciudad 1, el costo óptimo del camino sería = costo(1, {otras ciudades}, 1).

Averigüemos cómo podríamos lograrlo:

Ahora S = {1, 2, 3, 4}. Hay cuatro elementos. Por lo tanto, el número de subconjuntos será 2 ^ 4 o 16. Esos subconjuntos son:

1) |S| = Nulo:

{Φ}

2) |S| = 1:

{{1}, {2}, {3}, {4}}

3) |S| = 2:

{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

4) |S| = 3:

{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}

5) |S| = 4:

{{1, 2, 3, 4}}

Como comenzamos en 1, podríamos descartar los subconjuntos que contienen la ciudad 1.

El cálculo del algoritmo:

1) |S| =Φ:

costo (2, Φ, 1) = dist(2, 1) = 10

costo (3, Φ, 1) = dist(3, 1) = 15

costo (4, Φ, 1) = dist(4, 1) = 20

2) |S| = 1:

costo (2, {3}, 1) = dist(2, 3) + costo (3, Φ, 1) = 35+15 = 50

costo (2, {4}, 1) = dist(2, 4) + costo (4, Φ, 1) = 25+20 = 45

costo (3, {2}, 1) = dist(3, 2) + costo (2, Φ, 1) = 35+10 = 45

costo (3, {4}, 1) = dist(3, 4) + costo (4, Φ, 1) = 30+20 = 50

costo (4, {2}, 1) = dist(4, 2) + costo (2, Φ, 1) = 25+10 = 35

costo (4, {3}, 1) = dist(4, 3) + costo (3, Φ, 1) = 30+15 = 45

3) |S| = 2:

costo (2, {3, 4}, 1) = mínimo [ dist[2,3]+Costo(3,{4},1) = 35+50 = 85,

dist[2,4]+Costo(4,{3},1) = 25+45 = 70 ] = 70

costo (3, {2, 4}, 1) = mínimo [ dist[3,2]+Costo(2,{4},1) = 35+45 = 80,

dist[3,4]+Costo(4,{2},1) = 30+35 = 65 ] = 65

costo (4, {2, 3}, 1) = mínimo [ dist[4,2]+Costo(2,{3},1) = 25+50 = 75

dist[4,3]+Costo(3,{2},1) = 30+45 = 75 ] = 75

4) |S| = 3:

costo (1, {2, 3, 4}, 1) = min [ dist[1,2]+Costo(2,{3,4},1) = 10+70 = 80

dist[1,3]+Costo(3,{2,4},1) = 15+65 = 80

dist[1,4]+Costo(4,{2,3},1) = 20+75 = 95 ] = 80

Entonces la solución óptima sería 1-2-4-3-1

Pseudocódigo

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

Implantación en C/C++

Aquí está la implementación en C++:

#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000
int tsp(int graph[][V], int s)
{
    vector<int> vertex;
    for (int i = 0; i < V; i++)
        if (i != s)
            vertex.push_back(i);
    int min_cost = MAX;
    while(next_permutation(vertex.begin(), vertex.end()))
     {
        int current_cost = 0;
        int j = s;
        for (int i = 0; i < vertex.size(); i++) {
            current_cost += graph[j][vertex[i]];
            j = vertex[i];
        }
        current_cost += graph[j][s];
        min_cost = min(min_cost, current_cost);
        return min_cost;
	}
}
int main()
{
    int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } };                      
    int s = 0;
    cout << tsp(graph, s) << endl;
    return 0;
}

Salida:

80

Implementación en Python

from sys import maxsize
from itertools, import permutations
V = 4
def tsp(graph, s):
	vertex = []
	for i in range(V):
		if i != s:
			vertex.append(i)
    min_cost = maxsize
	next_permutation=permutations(vertex)
	for i in next_permutation:
		current_cost = 0
		k = s
		for j in i:
			current_cost += graph[k][j]
			k = j
		current_cost += graph[k][s]
		min_cost = min(min_cost, current_cost)
		return min_cost
graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
		s = 0
print(tsp(graph, s))

Salida:

80

Soluciones académicas para TSP

Los informáticos han pasado años buscando un algoritmo de tiempo polinómico mejorado para el problema del viajante. Hasta ahora, el problema sigue siendo NP-hard.

Aunque en los últimos años se han publicado algunas de las siguientes soluciones que han reducido la complejidad hasta cierto punto:

• El TSP simétrico clásico se resuelve mediante el método del sufijo cero.
• El Algoritmo de Optimización basado en Biogeografía se basa en la estrategia de migración para resolver los problemas de optimización que se pueden planificar como TSP.
• El algoritmo evolutivo multiobjetivo está diseñado para resolver múltiples TSP basados ​​en NSGA-II.
• El Sistema Multi-Agente resuelve el TSP de N ciudades con recursos fijos.

Aplicación del problema del viajante

El problema del viajante (TSP) se aplica en el mundo real tanto en su forma más pura como modificada. Algunos de ellos son:

• Planificación, logística y fabricación de microchips.: Los problemas de inserción de chips surgen naturalmente en la industria de los microchips. Esos problemas pueden planificarse como problemas de viajante de comercio.
• secuencia ADN: Se puede utilizar una ligera modificación del problema del viajante en la secuenciación del ADN. Aquí, las ciudades representan los fragmentos de ADN y la distancia representa la medida de similitud entre dos fragmentos de ADN.
• AstronomíaLos astrónomos aplican el problema del viajante para minimizar el tiempo empleado en observar diversas fuentes.
• Problema de control óptimo: La formulación del problema del viajante se puede aplicar en problemas de control óptimo. Es posible que se agreguen varias otras restricciones.

Análisis de complejidad de TSP

• Complejidad del tiempo: Hay un total de 2^N subproblemas para cada nodo. Entonces el número total de subproblemas sería N*2^N. Cada uno de los subproblemas requiere un tiempo lineal para resolverse. Si no se especifica el nodo de origen, tenemos que ejecutar bucles para N nodos.

  Por lo tanto, la complejidad temporal total para una solución óptima sería la cantidad de nodos * cantidad de subproblemas * tiempo para resolver cada subproblema. La complejidad temporal se puede definir como O(N² * 2^N).

• Complejidad espacial: El enfoque de programación dinámica utiliza memoria para almacenar C(S, i), donde S es un subconjunto del conjunto de vértices. hay un total de 2^N subconjuntos para cada nodo. Por lo tanto, la complejidad espacial es O(2^N).

A continuación, aprenderá sobre Algoritmo del tamiz de Eratóstenes