Navegando por Autor "Oliveira, Camila Nascimento de"
Agora exibindo 1 - 1 de 1
- Resultados por página
- Opções de Ordenação
Dissertação Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma(Universidade Federal do Rio Grande do Norte, 2013-02-01) Oliveira, Camila Nascimento de; Gouvêa, Elizabeth Ferreira; ; http://lattes.cnpq.br/2888641121265608; ; Thomé, Antônio Carlos Gay; ; http://lattes.cnpq.br/9282046098909851; Ramos, Iloneide Carlos de Oliveira; ; http://lattes.cnpq.br/0613948277011672; Goldbarg, Marco César; ; http://lattes.cnpq.br/1371199678541174O Nonograma é um jogo lógico cujo problema de decisão associado é NP-completo. Ele possui aplicação em problemas de identificação de padrões e de compactação de dados, dentre outros. O jogo consiste em determinar uma alocação de cores em pixels distribuídos em uma matriz N M atendendo restrições em linhas e colunas. Um Nonograma é codificado através de vetores cujos elementos especificam o número de pixels existentes em cada coluna e linha de uma figura, sem especificar suas coordenadas. Este trabalho apresenta abordagens exatas e heurísticas para solucionar o Nonograma. A Busca em Profundidade foi uma das abordagens exatas escolhida, por ser um exemplo típico de algoritmo de força bruta de fácil implementação. Outra abordagem exata implementada foi baseada no algoritmo Las Vegas, através do qual se pretende investigar se a aleatoriedade introduzida pelo algoritmo Las Vegas traria algum benefício em relação à Busca em Profundidade. O Nonograma também é transformado em um Problema de Satisfação de Restrições. Três abordagens heurísticas são propostas: uma Busca Tabu e dois algoritmos Memético. Uma nova abordagem para o cálculo da função objetivo é proposta neste trabalho. As abordagens são testadas em 234 casos de teste de tamanho entre 5 x 5 e 100 x 100, incluindo Nonogramas lógicos e aleatórios