Please use this identifier to cite or link to this item: http://www.repositorio.ufop.br/jspui/handle/123456789/10571
Title: Busca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos.
Authors: Santos, Vinícius Gandra Martins
metadata.dc.contributor.advisor: Carvalho, Marco Antonio Moreira de
Keywords: Heurística
Teoria dos grafos
Otimização combinatória
Issue Date: 2018
metadata.dc.contributor.referee: Carvalho, Marco Antonio Moreira de
Souza, Marcone Jamilson Freitas
Santos, André Gustavo dos
Lima, Joubert de Castro
Citation: SANTOS, Vinícius Gandra Martins. Busca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos. 2018. 75 f. Dissertação (Mestrado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2018.
Abstract: O problema de Minimização da Largura de Corte em Grafos (ou CMP, do inglês Cutwidth Minimization Problem) consiste em determinar um leiaute linear para um grafo de forma a minimizar a quantidade máxima de arestas que cruzam cada par de vértices consecutivos. Esse problema pode ser encontrado no projeto de circuitos integrados de larga escala, no desenho de diagramas de grafos e no projeto de compiladores, entre outros. O CMP é um problema NP-Difícil e se apresenta como um desafio para métodos exatos e heurísticas. Neste trabalho, é reportada pela primeira vez na literatura a aplicação do método metaheurístico Busca Adaptativa em Grandes Vizinhanças (Adaptive Large Neighborhood Search) para solução do CMP. Os experimentos computacionais envolvem 11.786 instâncias de quatro conjuntos da literatura e os resultados encontrados são comparados com o atual estado da arte. O método proposto se mostra competitivo, sendo capaz de igualar a maioria dos resultados comprovadamente ótimos e melhores resultados conhecidos, além de melhorar alguns resultados que não foram provados ótimos e encontrar pela primeira vez limitantes superiores para instâncias não resolvidas.
metadata.dc.description.abstracten: The cutwidth minimization problem (CMP) consists in determining a linear layout of the vertices of a graph that minimizes the maximum cardinality of edges cut between any consecutive pair of vertices. This problem has applications, for instance, in design of very large-scale integration circuits, graph drawing, and compiler design, among others. The CMP is an NP-Hard problem and presents a challenge to exact methods and heuristics. In this study, the metaheuristic adaptive large neighborhood search is applied for the first time to the CMP. The computational experiments include 11,786 benchmark instances from the literature, and the obtained results are compared with those of the state-of-the-art methods. The proposed method was demonstrated to be competitive, as it matched most of proved optimal and best known results, improved some of the (not proved optimal) best known solutions, and provided the first upper bounds for unsolved instances.
Description: Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
URI: http://www.repositorio.ufop.br/handle/123456789/10571
metadata.dc.rights.license: Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 29/11/2018 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação.
Appears in Collections:PPGCC - Mestrado (Dissertações)

Files in This Item:
File Description SizeFormat 
DISSERTAÇÃO_BuscaAdaptativaGrandes.pdf1,54 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons