image

Acesse bootcamps ilimitados e +650 cursos

50
%OFF
Article image
Tiago Almeida
Tiago Almeida04/09/2024 11:21
Compartilhe

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.

    image

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

    Compartilhe
    Comentários (1)
    Tiago Almeida
    Tiago Almeida - 04/09/2024 11:44

    Referência:


    https://impa.br/noticias/folha-o-problema-do-caixeiro-viajante/