Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

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

No description
by

Diego Gomes

on 12 December 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 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
Full transcript