Propostas Eficientes para o Problema de Inundação em Grafos

- 84565
Artigo Completo
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O Problema de Inundação em Grafos deriva de um popular jogo de tabuleiro com dimensão n x m de casas coloridas. O objetivo do jogo é aplicar mudanças de cores, denominadas inundações, a alguma casa até que todo o tabuleiro seja monocromático. O jogo tem duas versões: a versão fixa e a livre, onde ambas têm o mesmo objetivo. Para resolver o problema são propostos neste trabalho três algoritmos heurísticos: Iterated Local Search (ILS), Greedy Randomized Adaptive Search Procedure (GRASP) e um Algoritmo Evolutivo (EA). Os resultados obtidos foram comparados com formulações matemáticas encontradas na literatura e obtiveram a mesma qualidade das soluções dos algoritmos exatos. Porém, foram encontradas em tempo computacional muito inferior. O aluno (primeiro autor) desenvolveu o trabalho, como parte de seu projeto de iniciação científica e trabalho de conclusão de curso em Ciência da Computação, sempre supervisionado pelos outros dois autores (orientadores).

Instituições
  • 1 Universidade Federal Rural de Pernambuco
  • 2 Universidade Federal Fluminense
Eixo Temático
  • OC – Otimização Combinatória
Palavras-chave
Problema de Inundação em Grafos
Metaheurísticas