Problema del vendedor ambulante: Python, C++ Algoritmo

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

El problema del viajante (TSP, por sus siglas en inglés) es un problema clásico de optimización combinatoria en la informática teórica. Dado un grafo de ciudades, el TSP busca el camino más corto que visite cada nodo exactamente una vez y regrese a la ciudad de origen.

El enunciado del problema proporciona una lista de ciudades junto con las distancias entre cada par de ciudades.

Objetivo: Empieza en la ciudad de origen, visita todas las demás ciudades exactamente una vez y regresa a la ciudad de partida. El objetivo es encontrar la ruta de ida y vuelta más corta posible.

Ejemplo de TSP

Consideremos el gráfico que aparece a continuación, donde 1, 2, 3 y 4 representan las ciudades, y el peso de cada arista representa la distancia entre esas ciudades.

El objetivo es encontrar la ruta más corta posible que comience en la ciudad de origen, visite todas las demás ciudades exactamente una vez y regrese a la ciudad de origen.

Para el gráfico anterior, la ruta óptima es 1-2-4-3-1. El costo del tour más corto es 10 + 25 + 30 + 15 = 80.

Diferentes soluciones al problema del viajante

El problema del viajante se clasifica como NP-difícil porque no existe ningún algoritmo conocido de tiempo polinomial que lo resuelva exactamente. La complejidad aumenta exponencialmente con el número de ciudades.

Existen múltiples formas de abordar el problema del viajante. Los enfoques más comunes son:

Enfoque de fuerza bruta: El método ingenuo calcula todos los recorridos posibles y los compara. El número de recorridos en un grafo con n ciudades es n!, lo que hace que la fuerza bruta sea computacionalmente muy costosa para cualquier cosa que supere las diez ciudades aproximadamente.

Método de ramificación y acotación: El problema se divide en subproblemas, y las soluciones de estos subproblemas se combinan para formar una solución óptima. Una poda eficaz descarta los recorridos parciales que no pueden superar el mejor coste actual.

Este tutorial demuestra la enfoque de programación dinámica, que es la versión memorizada del método de ramificación y acotación y coincide con el algoritmo de Bellman-Held-Karp.

Programación dinámica: Este es un método exacto que busca la solución óptima mediante la reutilización de la superposición.ping resultados del subproblema. Es más lento que el casi óptimo. métodos codiciosospero siempre ofrece un recorrido óptimo a nivel global.

La complejidad computacional de este enfoque es O(N² × 2^N), tema que abordaremos más adelante en el artículo.

Método del vecino más cercano: Un enfoque heurístico voraz que siempre salta a la ciudad no visitada más cercana. Es mucho más económico que la programación dinámica, pero no garantiza un recorrido óptimo, por lo que se utiliza para soluciones casi óptimas cuando la velocidad es más importante que la obtención de mínimos exactos.

Algoritmo para el problema del viajante

Utilizamos el enfoque de programación dinámica para resolver el problema del viajante. Antes de comenzar con el algoritmo, aclaremos algunos términos:

• Un gráfico G = (V, E) 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 los vértices i y j.

Supongamos que S es un subconjunto de ciudades extraídas de {1, 2, 3, …, n}, donde i y j son dos ciudades de ese subconjunto. Entonces cost(i, S, j) es la longitud del camino más corto que comienza en i, visita cada ciudad en S exactamente una vez y termina en j.

Por ejemplo, cost(1, {2, 3, 4}, 1) denota el 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.

La recurrencia de la programación dinámica es:

• Establecer cost(i, {}, i) = 0, lo que significa que comenzamos y terminamos en i con costo cero.
• Cuando |S| > 1, definir cost(i, S, 1) = ∞ por la i ≠ 1, porque el coste real del tour aún se desconoce.
• Comenzando en la ciudad 1, elige la siguiente ciudad de modo que cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] por la i ∈ S y i ≠ j.

Para el gráfico anterior, la matriz de adyacencia es la siguiente:

Así es como procede el algoritmo:

Paso 1) El viaje comienza en la ciudad 1, visita todas las demás ciudades una vez y regresa a la ciudad 1.

Paso 2) S es un subconjunto de ciudades. Para cada |S| > 1, inicializar cost(i, S, 1) = ∞. aquí cost(i, S, j) denota un recorrido que comienza en i, visita las ciudades en S una vez y llega a j. Comenzamos desde el infinito porque la distancia es desconocida en este punto. Por lo tanto, los valores son:

cost(2, {3, 4}, 1) = ∞ significa que comenzamos en la ciudad 2, pasamos por las ciudades 3 y 4, y llegamos a la 1, con un costo desconocido. De manera similar:

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

Paso 3) Para cada subconjunto de S, calcule:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], donde j ∈ S y i ≠ j.

Ese es el recorrido de costo mínimo que comienza en i, visita el subconjunto de ciudades una vez y regresa a j. Debido a que el recorrido comienza en la ciudad 1, el costo óptimo es cost(1, {other cities}, 1).

Trabajar la recurrencia paso a paso

Ahora S = {1, 2, 3, 4}. Hay cuatro elementos, por lo que el número de subconjuntos es 2^4 = 16Esos subconjuntos son:

1) |S| = 0: {Φ}

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}}

Dado que el recorrido comienza en la ciudad 1, podemos descartar cualquier subconjunto que contenga la ciudad 1 al calcular los costos intermedios.

El cálculo del algoritmo se desarrolla de la siguiente manera:

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) = min [ 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) = min [ 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) = min [ 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

Por lo tanto, la solución óptima es 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 in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in 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++La versión que aparece a continuación corrige el error inicial del código fuente. return error, que se producía después de la primera permutación en lugar de enumerar todos los recorridos.

#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;
    do {
        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);
    } while (next_permutation(vertex.begin(), vertex.end()));

    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

El Python La implementación refleja la C++ versión. Corrige la fuente from itertools, import error tipográfico de coma, el mal colocado return dentro del bucle interior y la hendidura suelta en s = 0.

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
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            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 dedicado décadas a buscar algoritmos mejorados de tiempo polinomial para el problema del viajante. Hasta ahora, el problema del viajante sigue siendo NP-difícil.

Varias técnicas publicadas reducen la complejidad práctica para familias específicas de instancias del problema del viajante:

• El TSP simétrico clásico se resuelve mediante el Método del sufijo cero.
• El Algoritmo de optimización basado en biogeografía Utiliza estrategias de migración para resolver problemas de optimización que se corresponden con el problema del viajante.
• El Algoritmo evolutivo multiobjetivo Está diseñado para el problema del viajante multiobjetivo y se basa en NSGA-II.
• El Sistema Multi-Agente Este enfoque resuelve el problema del viajante para N ciudades con recursos computacionales fijos.
• El Heurística de Lin-Kernighan y su sucesor LKH Ofrecer recorridos con una precisión de entre el 2 % y el 3 % respecto al óptimo en casos con millones de ciudades.
• Concord Utiliza planos de corte y el método de ramificación y corte para calcular óptimos exactos para instancias de referencia con decenas de miles de ciudades.

Aplicación del problema del viajante

El problema del viajante se presenta en el mundo real tanto en su forma pura como modificada. Algunas de sus principales aplicaciones son:

• Planificación, logística y fabricación de microchips: Los problemas de inserción de chips en la industria de los microchips se modelan como variantes del problema del viajante para minimizar el tiempo de desplazamiento del brazo robótico.
• Secuencia ADN: En la secuenciación de ADN se utiliza un TSP modificado, donde las ciudades representan fragmentos de ADN y las distancias representan la similitud entre los fragmentos.
• Astronomía: Los astrónomos utilizan TSP para minimizar el tiempo que se tarda en mover los telescopios entre los objetivos de observación.
• Control óptimo: Las formulaciones del problema del viajante modelan problemas de control óptimo en los que se deben respetar múltiples restricciones al tiempo que se minimiza el coste de recorrido.
• Entrega de última milla: AmazonLas aplicaciones de reparto de comida, como UPS, resuelven variantes dinámicas del problema del viajante para secuenciar las paradas de los conductores.
• Picking en almacén: Los operarios, tanto robóticos como humanos, siguen rutas optimizadas mediante el algoritmo TSP que reducen el tiempo de desplazamiento dentro de los centros de distribución.

Análisis de complejidad de TSP

• Complejidad del tiempo: El enfoque de programación dinámica de Held-Karp resuelve 2^N subconjuntos para cada nodo inicial, dando N × 2^N subproblemas. Cada subproblema requiere un tiempo lineal para combinarse. Si el nodo de origen no está especificado, se requiere un bucle externo sobre N nodos. La complejidad temporal total es O(N² × 2^N).
• Complejidad espacial: La tabla DP almacena C(S, i) para cada subconjunto S del conjunto de vértices. Hay 2^N subconjuntos por nodo, por lo que la complejidad espacial es O(N × 2^N), que a menudo se escribe como O(2^N) cuando N se considera fijo.

A continuación, aprenda sobre el Algoritmo del tamiz de Eratóstenes.

Preguntas Frecuentes