| dc.contributor | Fundação Araucária, PROPPG/UTFPR | pt-BR |
| dc.creator | Wall Berg Miranda dos Santos Morais; Universidade Tecnológica Federal do Paraná - UTFPR | |
| dc.creator | Marco Antonio de Castro Barbosa; Universidade Tecnológica Federal do Paraná, Pato Branco, Paraná, Brasil | |
| dc.date | 2017-10-07 01:05:30 | |
| dc.date.accessioned | 2022-12-07T17:17:48Z | |
| dc.date.available | 2022-12-07T17:17:48Z | |
| dc.identifier | https://eventos.utfpr.edu.br//sicite/sicite2017/paper/view/86 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/5303211 | |
| dc.description | Muitos problemas do cotidiano podem ser modelados como grafos. Caminhos, circuitos, fluxo em redes, fluxo de dados, roteamento, cortes, dentre vários outros. Muitos destes problemas possuem algoritmos heurísticos eficientes para instâncias relativamente grandes. Entretanto, o que se observa é que muitos destes algoritmos eficientes para estas instâncias não apresentam desempenho satisfatório para instância representadas por grafos massivos (grafos nos quais os conjuntos de vértices e arestas ultrapassam os milhões). Mesmo algoritmos heurísticos com ordem assintótica quadrática 0(n2) apresentam um desempenho insatisfatório para instâncias de grafos massivos. Portanto o novo desafio de pesquisa na área reside no desenvolvimento de métodos para o tratamento de grafos massivos. Em face do acima exposto, esta pesquisa tem por objetivo fazer um levantamento sobre o estado-da-arte no assunto: soluções heurísticas para grafos massivos e a adaptação de metaheurísticas clássicas, tais como, Simulated Annealing, Algoritmos Genéticos, GRASP, etc., para a solução de grafos massivos. Após um estudo sobre as possíveis metaheurísticas a serem implementadas, optou-se pelo algoritmo Simulated Annealing (SA). Para efeitos de comparação com trabalhos similares, existentes na literatura, optou-se pela implementação do SA para a resolução do problema da Cobertura Mínima de Vértices (PCMV). Os experimentos com o SA foram realizados sobre algumas instâncias de grafos massivos disponíveis no site Network Data Repository. A solução SA implementada foi comparada ao algoritmo FastVC que, atualmente, é o mais rápido método para solucionar o PCMV. Os resultados mostraram que o SA é bastante competitivo e apresenta bom desempenho quando aplicado a grafos massivos. | pt-BR |
| dc.language | pt | |
| dc.publisher | Seminário de Iniciação Científica e Tecnológica da UTFPR | pt-BR |
| dc.rights | Autores que submetem a esta conferência concordam com os seguintes termos:<br /> <strong>a)</strong> Autores mantém os direitos autorais sobre o trabalho, permitindo à conferência colocá-lo sob uma licença <a href="https://creativecommons.org/licenses/by/4.0/">Licença Creative Commons-Attribution</a>, que permite livremente a outros acessar, usar e compartilhar o trabalho com o crédito de autoria e apresentação inicial nesta conferência.<br /> <strong>b)</strong> Autores podem abrir mão dos termos da licença CC e definir contratos adicionais para a distribuição não-exclusiva e subsequente publicação deste trabalho (ex.: publicar uma versão atualizada em um periódico, disponibilizar em repositório institucional, ou publicá-lo em livro), com o crédito de autoria e apresentação inicial nesta conferência.<br /> <strong>c)</strong> Além disso, autores são incentivados a publicar e compartilhar seus trabalhos online (ex.: em repositório institucional ou em sua página pessoal) a qualquer momento antes e depois da conferência. | |
| dc.source | Seminário de Iniciação Científica e Tecnológica da UTFPR; XXII Seminário de Iniciação Científica e Tecnológica da UTFPR | 0 |
| dc.subject | Otimização; Grafos massivos; Metaheurística; Simulated Annealing | pt-BR |
| dc.title | O uso de meta heurísticas para problemas intratáveis em grafos massivos | 0 |
| dc.type | Documento avaliado pelos pares | pt-BR |
