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

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.