Problema do caixeiro viajante: Python, C++ Algoritmo

Qual é o problema do caixeiro viajante (TSP)?

O Problema do Caixeiro Viajante (TSP) é um problema combinatório clássico da ciência da computação teórica. O problema pede para encontrar o caminho mais curto em um grafo com a condição de visitar todos os nós apenas uma vez e retornar à cidade de origem.

A definição do problema fornece uma lista de cidades junto com as distâncias entre cada cidade.

Objetivo: Para começar na cidade de origem, visite outras cidades apenas uma vez e retorne à cidade original novamente. Nosso objetivo é encontrar o caminho mais curto possível para completar a rota de ida e volta.

Exemplo de TSP

Aqui é fornecido um gráfico onde 1, 2, 3 e 4 representam as cidades, e o peso associado a cada aresta representa a distância entre essas cidades.

O objetivo é encontrar o caminho mais curto possível para o passeio que começa na cidade de origem, percorre o grafo visitando apenas uma vez as outras cidades ou nós e retorna à cidade de origem.

Para o gráfico acima, a rota ideal é seguir o caminho de custo mínimo: 1-2-4-3-1. E esse caminho mais curto custaria 10+25+30+15 =80

Diferentes soluções para o problema do caixeiro viajante

O Problema do Caixeiro Viajante (TSP) é classificado como um problema NP-difícil por não possuir algoritmo de tempo polinomial. A complexidade aumenta exponencialmente com o aumento do número de cidades.

Existem várias maneiras de resolver o problema do caixeiro viajante (tsp). Algumas soluções populares são:

A abordagem da força bruta é o método ingênuo para resolver problemas do caixeiro viajante. Nesta abordagem, primeiro calculamos todos os caminhos possíveis e depois os comparamos. O número de caminhos em um grafo que consiste em n cidades é n! É computacionalmente muito caro resolver o problema do caixeiro viajante nesta abordagem de força bruta.

O método branch-and-bound: O problema é dividido em subproblemas nesta abordagem. A solução desses subproblemas individuais forneceria uma solução ótima.

Este tutorial demonstrará uma abordagem de programação dinâmica, a versão recursiva deste método branch-and-bound, para resolver o problema do caixeiro viajante.

Programaçao dinamica é um método para buscar soluções ótimas analisando todas as rotas possíveis. É um dos métodos de solução exatos que resolvem os problemas do caixeiro viajante através de um custo relativamente mais elevado do que o métodos gananciosos que fornecem uma solução quase ideal.

A complexidade computacional desta abordagem é SOBRE(N^2 * 2^N) que é discutido posteriormente neste artigo.

O método do vizinho mais próximo é uma abordagem gananciosa baseada em heurística onde escolhemos o nó vizinho mais próximo. Esta abordagem é computacionalmente mais barata que a abordagem dinâmica. Mas não oferece a garantia de uma solução ótima. Este método é usado para soluções quase ótimas.

Algoritmo para o problema do caixeiro viajante

Usaremos a abordagem de programação dinâmica para resolver o Problema do Caixeiro Viajante (TSP).

Antes de iniciar o algoritmo, vamos conhecer algumas terminologias:

• Um gráfico G=(V, E), que é 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 dois vértices, i e j.

Vamos supor que S seja o subconjunto de cidades e pertença a {1, 2, 3,…, n} onde 1, 2, 3…n são as cidades e i, j são duas cidades nesse subconjunto. Agora cost(i, S, j) é definido de tal forma como o comprimento do caminho mais curto que visita o nó em S, que tem exatamente uma vez o ponto inicial e final como i e j, respectivamente.

Por exemplo, custo (1, {2, 3, 4}, 1) denota o comprimento do caminho mais curto onde:

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

O algoritmo de programação dinâmica seria:

• Defina cost(i, , i) = 0, o que significa que começamos e terminamos em i, e o custo é 0.
• Quando |S| > 1, definimos cost(i, S, 1) = ∝ onde i !=1 . Porque inicialmente não sabemos o custo exato para chegar da cidade i à cidade 1 através de outras cidades.
• Agora, precisamos começar em 1 e completar o tour. Precisamos selecionar a próxima cidade de tal maneira-

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

Para a figura dada, a matriz de adjacência seria a seguinte:

dist(eu,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

Vamos ver como nosso algoritmo funciona:

Passo 1) Estamos considerando nossa jornada começando na cidade 1, visitar outras cidades uma vez e retornar à cidade 1.

Passo 2) S é o subconjunto de cidades. De acordo com nosso algoritmo, para todo |S| > 1, definiremos o custo da distância (i, S, 1) = ∝. Aqui cost(i, S, j) significa que estamos começando na cidade i, visitando as cidades de S uma vez, e agora estamos na cidade j. Definimos esse custo de caminho como infinito porque ainda não sabemos a distância. Então os valores serão os seguintes:

Custo (2, {3, 4}, 1) = ∝ ; a notação indica que estamos começando na cidade 2, passando pelas cidades 3, 4 e chegando a 1. E o custo do caminho é infinito. De forma similar-

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

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

Passo 3) Agora, para todos os subconjuntos de S, precisamos encontrar o seguinte:

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

Isso significa o caminho de custo mínimo para começar em i, passar uma vez pelo subconjunto de cidades e retornar à cidade j. Considerando que a viagem começa na cidade 1, o custo ótimo do caminho seria = custo(1, {outras cidades}, 1).

Vamos descobrir como poderíamos conseguir isso:

Agora S = {1, 2, 3, 4}. Existem quatro elementos. Portanto, o número de subconjuntos será 2 ^ 4 ou 16. Esses subconjuntos são-

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 estamos começando em 1, poderíamos descartar os subconjuntos que contêm a cidade 1.

O cálculo do algoritmo:

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

Então a solução ótima seria 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 Є 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) 

Implementação em C/C++

Aqui está a implementação em 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;
}

Saída:

80

Implementação em 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))

Saída:

80

Soluções Acadêmicas para TSP

Os cientistas da computação passaram anos procurando um algoritmo de tempo polinomial aprimorado para o Problema do Caixeiro Viajante. Até agora, o problema ainda é NP-difícil.

Embora algumas das seguintes soluções tenham sido publicadas nos últimos anos, reduziram a complexidade até certo ponto:

• O TSP simétrico clássico é resolvido pelo Método do Sufixo Zero.
• O Algoritmo de Otimização Baseado em Biogeografia baseia-se na estratégia de migração para resolver os problemas de otimização que podem ser planejados como TSP.
• O algoritmo evolutivo multiobjetivo foi projetado para resolver vários TSP baseados em NSGA-II.
• O Sistema Multiagente resolve o TSP de N cidades com recursos fixos.

Aplicação do problema do caixeiro viajante

O Problema do Caixeiro Viajante (TSP) é aplicado no mundo real tanto em sua forma mais pura quanto modificada. Alguns deles são:

• Planejamento, logística e fabricação de microchips: Problemas de inserção de chips surgem naturalmente na indústria de microchips. Esses problemas podem ser planejados como problemas do caixeiro viajante.
• A sequenciação de ADN: Uma ligeira modificação do problema do caixeiro viajante pode ser usada no sequenciamento de DNA. Aqui, as cidades representam os fragmentos de DNA e a distância representa a medida de similaridade entre dois fragmentos de DNA.
• Astronomia: O Problema do Caixeiro Viajante é aplicado por astrônomos para minimizar o tempo gasto na observação de várias fontes.
• Problema de controle ideal: A formulação do problema do caixeiro viajante pode ser aplicada em problemas de controle ótimo. Pode haver várias outras restrições adicionadas.

Análise de Complexidade do TSP

• Complexidade de tempo: Há um total de 2^N subproblemas para cada nó. Portanto, o número total de subproblemas seria N*2^N. Cada um dos subproblemas requer tempo linear para ser resolvido. Se o nó de origem não for especificado, teremos que executar loops para N nós.

  Portanto, a complexidade de tempo total para uma solução ideal seria o Número de nós * Número de subproblemas * tempo para resolver cada subproblema. A complexidade do tempo pode ser definida como O(N² * 2^N).

• Complexidade do espaço: A abordagem de programação dinâmica usa memória para armazenar C(S, i), onde S é um subconjunto do conjunto de vértices. Há um total de 2^N subconjuntos para cada nó. Portanto, a complexidade do espaço é O(2^N).

A seguir, você aprenderá sobre Algoritmo da Peneira de Eratóstenes