Fiz um programa em Java que implementou o algoritmo Depth-First Search (busca em profundidade) para encontrar a solução ótima do problema do caixeiro viajante. Quem quiser pode fazer o download do programa. O algoritmo implementado é de força-bruta, ou seja, testa todas as possibilidades possíveis. Assim, como a complexidade do programa é da ordem de n!, logo a execução do programa torna-se inviável. Em meus testes, para n=14, o tempo de execução foi de 42,73 minutos. A estimativa de tempo para n=15 é de 15 vezes esse tempo, ou seja, 641 minutos.
Ao executar o programa, deve ser informada a matriz de adjacência do grafo, indicando as distâncias entre os vértices. A figura acima ilustra a execução do problema do caixeiro viajante com n=4. Para n=5, deve-se incluir uma uma nova linha e uma nova coluna em todas as linhas. O resultado apresentará o menor caminho que saia da cidade 0, passe por todas as outras cidades e retorne para 0.
Atualizado em 14/02/2011: O link para download do programa foi corrigido.
14 comentários:
Olá luciano, preciso fazer um trabalho parecido com o seu. No caso, preciso fazer um circuito hamiltoniano em um grafo.
Caso esteja interessado em ajudar, entre em contato!
MSN: diego@pti.org.br
Escrevi um artigo sobre o Caixeiro Viajante e disponibilizei para download no link
http://lucianozanuz.blogspot.com/2007/10/ltimos-trabalhos-do-segundo-trimestre.html. Espero que ajude!
Abraços
No PCV existe o problema de ciclagem ou subciclos, o que poderia ser feito para eliminar esse problema.
Atenciosamente,
Moisés
Olá Luciano.
Tentei fazer download do do seu artigo sobre caixero viajannte, mas não está dando erro na pagina como não encontrado.
Se poder mandar por e-mail ficaria muito grata.
denisehcosta@gmail.com
Obrigado.
boas nao seria possivel enviar o trabalho para o mail pedro22dragao@sapo.pt é que o link para donwload da erro obrigado
Luciando, seu link não está mais funcionando, voce poderia me passar o codigo por email lpor gentileza??? brunokta@msn.com
grato desde já
boas nao seria possivel enviar
o trabalho para o mail luismcdc@hotmail.com é que o link para donwload da erro obrigado.
Olá Luciano ficarei muito grato se vc puder me enviar o codigo do problema do caixeiro viajante pois o link tá quebrado.
meu email: laudimar.brito@gmail.com
desde já agradeço!!!!!!!!!
Laudimar
Me manda o software e o codigo, leonardo@vibeti.com.br
E ai Luciano blz?
Nao consegui o programa atraves do link que colocasse a disposição.
Teria como mandar para meu email?
pedrokloppel@gmail.com
Olá Luciano, fiquei muito interessado pelo seu trabalho, talvez poderia me ajudar com o meu trabalho da facul. Poderia me passar para o meu email?
fernando_5371@hotmail.com
Att,
Fernando da Cruz Pinheiro
tentei baixar seu programa, mais o link ta quebrado, se possivel me envie o link correto para meu email (danilolima.si09@gmail.com)ou poste aki no blog.
Desde já agradeço a atenção.
Atenciosamente,
Danilo Lima
Atualizado em 14/02/2011: O link para download do programa foi corrigido.
Cara, o algoritmo não faz o caminho de volta.
Postar um comentário