Gouvêa, Elizabeth FerreiraOliveira, Camila Nascimento de2014-12-172013-09-032014-12-172013-02-01OLIVEIRA, 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/18081Nonogram 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 Nonogramsapplication/pdfAcesso AbertoNonograma. Busca em profundidade. Las Vegas. Problema de satisfação de restrições. Busca tabu. MeméticoNonogram. Depth first search. Las Vegas. Constraint satisfaction problem. Tabu search. MemeticmasterThesisCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO