Trabalho 5
Contexto
O Problema do Caixeiro Viajante (TSP) faz a seguinte pergunta: "Dada uma lista de cidades e distância entre cada par delas, qual é a distância mínima possível em que o Caixeiro Viajante poderia visitar todas as cidades exatamente uma vez e retornar à sua de origem?".
Esse é um problema de nível NP-Hard (onde não há um algoritmo ótimo para a resolução do mesmo) da otimização computacional, importante em operações de pesquisa e ciência da computação teórica.
Um grafo G é dito um Grafo Hamiltoniano se existe um ciclo no mesmo que contenha todos os seus vértices, sendo que cada vértice só aparece uma vez no ciclo, que é chamado de Ciclo Hamiltoniano; sendo assim, um grafo é hamiltoniano caso contenha um ciclo hamiltoniano.
Execução
O objetivo deste trabalho é, utilizando um dos algoritmos apresentados em sala para o TSP (Twice-around ou 2-otimal) e um grafo fornecido, encontrar 10 possíveis soluções para o Problema do Caixeiro Viajante e elencar as três melhores e três piores soluções encontradas.
O algoritmo usado pelo grupo foi o Twice Around, um algoritmo de aproximação para o TSP com distâncias Euclidianas. Para o desenvolvimento do código foi utilizada a linguagem Python e a biblioteca NetworkX, além da IDE Spyder.
 |
| Grafo de 30 vértices fornecido para a implementação do algoritmo |
 |
| Algoritmo Twice Around |
 |
| Grafo G gerado |
Analisando os resultados, então, podemos concluir que os três melhores caminhos para o início da Tour de Euler se iniciam nos vértices 13 (peso 593), 27 (peso 577) e 29 (peso 575). Por sua vez, os piores inícios para a Tour de Euler se encontram nos vértices 7 (peso 676), 15 (peso 682) e 18 (peso 682).
A diferença entre os pesos dos caminhos é claramente visível dependendo do vértice escolhido; se aplicado num problema real e cada vértice fosse uma cidade ou até mesmo país, teríamos uma diferença absurda de quilômetros entre o melhor e pior caminho.
Comentários
Postar um comentário