Problema do Caixeiro Viajante
O Problema do Caixeiro Viajante (TSP) é um problema que possui como objetivo determinar a menor distância percorrendo várias cidades apenas uma vez cada e retornando a cidade na qual se iniciou a rota. O problema foi inspirado na necessidade de realizar entregas em locais distintos percorrendo o menor caminho, reduzindo assim o tempo e o custo das viagens.
Grafo Hamiltoniano
Um grafo G pode ser considerado hamiltoniano se existe um ciclo pertencente a G que contenha todos os seus vértices, e esses vértices devem aparecer somente uma vez no ciclo. O ciclo em questão é chamado de ciclo hamiltoniano. Ou seja, todo grafo que possui o ciclo hamiltoniano ele é um grafo hamiltoniano.
Objetivo
Desenvolver um programa que deve ler o grafo Hamiltoniano ponderado abaixo a partir de um arquivo qualquer e através de um algoritmo visto em sala (Twice-Around), obter 10 soluções diferentes para o problema do caixeiro-viajante.
Metodologia
Foi utilizada a linguagem de programação Python em conjunto com a biblioteca NetwrokX.
Após a execução do Twice-Around, o grafo obtido foi:
Liste as 3 melhores soluções e as 3 piores obtidas. Qual a diferença de custo entre a melhor e a pior? Discuta como a diferença pode ser significativa.
Melhores Soluções
Iniciando no vértice 29: 575.0
Iniciando no vértice 27: 577.0
Iniciando no vértice 13: 593.0
Iniciando no vértice 15: 682.0
Iniciando no vértice 18: 682.0
Iniciando no vértice 7: 676.0
A escolhe pelo vértice inicial pode ser bem significativa, visto que a diferença é consideravelmente grande. Há uma diferença de 10000km entre o pior e o melhor caminho.
Nenhum comentário:
Postar um comentário