Olá pessoal!
Estou tentando implementar um algoritmo de Busca Gulosa para o problema do Caixeiro Viajante (se conseguir, quero implementar também por Força Bruta). Eu comecei meu código criando uma matriz com números aleatórios para criar as distâncias das cidades, mas talvez esse não seja o melhor caminho e agora me perdi. kkkkkkk
Minha ideia era: criar essa matriz, pegar a diagonal dela que seriam as cidades e a partir daí calcular a distancia pra outros pontos. Mas então me perdi no processo…
Eu n queria utilizar um método que lesse as cidades de arquivos, alguém pode me dar uma luz?
Obrigada!
Só por curiosidade, vc tem formação em computação? Vc está implementando por curiosidade ou porque precisa? O caixeiro viajante é um dos problemas clássicos que são NP-difíceis… Uma matriz de adjacências não vai modelar corretamente um grafo de um mapa, pq dadas duas cidades, A e B, pode existir mais de um caminho entre elas… Se vc precisa implementá-lo para uma situação real, vc terá que estudar um pouco ou usar algo pronto (é o que eu faria pelo menos). Uma abordagem de força bruta é simplesmente impraticável, pois o problema é intratável. Um ponto de partida é o artigo em inglês da Wikipedia (https://en.wikipedia.org/wiki/Travelling_salesman_problem). A versão em português tbm tem bastante informação.
Mais alguns links: https://cs.stackexchange.com/search?q=TSP https://cstheory.stackexchange.com/search?q=TSP
4 curtidas