Publicado no Encontro de Saberes 2016
Evento: XXIV Seminário de Iniciação Científica
Área: CIÊNCIAS EXATAS E DA TERRA
Subárea: Ciência da Computação
Órgão de Fomento: Conselho Nacional de Desenvolvimento Científico e Tecnológico
| Título |
| Uma Ferramenta Diagramação Automática de Modelos Entidade-Relacionamento Utilizando Heurísticas: Abordagens Paralelas |
| Autores |
|
CEZAR AUGUSTO NASCIMENTO E SILVA (Autor) HAROLDO GAMBINI SANTOS (DECOM) (Orientador) |
| Resumo |
| No problema de Diagramação de Grafos, um conjunto de símbolos devem ser desenhados em um plano(fase 1) e suas conexões devem ser criadas(fase 2). Para produzir um diagrama legível e esteticamente bonito este problema é geralmente resolvido tentando-se minimizar o cruzamento de arestas e a área utilizada pelo desenho, resultando em um problema NP-Hard. Nossa pesquisa se especializa em desenhar Diagramas Entidade-Relacionamento, uma versão interessante do problema em que os vértices têm tamanhos diferentes e as arestas representam referências de chaves estrangeiras. Havendo tal divisão do problema, verificamos que a segunda fase é extremamente dependente da primeira uma vez que a qualidade das conexões é muito dependente do posicionamento dos símbolos. Inicialmente o problema foi abordado utilizando-se Programação Inteira(PI) para a resolução de ambas as fases, porém testes experimentais demonstraram uma particular dificuldade dos resolvedores de Programação Inteira para se provar a otimalidade do problema para a primeira fase, os quais eram capazes de provar a otimalidade apenas para instâncias fáceis do problema, sendo incapazes de resolver as demais com um tempo máximo de duas horas e modo paralelo habilitado. A fase 2 se mostra bem resolvida com Programação Inteira sendo capaz de provar a otimalidade em menos de dez minutos para qualquer instância testada. Reconhecendo a dificuldade de resolução da primeira fase decidimos implementar e apresentar um método heurístico para a sua resolução utilizando uma Busca de Vizinhança Variável(VNS) customizada para melhor resolver o problema, por exemplo com execuções em paralelo e buscas locais internas. Utilizando-se tanto o método puramente de PI (para a fase 1 e fase 2) ou utilizando-se o método misto(VNS para a fase 1 e PI para a fase 2) conseguimos obter diagramas melhores que as imagens encontradas na web para os mesmos, e também para instâncias artificiais. |
