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 menor ciclo hamiltoniano do grafo G” (Álvaro Nunes, 2006, p.4).

O PCV tem larga aplicabilidade em situações reais devido sua fácil compreensão e descrição, apesar de difícil resolução, pois pertence a classe de problemas NP-Árduos, segundo Garey e Jonhson (1979). Os problemas de NP-Árduos dificilmente serão apresentados algoritmos polinomiais que os solucionam, pois o esforço computacional para a resolução do problema cresce exponencialmente com o tamanho do problema. O PCV é um problema de otimização combinatória. Os problemas de alocação, roteamento e programação de horários são exemplos de problemas de otimização. Os problemas de otimização são de difícil resolução, por isso pesquisadores de diversas áreas buscam por soluções desenvolvendo algoritmos cada vez mais eficientes.

A programação inteira possui algoritmos exatos que garantem a obtenção da solução ótima para o problema de otimização combinatória. Segundo Dumitrescu e Stutzle (2003), os métodos exatos na solução de problemas de otimização combinatória tem desvantagem em muitos problemas por ter custo computacional muito elevado, principalmente naqueles que crescem exponencialmente. Para compensar o custo computacional dos métodos exatos, usam-se as heurísticas. As heurísticas são algoritmos que buscam uma solução boa em um tempo adequado, mas não é a garantia de uma solução ótima. Neste trabalho serão analisados e comparados os critérios de inserção do vértice mais próximo, mais distante e vértice aleatório da heurística de inserção aplicado ao problema do caixeiro viajante através de testes computacionais. Em seguida será feito a conclusão dos resultados obtidos.

1.1 Heurística de Inserção

A heurística de inserção também conhecido como método guloso consiste em gerar um circuito viável de vértices partindo de um conjunto inicial de três vértices, e modificando esse conjunto após adicionar um vértice a cada iteração utilizando algum critério de escolha.

1.2 Algoritmo de Inserção para o PCV

Dado G = (V, E) um grafo completo e simétrico, e Cij o custo não negativo associado com cada aresta ligando os vértices i e j do grafo. O algoritmo de inserção é dado por:

a) Partir de um ciclo inicial de tamanho K=3 ou K=4, escolhido de forma aleatória.

b) Encontre um vértice v pertencente ao grafo e não pertencente ao ciclo, utilizando um dos critérios:

• Mais próxima do ciclo

• Mais distante do ciclo

• Aleatório

c) Incluir o vértice v no ciclo na posição que gere o menor custo, ou seja, encontre uma aresta (i, j) do ciclo que minimize {Civ + Cvj - Cij}

d) Insira o vértice v entre i e j. Forme um novo ciclo com o vértice incluso e retorne a etapa-b até K=V.

Exemplo:

1.3 Heurística de inserção mais próximo

Seja G = (V, E), um grafo completo como na figura 1:

O ciclo inicial é: C = {1, 3, 4, 1} com custo inicial Custo(C) = 22.

Iteração 1:

Vértice mais próximo do ciclo é: 5.

Temos 3 inserções possíveis:

• Inserção