Made available in DSpace on 2014-12-17T15:48:07Z (GMT). No. of bitstreams: 1
CamilaNOT_DISSERT.pdf: 4321465 bytes, checksum: d103bd2da647997e8dfd0a8784c2060d (MD5)
Previous issue date: 2013-02-01 / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/18081 |
| Date | 01 February 2013 |
| Creators | Oliveira, Camila Nascimento de |
| Contributors | CPF:81652011749, http://lattes.cnpq.br/2888641121265608, Thom?, Ant?nio Carlos Gay, CPF:23336048753, http://lattes.cnpq.br/9282046098909851, Ramos, Iloneide Carlos de Oliveira, CPF:24260142453, http://lattes.cnpq.br/0613948277011672, Goldbarg, Marco C?sar, CPF:25841025953, http://lattes.cnpq.br/1371199678541174, Gouv?a, Elizabeth Ferreira |
| Publisher | Universidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Sistemas e Computa??o, UFRN, BR, Ci?ncia da Computa??o |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds