Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma

Nonogram is a logical puzzle whose associated decision problem is NP-complete. It has applications in pattern recognition problems and data compression, among others. The puzzle consists in determining an assignment of colors to pixels distributed in a N  M matrix that satisfies line and...

ver descrição completa

Na minha lista:
Detalhes bibliográficos
Autor principal: Oliveira, Camila Nascimento de
Outros Autores: Gouvêa, Elizabeth Ferreira
Formato: Dissertação
Idioma:por
Publicado em: Universidade Federal do Rio Grande do Norte
Assuntos:
Nonograma. Busca em profundidade. Las Vegas. Problema de satisfação de restrições. Busca tabu. Memético
Nonogram. Depth first search. Las Vegas. Constraint satisfaction problem. Tabu search. Memetic
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Endereço do item:https://repositorio.ufrn.br/jspui/handle/123456789/18081
Tags: Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
id ri-123456789-18081
record_format dspace
spelling ri-123456789-180812017-11-04T16:11:36Z Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma Exact and metaheuristic algorithms research applied to nonogram 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/1371199678541174 Nonograma. Busca em profundidade. Las Vegas. Problema de satisfação de restrições. Busca tabu. Memético Nonogram. Depth first search. Las Vegas. Constraint satisfaction problem. Tabu search. Memetic CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO Nonogram is a logical puzzle whose associated decision problem is NP-complete. It has applications in pattern recognition problems and data compression, among others. The puzzle consists in determining an assignment of colors to pixels distributed in a N  M matrix that satisfies line and column constraints. A Nonogram is encoded by a vector whose elements specify the number of pixels in each row and column of a figure without specifying their coordinates. This work presents exact and heuristic approaches to solve Nonograms. The depth first search was one of the chosen exact approaches because it is a typical example of brute search algorithm that is easy to implement. Another implemented exact approach was based on the Las Vegas algorithm, so that we intend to investigate whether the randomness introduce by the Las Vegas-based algorithm would be an advantage over the depth first search. The Nonogram is also transformed into a Constraint Satisfaction Problem. Three heuristics approaches are proposed: a Tabu Search and two memetic algorithms. A new function to calculate the objective function is proposed. The approaches are applied on 234 instances, the size of the instances ranging from 5 x 5 to 100 x 100 size, and including logical and random Nonograms O 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 2014-12-17T15:48:07Z 2013-09-03 2014-12-17T15:48:07Z 2013-02-01 masterThesis OLIVEIRA, Camila Nascimento de. Exact and metaheuristic algorithms research applied to nonogram. 2013. 108 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Rio Grande do Norte, Natal, 2013. https://repositorio.ufrn.br/jspui/handle/123456789/18081 por Acesso Aberto application/pdf application/pdf Universidade Federal do Rio Grande do Norte BR UFRN Programa de Pós-Graduação em Sistemas e Computação Ciência da Computação
institution Repositório Institucional
collection RI - UFRN
language por
topic Nonograma. Busca em profundidade. Las Vegas. Problema de satisfação de restrições. Busca tabu. Memético
Nonogram. Depth first search. Las Vegas. Constraint satisfaction problem. Tabu search. Memetic
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
spellingShingle Nonograma. Busca em profundidade. Las Vegas. Problema de satisfação de restrições. Busca tabu. Memético
Nonogram. Depth first search. Las Vegas. Constraint satisfaction problem. Tabu search. Memetic
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
Oliveira, Camila Nascimento de
Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma
description Nonogram is a logical puzzle whose associated decision problem is NP-complete. It has applications in pattern recognition problems and data compression, among others. The puzzle consists in determining an assignment of colors to pixels distributed in a N  M matrix that satisfies line and column constraints. A Nonogram is encoded by a vector whose elements specify the number of pixels in each row and column of a figure without specifying their coordinates. This work presents exact and heuristic approaches to solve Nonograms. The depth first search was one of the chosen exact approaches because it is a typical example of brute search algorithm that is easy to implement. Another implemented exact approach was based on the Las Vegas algorithm, so that we intend to investigate whether the randomness introduce by the Las Vegas-based algorithm would be an advantage over the depth first search. The Nonogram is also transformed into a Constraint Satisfaction Problem. Three heuristics approaches are proposed: a Tabu Search and two memetic algorithms. A new function to calculate the objective function is proposed. The approaches are applied on 234 instances, the size of the instances ranging from 5 x 5 to 100 x 100 size, and including logical and random Nonograms
author2 Gouvêa, Elizabeth Ferreira
author_facet Gouvêa, Elizabeth Ferreira
Oliveira, Camila Nascimento de
format masterThesis
author Oliveira, Camila Nascimento de
author_sort Oliveira, Camila Nascimento de
title Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma
title_short Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma
title_full Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma
title_fullStr Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma
title_full_unstemmed Uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma
title_sort uma investigação de algoritmos exatos e metaheurísticos aplicados ao nonograma
publisher Universidade Federal do Rio Grande do Norte
publishDate 2014
url https://repositorio.ufrn.br/jspui/handle/123456789/18081
work_keys_str_mv AT oliveiracamilanascimentode umainvestigacaodealgoritmosexatosemetaheuristicosaplicadosaononograma
AT oliveiracamilanascimentode exactandmetaheuristicalgorithmsresearchappliedtononogram
_version_ 1773961152999456768

Registros relacionados