Uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma /

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 x M atendendo restrições e...

ver descrição completa

Na minha lista:

Detalhes bibliográficos
Principais autores:	Taumaturgo, Camila Nascimento de Oliveira., Goldbarg, Elizabeth Ferreira Gouvêa., Universidade Federal do Rio Grande do Norte.
Formato:	Dissertação
Publicado em:
Assuntos:	Algoritmos - Dissertação. Nanograma - Jogos de raciocíno lógico - Busca em profundidade - Las Vegas - Problema de satisfação de restrições - Busca Tabu - Algoritmo memético - Games logical reasoning. Nanogram.
Endereço do item:	https://repositorio.ufrn.br/jspui/bitstream/123456789/18081/1/CamilaNOT_DISSERT.pdf
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	oai:localhost:123456789-132665
record_format	dspace
spelling	oai:localhost:123456789-1326652022-12-01T02:02:56Z Uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma / Taumaturgo, Camila Nascimento de Oliveira. Goldbarg, Elizabeth Ferreira Gouvêa. Universidade Federal do Rio Grande do Norte. Algoritmos - Dissertação. Nanograma - Jogos de raciocíno lógico - Dissertação. Busca em profundidade - Las Vegas - Dissertação. Problema de satisfação de restrições - Dissertação. Busca Tabu - Algoritmo memético - Dissertação. Games logical reasoning. Nanogram. 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 x 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.#$&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 x 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. 1 2022-10-06T08:43:29Z 2022-10-06T08:43:29Z 2013. Dissertação 004.421 T225i DISSERT 202243 https://repositorio.ufrn.br/jspui/bitstream/123456789/18081/1/CamilaNOT_DISSERT.pdf https://repositorio.ufrn.br/jspui/bitstream/123456789/18081/1/CamilaNOT_DISSERT.pdf
institution	Acervo SISBI
collection	SIGAA
topic	Algoritmos - Dissertação. Nanograma - Jogos de raciocíno lógico - Dissertação. Busca em profundidade - Las Vegas - Dissertação. Problema de satisfação de restrições - Dissertação. Busca Tabu - Algoritmo memético - Dissertação. Games logical reasoning. Nanogram.
spellingShingle	Algoritmos - Dissertação. Nanograma - Jogos de raciocíno lógico - Dissertação. Busca em profundidade - Las Vegas - Dissertação. Problema de satisfação de restrições - Dissertação. Busca Tabu - Algoritmo memético - Dissertação. Games logical reasoning. Nanogram. Taumaturgo, Camila Nascimento de Oliveira. Goldbarg, Elizabeth Ferreira Gouvêa. Universidade Federal do Rio Grande do Norte. Uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma /
description	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 x 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.#$&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 x 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.
format	Dissertação
author	Taumaturgo, Camila Nascimento de Oliveira. Goldbarg, Elizabeth Ferreira Gouvêa. Universidade Federal do Rio Grande do Norte.
author_facet	Taumaturgo, Camila Nascimento de Oliveira. Goldbarg, Elizabeth Ferreira Gouvêa. Universidade Federal do Rio Grande do Norte.
author_sort	Taumaturgo, Camila Nascimento de Oliveira.
title	Uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma /
title_short	Uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma /
title_full	Uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma /
title_fullStr	Uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma /
title_full_unstemmed	Uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma /
title_sort	uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma /
publishDate	2022
url	https://repositorio.ufrn.br/jspui/bitstream/123456789/18081/1/CamilaNOT_DISSERT.pdf
work_keys_str_mv	AT taumaturgocamilanascimentodeoliveira umainvestigacaodealgoritmosexatasemetaheuristicosaplicadosaonanograma AT goldbargelizabethferreiragouvea umainvestigacaodealgoritmosexatasemetaheuristicosaplicadosaonanograma AT universidadefederaldoriograndedonorte umainvestigacaodealgoritmosexatasemetaheuristicosaplicadosaonanograma
_version_	1766816496175022080

Uma investigação de algoritmos exatas e metaheurísticos aplicados ao nanograma /

Registros relacionados