quarta-feira, 19 de setembro de 2007

O problema do caixeiro viajante

O Problema do Caixeiro Viajante (PCV), ou Traveling Salesman Problem (TSP), é um caso típico de otimização combinatória, freqüentemente utilizado em computação para demonstrar problemas de difícil resolução. A sua definição formal é: encontrar um caminho através de um grafo valorado que inicie e termine no mesmo vértice, passe por todos os demais vértices do grafo uma única vez e minimize o custo total. O problema do caixeiro viajante é um problema de otimização associado ao da determinação dos caminhos hamiltonianos em um grafo qualquer. O objetivo do PCV é encontrar, em um grafo G = (N, A), o caminho hamiltoniano de menor custo.

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:

diego@pti.org.br disse...

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

Luciano Zanuz disse...

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

Moises disse...

No PCV existe o problema de ciclagem ou subciclos, o que poderia ser feito para eliminar esse problema.

Atenciosamente,
Moisés

Denise Costa disse...

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.

Anônimo disse...

boas nao seria possivel enviar o trabalho para o mail pedro22dragao@sapo.pt é que o link para donwload da erro obrigado

brunonovaisjf disse...

Luciando, seu link não está mais funcionando, voce poderia me passar o codigo por email lpor gentileza??? brunokta@msn.com

grato desde já

luis disse...

boas nao seria possivel enviar
o trabalho para o mail luismcdc@hotmail.com é que o link para donwload da erro obrigado.

Baiano disse...

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

Leonardo Gutierres disse...

Me manda o software e o codigo, leonardo@vibeti.com.br

pedro disse...

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

Fernando disse...

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

Danilo lima SI 09 disse...

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

Luciano Zanuz disse...

Atualizado em 14/02/2011: O link para download do programa foi corrigido.

Anônimo disse...

Cara, o algoritmo não faz o caminho de volta.