Heurística de Inserção em Grafos na resolução do Problema do

Heurística de Inserção em Grafos na resolução do Problema do Caixeiro Viajante
Roteiro
- Introdução ao Problema do Caixeiro Viajante (TCP)

-Heurística de Inserção e critérios: mais próximo, mais
distante e Randômico.

-Testes e resultados

-Conclusões

-Referencias
Introdução ao Problema do Caixeiro Viajante (TCP)
* Teve sua primeira menção em 1934, devido a Hassler Whitney em um trabalho na Princeton University.

* Consiste em percorrer um conjunto de cidades, dado as cidades e as distâncias entre elas.
Heurística de Inserção e critérios: mais próximo, mais distante e Randômico.
* As heurísticas são algoritmos que buscam uma solução boa em um tempo adequado.
Algoritmo
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.

Criterios de Escolha do Vértice
* Criterio do mais proximo: consiste em eleger o vertice mais proximo do ciclo atual, ou seja, de menor distância.

* Criterio do mais distante: consiste em eleger o vertice mais distante do ciclo atual, ou seja, de maior distância.

* Criterio de escolha aleatória: consiste em eleger o vertice dentre o conjunto de vértices não incluidos no ciclo de forma aleatória.
CONCLUSÕES
Neste trabalho foram realizados testes com a Heurísticas de Inserção. Os testes foram feitos para os três critérios de inserção do vértice mais próximo do ciclo, do mais distante do ciclo e do vértice escolhido com distância aleatório ao ciclo. Em relação à comparação de desempenho entre as Heurísticas e o valor ótimo de cada instância, observa-se na primeira tabela que os valores obtidos do custo do melhor ciclo bastante próximos do valor ótimo. Na segunda tabela não se usa o valor ótimo das instancias para comparar os valores obtidos, no entanto, o valor médio encontrado teve pouco desvio padrão dos valores máximos e melhores, dando a ideia que a heurística de inserção atingiu seu objetivo de encontrar um ciclo mínimo próximo do ótimo.
Equipe: Diego Gomes, Fabiana Perreira e Bruno Filgueiras. GRAFOS 2013.2
Critérios: mais próximo, mais distante e randômico
* 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,
* A Heurística da Inserção 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.
A Heurística de inserção foi implementada em NetBeans 7.3. Os testes computacionais foram realizados em um notebook com processador Intel(R) I3, 1,83 GHz e 4GB de RAM. Foram utilizados dados contidos nas referências. Os resultados obtidos foram comparados entre si com os três critérios de inserção. Os resultados foram:
Testes e Resultados
Referências
• http://homepages.dcc.ufmg.br/~nivio/cursos/pa03/tp2/tp22/tp22.html
• ftp://ftp.ufrn.br/pub/biblioteca/ext/bdtd/AlvaroNP.pdf
• http://www-usr.inf.ufsm.br/~andrezc/ia/heuristicas_construtivas_transparencias.pdf
• http://revistas.unoeste.br/revistas/ojs/index.php/ce/article/viewFile/939/995
• http://ictios.org/iv-erpon/wp-content/uploads/2013/06/AN%C3%81LISE-DE-HEUR%C3%8DSTICAS-DE-CONSTRU%C3%87%C3%83O-DE-ROTA.pdf
• http://www.densis.fee.unicamp.br/~franca/EA043/Transpa-Cap-3a.pdf