Problema do Caixeiro Viajante¶
Introdução¶
O Problema do Caixeiro Viajante (CVP) é um problema considerado computacionalmente dificil de ser resolvido, isso é, pertence a classe de problemas NP-Difícil. Nesse problema, temos como objetivo encontrar o menor caminho para percorrer uma série de pontos (e. g. cidades em um mapa, vértices em um grafo) e retornar a posição inicial. Assim, o objetivo desse trabalho é apresentar e comparar diferentes abordagens para a resolução desse problema.
# Importando bibliotecas
from time import time
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
# Funcões auxiliares
def read_matrix_file(file):
with open(file) as matrix_file:
matrix = [list(map(int, line.split())) for line in matrix_file]
return matrix
def show_graph(matrix, draw_edges=False):
G = nx.from_numpy_matrix(np.array(matrix))
pos = nx.shell_layout(G)
nx.draw(G, pos)
if draw_edges:
nx.draw_networkx_edge_labels(G, pos, label_pos=0.3)
plt.show()
def path_to_matrix(path, matrix):
# Creates an adjacency matrix representing the path
nodes = range(len(matrix))
path_matrix = np.zeros_like(matrix)
for index in nodes:
line = path[index]
column = path[index + 1]
edge_weight = matrix[line][column]
path_matrix[line][column] = edge_weight
return path_matrix
def calculate_path_cost(matrix, path):
tsp_cost = 0
nodes = range(len(matrix))
for index in nodes:
line = path[index]
column = path[index + 1]
edge_weight = matrix[line][column]
tsp_cost += edge_weight
return tsp_cost
Força bruta¶
Uma das abordagens consideradas para resolver o PCV é a força bruta. Aqui, o método utilizado consiste em verificar todos os caminhos possíveis de forma exaustiva. O algoritmo de força bruta garante sempre que seja encontrado o melhor caminho possível para o problema. A desvantagem dessa abrodagem é sua alta complexidade: O(N!), que torna inviável a sua execução com valores mais altos de entrada.
Abaixo está apresentada a implementação desse algoritmo de forma recursiva.
def brute_force_tsp(matrix, path=[0], best_cost=float("inf"), best_path=None):
# Recursion base
if len(path) == len(matrix):
# Path ends on the initial node
path.append(0)
final_cost = calculate_path_cost(matrix, path)
if final_cost < best_cost:
best_path = path.copy()
best_cost = final_cost
path.pop()
return best_cost, best_path
# Recursive step
for node in range(len(matrix)):
if node in path:
continue
path.append(node)
best_cost, best_path = brute_force_tsp(matrix, path, best_cost, best_path)
path.pop()
return best_cost, best_path
Algoritmo aproximativo¶
A outra abordagem utilizada para a resolução do PCV é de algoritmo aproximativo. Essa abordagem só é possível para o PCV em sua versão euclidiana. O algoritmo consiste em montar uma árvore de espalhamento mínima, e então criar um ciclo hamiltoniano baseado nessa árvore (um caminho sem repetições que retorne ao vértice original). Essa abordagem possui uma complexidade menor que a força bruta, tornando viável solucionar o PVC com entradas maiores. Esse algoritmo é 2-aproximado, logo, podemos afirmar que o caminho encontrado por ele é, no pior caso, 2x pior que o melhor caminho.
A implementação desse algoritmo está apresentada abaixo.
def approximate_tsp(matrix, initial_node=0):
# Convert adjacency matrix to MST
MST = minimum_spanning_tree(matrix)
MST = MST.toarray().astype(int)
# Set initial parameters
nodes = range(len(MST))
path = list()
path.append(initial_node)
current_node = initial_node
previous_node = -1
# Creates a path until all nodes are connected
while len(set(path)) != len(nodes):
for connected_node in nodes:
# If there's no edge, continue
if MST[current_node, connected_node] == 0 and MST[connected_node, current_node] == 0:
continue
elif connected_node in path:
continue
else:
path.append(connected_node)
current_node = connected_node
# Reset previous node
previous_node = -1
break
else:
# If it did not found an edge, go back to previous node
current_node = path[previous_node]
previous_node = previous_node - 1
# Path ends on the initial node
path.append(initial_node)
tsp_cost = calculate_path_cost(matrix, path)
return tsp_cost, path
Comparando os algoritmos¶
def compare_algorithms(matrix_file, run_brute_force=False):
matrix = read_matrix_file(matrix_file)
# Get best approximate algorithm based on initial node
costs = dict()
for initial_node in range(len(matrix)):
start_time = time()
cost, approximate_path = approximate_tsp(matrix, initial_node=initial_node)
approximate_time = time() - start_time
costs[cost] = {"path": approximate_path,
"time": approximate_time}
min_cost = min(costs.keys())
min_path = costs[min_cost]["path"]
min_time = costs[min_cost]["time"]
# Get cost from file name
file_name = matrix_file.split('/').pop().upper()
tsp, cost = file_name.split('_')
cost = cost.split('.')[0]
brute_force_time = '--'
if run_brute_force:
start_time = time()
cost, path = brute_force_tsp(matrix)
brute_force_time = time() - start_time
return tsp, min_cost, min_time, cost, brute_force_time
files = (("tsp1_253.txt", True),
("tsp2_1248.txt", True),
("tsp3_1194.txt", False),
("tsp4_7013.txt", False),
("tsp5_27603.txt", False))
print("TSP\t\tAA Cost\t\tAA Time\t\tBF Cost\t\tBF Time")
for tsp_file in files:
tsp, brute_force = tsp_file
tsp, ap_cost, ap_time, bf_cost, bf_time = compare_algorithms(
f"./tsp_data/{tsp}", run_brute_force=brute_force)
if brute_force:
print(f'{tsp}\t\t{ap_cost}\t\t{ap_time:.5f}\t\t{bf_cost}\t\t{bf_time:.5f}')
else:
print(f'{tsp}\t\t{ap_cost}\t\t{ap_time:.5f}\t\t{bf_cost}\t\t{bf_time}')
Resultados¶
Para os 2 primeiros TSPs, foram executados ambos os algoritmos de força bruta e aproximativo. A execução do algoritmo de força bruta se mostrou inviável para os demais TSPs, portanto, foram excutados apenas os algoritmos aproximativos.
Custo da solução¶
Essa primeira tabela apresenta o custo dos caminhos encontrados pelo algoritmo aproximativo e pela força bruta. Aqui, também é possível observar que a proporção entre as duas soluções se manteve menor que 2x em todos os casos. Esse resultado está de acordo com a teoria vista em aula. No TSP2, o menor caminho encontrado pelo algoritmo aproximativo é igual ao caminho encontrado pela força bruta, o que pode ser explicado pelo baixo número de vértices.
No algoritmo aproximativo, foi observado que o custo resultante variava de acordo com vértice inicial escolhido. Por sua baixa complexidade, foi definida a estratégia de verificar todos os vértices como vértice inicial, decidindo pelo o que apresentasse o menor caminho. Na tabela também está apresentado o pior caso para cada execução do algoritmo. Mesmo nesse pior caso, o custo se manteve menor que 2x o custo do melhor caminho.
| TSP | Custo Força Bruta | Melhor Custo Aproximativo | Proporção | Pior Custo Aproximativo | Proporção |
|---|---|---|---|---|---|
| TSP1 | 253 | 260 | 1.028 | 274 | 1.083 |
| TSP2 | 1248 | 1248 | 1 | 1455 | 1.166 |
| TSP3 | 1194 | 1240 | 1.039 | 1613 | 1.351 |
| TSP4 | 7013 | 9976 | 1.423 | 13798 | 1.967 |
| TSP5 | 27603 | 31662 | 1.147 | 35881 | 1.300 |
Tempo de execução¶
Essa segunda tabela apresenta uma comparação entre o tempo de execução em segundos de ambos os algoritmos. Aqui, é possível verificar como o número de vértices afeta o tempo de execução de cada solução. O tempo estimado da força bruta foi calculado baseado no fatorial do número do vértices. O TSP2 apresentou menor tempo de execução na força bruto do que no algoritmo aproximativo, o que é possível em razão do seu baixo número de vértices.
| TSP | Tempo Aproximativo | Tempo Força Bruta | Vértices |
|---|---|---|---|
| TSP1 | 0.00190 | 14.28295 | 11 |
| TSP2 | 0.00036 | 0.00028 | 6 |
| TSP3 | 0.00052 | 5 dias e 2 horas (estimado) | 15 |
| TSP4 | 0.00536 | 2.852e36 anos (estimado) | 44 |
| TSP5 | 0.00980 | 9.482e16 anos (estimado) | 29 |
Caminho encontrado¶
As figuras a seguir apresentam (da esquerda para direita) o grafo original, o melhor caminho aproximado, e o melhor caminho (onde foi possível executar a força bruta). Essa figuras foram geradas pela biblioteca NetworkX.
TSP 1¶
TSP 2¶
TSP 3¶
TSP 4¶
TSP 5¶
