Ceixeiro viajante

O Caixeiro Viajante no Interior de Minas Gerais
Giselle Moraes Resende Pereira, Marcos Antônio Câmara (Tutor do PETMatemática).
Faculdade de Matemática, UFU, MG
Universidade Federal de Uberlândia, Minas Gerais

1. Objetivos
O objetivo do trabalho é o estudo de um problema de grafos considerado complexo e algoritmos que possam solucioná-lo. Neste sentido são investigados os algoritmos dos mínimos sucessivos e o algoritmo da ordenação do peso das arestas para um problema clássico de grafos hamiltonianos, o problema do caixeiro viajante, que consiste em estabelecer uma viagem circular (que o leve ao ponto de partida) de forma que ele visite cada cidade exatamente uma vez determinando o melhor percurso.

2. Material e Métodos
Inicialmente foi feito o levantamento das distâncias entre as cidades selecionadas do estado de Minas Gerais (Belo Horizonte,
Uberlândia, Araguari, Araxá, Patos de Minas,
Patrocínio e Uberaba), e construído o grafo correspondente. Para a resolução do problema de grafo proposto, foram utilizados algoritmos, que se baseiam numa escolha sucessiva da melhor etapa que, apesar de não garantir a melhor solução, em geral, garante uma solução adequada. 3. Resultados e discussão
Foram implementados dois algoritmos, os algoritmos dos mínimos sucessivos e o algoritmo da ordenação do peso das arestas, para comparação e para a resolução do problema do caixeiro viajante que tinha de percorrer as sete cidades mineiras selecionadas. O grafo obtido está representado na figura 1. Os resultados foram diferentes para cada algoritmo, possibilitando a escolha do caminho mais econômico. Pelo algoritmo dos

mínimos sucessivos encontramos que o melhor percurso totalizaria 1420 km e pelo algoritmo da ordenação do peso das arestas seria de
1446 km, contribuindo para a escolha adequada. Figura 1

4. Conclusões
Os algoritmos podem se mostrar eficientes para problemas complexos. Além disto, eles permitem trabalhar