Heurística de Inserção em Grafos na resolução do Problema do Caixeiro Viajante Critérios: mais próximo, mais distante e randômico Implementação e Testes

Heurística de Inserção em Grafos na resolução do Problema do Caixeiro Viajante Critérios: mais próximo, mais distante e randômico Implementação e Testes

Diego Gomes Tomé* Francisca Fabiana Pereira da Silva** Francisco Bruno Filgueiras***

RESUMO
Este trabalho tem como objetivo mostrar a resolução do problema caixeiro viajante através da heurística de inserção em grafos. O problema do caixeiro viajante consiste em determinar num grafo ponderado, um ciclo hamiltoniano de custo mínimo. Na implementação do algoritmo de inserção foram utilizados três critérios de escolha de vértices: mais próximo, mais distante e por escolha randômica.
Palavras-chave: Caixeiro viajante. Algoritmo de inserção. Custo mínimo.

* Graduando em Ciência da Computação – UECE, [e-mail].
** Graduando em Ciência da Computação – UECE, [e-mail].
*** Graduando em Ciência da Computação – UECE, [e-mail].
1. INDRODUÇÃO O Problema do Caixeiro Viajante (PCV) mais conhecido na literatura como Traveling Salesman Problem, teve sua primeira menção em 1934, devido a Hassler Whitney em um trabalho na Princeton University. é um problema que consiste em percorrer um conjunto de cidades, dado as cidades e as distâncias entre elas. O caixeiro tem que visitar todas as cidades sem repeti-las, partindo da primeira, chamada de origem, visitando as (n-1) cidades apenas uma única vez e voltando para a cidade origem e que o trajeto percorrido seja o menor possível. Em outras palavras, “seja um grafo G= (V, E) onde V= {1,2,3...v} é o conjunto de vértices, e E={1,2,3...e} é o conjunto de arestas de G, e custos Cij, associados com cada arestas ligando os vértices i e j, o problema do caixeiro viajante consiste em localizar o