Tentando resolver o problema do caixeiro viajante com python 🤯

Considerado as inúmeras tentativas de diversos matemáticos para resolver, que para muitos estudiosos é considerado um dos maiores problemas do século, e quem resolver tem chance de ficar igual ao tio patinhas, enfim eu não consegui resolver mas vou especificar com código python.

Mas antes de entrar em detalhes técnicos vou deixar claro o problema do caixeiro viajante:

Ok, imagina que temos um entregador ele tem diversos produtos em diferentes locais para entregar mas enfim este entregador tem um pequeno surto ao pensa qual é o itinerário mas curto para mim?

Aí que surge o problema dado um conjunto finito de pontos cujas distâncias são conhecidas, encontrar a rota mais curta que conecta todos os pontos e volta ao ponto de partida. Esse é o problema matemático, então como é possível resolver?

Eu usei dois algoritmos, o de força bruta e algoritmo polinomial, por mais que temos objetivos, que é encontrar o menor percurso possível que passe por todas as cidades uma vez e retorne a cidade de origem, os algoritmos tem desvantagens devido a complexidade de cada um.

Algoritmo de força bruta:

Esse algoritmo gera todas as permutações possíveis das cidades e calcula o custo de cada percurso:

from itertools import permutations

def tsp_brute_force(distances):
  cities = list(range(len(distances)))
  min_path = None
  min_cost = float('inf')

  for perm in permutations(cities):
      cost = sum(distances[perm[i]][perm[i+1]] for i in range(len(perm)-1))
      cost += distances[perm[-1]][perm[0]]  # Voltar à cidade de origem

      if cost < min_cost:
          min_cost = cost
          min_path = perm

  return min_path, min_cost

# Exemplo de matriz de distâncias
distances = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0]
]

min_path, min_cost = tsp_brute_force(distances)
print(f"Menor caminho: {min_
path}, Custo: {min_cost}")

Ohhh🤯,Encontrou a solução ótima, mas é impraticável para grandes problemas devido à complexidade O(n!)😞. Ou seja o tempo de execução cresce exponencialmente conforme a quantidade de cidades, quando for lidar com uma grande quantidade de dados se torna impossível de se usar para resolver o problema.

Algoritmo Polinominal:

Agora vamos usar o conhecidíssimo o algoritmo do vizinho mais próximo(Nearest Neighbor).

def tsp_nearest_neighbor(distances):
  n = len(distances)
  visited = [False] * n
  path = [0]
  visited[0] = True
  total_cost = 0

  for _ in range(1, n):
      last_city = path[-1]
      next_city = min(
          [(i, distances[last_city][i]) for i in range(n) if not visited[i]],
          key=lambda x: x[1]
      )[0]
      path.append(next_city)
      visited[next_city] = True
      total_cost += distances[last_city][next_city]

  total_cost += distances[path[-1]][path[0]]  # Voltar à cidade de origem
  return path, total_cost

min_path, min_cost = tsp_nearest_neighbor(distances)
print(f"Menor caminho (aproximado): {min_path}
, Custo: {min_cost}")

Olha esse deu uma solução boa para grande quantidade de dados, mas se torna ineficiente para trazer os caminhos, pois para cada loop ele vai carregar de novo os vizinhos próximos, e ainda mais o algoritmo não revisita suas escolhas, e não conheço uma forma que possa fazer com que ele volte para certas rotas e revise, talvez com um loop com -= 1, para os valores de posição das cidades, enfim vou falar como outro "eu tentei ", estou aberto a opiniões.

Espero que o artigo tenha sido divertido e tenha possibilitado quebrar um pouco a cabeça.