Problema do caixeiro viajante: Python, C++ Algoritmo

Qual é o problema do caixeiro viajante (TSP)?

O Problema do Caixeiro Viajante (PCV) é um problema clássico de otimização combinatória em ciência da computação teórica. Dado um grafo de cidades, o PCV busca o caminho mais curto que visite cada nó exatamente uma vez e retorne à cidade de origem.

O enunciado do problema fornece uma lista de cidades juntamente com as distâncias entre cada par de cidades.

Objetivo: Comece na cidade de origem, visite cada uma das outras cidades exatamente uma vez e retorne à cidade inicial. O objetivo é encontrar a rota de ida e volta mais curta possível.

Exemplo de TSP

Considere o gráfico abaixo, onde 1, 2, 3 e 4 representam as cidades, e o peso em cada aresta representa a distância entre essas cidades.

O objetivo é encontrar o percurso mais curto possível que comece na cidade de origem, visite cada uma das outras cidades exatamente uma vez e retorne à cidade de origem.

Para o gráfico acima, a rota ideal é 1-2-4-3-1O custo do passeio mais curto é 10 + 25 + 30 + 15 = 80.

Diferentes soluções para o problema do caixeiro viajante

O Problema do Caixeiro Viajante é classificado como NP-difícil porque não existe nenhum algoritmo conhecido de tempo polinomial que o resolva exatamente. A complexidade cresce exponencialmente com o número de cidades.

Existem várias maneiras de atacar o TSP. As abordagens mais comuns são:

Abordagem de força bruta: O método ingênuo calcula todos os percursos possíveis e os compara. O número de percursos em um grafo com n cidades é n!, o que torna o uso da força bruta computacionalmente muito caro para qualquer coisa além de cerca de dez cidades.

Método Branch and Bound: O problema é dividido em subproblemas, e as soluções desses subproblemas se combinam para formar uma solução ótima. Uma poda eficaz descarta percursos parciais que não conseguem superar o melhor custo atual.

Este tutorial demonstra o abordagem de programação dinâmica, que é a versão memorizada do algoritmo branch and bound e corresponde ao algoritmo de Bellman-Held-Karp.

Programaçao dinamica: Este é um método exato que busca a solução ótima reutilizando a sobreposição.ping resultados do subproblema. É mais lento do que o quase ótimo métodos gananciosos, mas sempre retorna um percurso globalmente ótimo.

A complexidade computacional desta abordagem é O(N² × 2^N), que abordaremos mais adiante neste artigo.

Método do Vizinho Mais Próximo: Uma abordagem heurística gulosa que sempre salta para a cidade não visitada mais próxima. É muito mais barata que a programação dinâmica, mas não garante um percurso ótimo, sendo utilizada para soluções quase ótimas quando a velocidade é mais importante do que mínimos exatos.

Algoritmo para o problema do caixeiro viajante

Utilizamos a abordagem de programação dinâmica para resolver o TSP. Antes de iniciar o algoritmo, vamos esclarecer alguns termos:

• Um gráfico G = (V, E) é um conjunto de vértices e arestas.
• V é o conjunto de vértices.
• E é o conjunto de arestas.
• Os vértices são conectados por meio de arestas.
• Dist(i, j) denota a distância não negativa entre os vértices i e j.

Suponha que S seja um subconjunto de cidades extraídas de {1, 2, 3, …, n}, onde i e j são duas cidades nesse subconjunto. Então cost(i, S, j) é o comprimento do caminho mais curto que começa em i, visita cada cidade em S exatamente uma vez e termina em j.

Por exemplo, nos cost(1, {2, 3, 4}, 1) denota o caminho mais curto onde:

• A cidade inicial é 1
• As cidades 2, 3 e 4 são visitadas apenas uma vez
• O ponto final é 1

A recorrência da programação dinâmica é:

• Conjunto cost(i, {}, i) = 0, o que significa que começamos e terminamos em i com custo zero.
• Ao |S| > 1, definir cost(i, S, 1) = ∞ pela i ≠ 1, porque o custo real da excursão ainda é desconhecido.
• Começando pela cidade 1, escolha a próxima cidade de forma que cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] pela i ∈ S e i ≠ j.

Para o grafo acima, a matriz de adjacência é a seguinte:

Eis como o algoritmo funciona:

Passo 1) A jornada começa na cidade 1, visita cada uma das outras cidades uma vez e retorna à cidade 1.

Passo 2) S é um subconjunto de cidades. Para todo |S| > 1, inicialize cost(i, S, 1) = ∞. Aqui cost(i, S, j) denota um percurso que começa em i, visita as cidades em S uma vez e chega a j. Começamos do infinito porque a distância é desconhecida neste ponto. Portanto, os valores são:

cost(2, {3, 4}, 1) = ∞ Significa que começamos na cidade 2, passamos pelas cidades 3 e 4 e chegamos à cidade 1, com custo desconhecido. Da mesma forma:

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

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

Passo 3) Para cada subconjunto de S, calcule:

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

Essa é a rota de custo mínimo que começa em i, visita o subconjunto de cidades uma vez e retorna a j. Como a rota começa na cidade 1, o custo ótimo é cost(1, {other cities}, 1).

Trabalhando com a recorrência passo a passo

Agora, S = {1, 2, 3, 4}. Há quatro elementos, então o número de subconjuntos é 2^4 = 16Esses subconjuntos são:

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

Como o passeio começa na cidade 1, podemos descartar todos os subconjuntos que contêm a cidade 1 ao calcular os custos intermediários.

O cálculo do algoritmo se desenrola da seguinte forma:

1) |S| =Φ:

• custo(2, Φ, 1) = dist(2, 1) = 10
• custo(3, Φ, 1) = dist(3, 1) = 15
• custo(4, Φ, 1) = dist(4, 1) = 20

2) |S| = 1:

• custo(2, {3}, 1) = dist(2, 3) + custo(3, Φ, 1) = 35 + 15 = 50
• custo(2, {4}, 1) = dist(2, 4) + custo(4, Φ, 1) = 25 + 20 = 45
• custo(3, {2}, 1) = dist(3, 2) + custo(2, Φ, 1) = 35 + 10 = 45
• custo(3, {4}, 1) = dist(3, 4) + custo(4, Φ, 1) = 30 + 20 = 50
• custo(4, {2}, 1) = dist(4, 2) + custo(2, Φ, 1) = 25 + 10 = 35
• custo(4, {3}, 1) = dist(4, 3) + custo(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2:

• custo(2, {3, 4}, 1) = min [ dist(2, 3) + custo(3, {4}, 1) = 35 + 50 = 85, dist(2, 4) + custo(4, {3}, 1) = 25 + 45 = 70 ] = 70
• custo(3, {2, 4}, 1) = min [ dist(3, 2) + custo(2, {4}, 1) = 35 + 45 = 80, dist(3, 4) + custo(4, {2}, 1) = 30 + 35 = 65 ] = 65
• custo(4, {2, 3}, 1) = min [ dist(4, 2) + custo(2, {3}, 1) = 25 + 50 = 75, dist(4, 3) + custo(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |S| = 3:

• custo(1, {2, 3, 4}, 1) = min [ dist(1, 2) + custo(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + custo(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + custo(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80

Portanto, a solução ótima é 1-2-4-3-1.

Pseudo-có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)

Implementação em C/C++

Aqui está a implementação em C++A versão abaixo corrige o problema inicial do código-fonte. return bug, que retornava após a primeira permutação em vez de enumerar todos os percursos.

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

Saída:

80

Implementação em Python

O Python A implementação espelha a C++ versão. Corrige a fonte from itertools, import vírgula mal colocada, return dentro do laço interno e a reentrância perdida em 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))

Saída:

80

Soluções Acadêmicas para TSP

Cientistas da computação têm dedicado décadas à busca de algoritmos de tempo polinomial aprimorados para o Problema do Caixeiro Viajante. Até o momento, o TSP permanece NP-difícil.

Diversas técnicas publicadas reduzem a complexidade prática para famílias específicas de instâncias do Problema do Caixeiro Viajante (TSP):

• O problema clássico do caixeiro viajante simétrico é resolvido pelo Método do sufixo zero.
• O Algoritmo de otimização baseado em biogeografia Utiliza estratégias de migração para resolver problemas de otimização que se assemelham ao TSP.
• O Algoritmo Evolutivo Multiobjetivo Foi projetado para o TSP com múltiplos objetivos e se baseia no NSGA-II.
• O Sistema multiagente Essa abordagem resolve o problema do caixeiro viajante (TSP) para N cidades com recursos computacionais fixos.
• O Heurística de Lin-Kernighan e seu sucessor LKH Realizar visitas guiadas com uma precisão de 2 a 3% em casos envolvendo milhões de cidades.
• concórdia Utiliza planos de corte e o método branch-and-cut para calcular os ótimos exatos em instâncias de referência com dezenas de milhares de cidades.

Aplicação do problema do caixeiro viajante

O Problema do Caixeiro Viajante aparece no mundo real tanto em sua forma pura quanto modificada. Algumas das principais aplicações são:

• Planejamento, logística e fabricação de microchips: Os problemas de inserção de chips na indústria de microchips são modelados como variantes do Problema do Caixeiro Viajante (TSP) para minimizar o tempo de deslocamento do braço robótico.
• Sequenciamento de DNA: Um TSP modificado é usado no sequenciamento de DNA, onde as cidades representam fragmentos de DNA e as distâncias representam a similaridade entre os fragmentos.
• Astronomia: Os astrônomos usam o TSP para minimizar o tempo gasto movimentando telescópios entre alvos de observação.
• Controle ótimo: As formulações do TSP modelam problemas de controle ótimo onde múltiplas restrições devem ser respeitadas, minimizando-se o custo de percurso.
• Entrega de última milha: AmazonAplicativos da UPS e de entrega de comida resolvem variantes dinâmicas do Problema do Caixeiro Viajante (TSP) para sequenciar paradas para motoristas.
• Separação em armazém: Robôs e operadores humanos realizam a coleta de itens seguindo rotas otimizadas pelo algoritmo TSP (Três Pontos de Encontro), o que reduz o tempo de deslocamento dentro dos centros de distribuição.

Análise de Complexidade do TSP

• Complexidade de tempo: A abordagem de programação dinâmica de Held-Karp resolve 2^N subconjuntos para cada nó inicial, resultando em N × 2^N subproblemas. Cada subproblema leva tempo linear para ser combinado. Se o nó de origem não for especificado, um loop externo sobre N nós é necessário. A complexidade de tempo total é O(N² × 2^N).
• Complexidade do espaço: A tabela DP armazena C(S, i) Para cada subconjunto S do conjunto de vértices. Existem 2^N subconjuntos por nó, portanto a complexidade espacial é O(N × 2^N), que geralmente é escrito como O(2^N) quando N é tratado como fixo.

Em seguida, aprenda sobre o Algoritmo da Peneira de Eratóstenes.

Perguntas Frequentes