Heuristicas construtivas para um problema de inundação em matrizes

Autores

  • André Renato Villela da Silva
  • Ricardo Vilela Machado
  • Maise Dantas da Silva

DOI:

https://doi.org/10.5540/03.2017.005.01.0458

Palavras-chave:

Problemas de inundação, heurı́sticas construtivas, otimização combinatória.

Resumo

O problema de inundação é derivado de um popular jogo de computador de-
nominado Flood-It. O objetivo é tornar monocromática uma matriz colorida através do menor número de etapas de inundação. Por inundação entende-se o processo de modificar a cor de uma região monocromática da matriz, fazendo assim com que regiões vizinhas se aglomerem. Pelo nosso conhecimento, a literatura para o problema (que é NP-difı́cil no caso geral) trata apenas de provas teóricas para diversas possı́veis situações de instâncias. Este trabalho apresenta um estudo empı́rico de diversas heurı́sticas construtivas para o problema. Diversas instâncias de portes distintos também são propostas para servirem de benchmark para testes futuros.

Downloads

Não há dados estatísticos.

Downloads

Publicado

2017-04-14

Edição

Seção

Trabalhos Completos - Otimização