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 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