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...
Na minha lista:
| Autor principal: | |
|---|---|
| Outros Autores: | |
| Formato: | Dissertação |
| Idioma: | por |
| Publicado em: |
Universidade Federal do Rio Grande do Norte
|
| Assuntos: | |
| Endereço do item: | https://repositorio.ufrn.br/jspui/handle/123456789/18081 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| Resumo: | 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 |
|---|