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

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

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.


Palavras-chave


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

Texto completo:

PDF


DOI: https://doi.org/10.5540/03.2017.005.01.0458

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato