1 resultado para constraint satisfaction
em Universidade Federal do Rio Grande do Norte(UFRN)
Filtro por publicador
- Repository Napier (1)
- Abertay Research Collections - Abertay University’s repository (1)
- Aberystwyth University Repository - Reino Unido (1)
- Academic Archive On-line (Stockholm University; Sweden) (1)
- Acceda, el repositorio institucional de la Universidad de Las Palmas de Gran Canaria. España (1)
- AMS Tesi di Dottorato - Alm@DL - Università di Bologna (6)
- AMS Tesi di Laurea - Alm@DL - Università di Bologna (3)
- Archivo Digital para la Docencia y la Investigación - Repositorio Institucional de la Universidad del País Vasco (3)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (17)
- Biblioteca Digital da Produção Intelectual da Universidade de São Paulo (BDPI/USP) (2)
- BORIS: Bern Open Repository and Information System - Berna - Suiça (95)
- Boston University Digital Common (2)
- Brock University, Canada (15)
- Bucknell University Digital Commons - Pensilvania - USA (3)
- Cambridge University Engineering Department Publications Database (27)
- CentAUR: Central Archive University of Reading - UK (39)
- Chinese Academy of Sciences Institutional Repositories Grid Portal (17)
- Cochin University of Science & Technology (CUSAT), India (3)
- Comissão Econômica para a América Latina e o Caribe (CEPAL) (2)
- CORA - Cork Open Research Archive - University College Cork - Ireland (3)
- CUNY Academic Works (3)
- Dalarna University College Electronic Archive (2)
- Deakin Research Online - Australia (233)
- Department of Computer Science E-Repository - King's College London, Strand, London (9)
- DI-fusion - The institutional repository of Université Libre de Bruxelles (1)
- Digital Archives@Colby (1)
- Digital Commons - Michigan Tech (1)
- Digital Commons @ DU | University of Denver Research (1)
- Digital Peer Publishing (2)
- DigitalCommons@The Texas Medical Center (13)
- Duke University (3)
- eResearch Archive - Queensland Department of Agriculture; Fisheries and Forestry (1)
- FAUBA DIGITAL: Repositorio institucional científico y académico de la Facultad de Agronomia de la Universidad de Buenos Aires (2)
- Gallica, Bibliotheque Numerique - Bibliothèque nationale de France (French National Library) (BnF), France (1)
- Greenwich Academic Literature Archive - UK (3)
- Helda - Digital Repository of University of Helsinki (6)
- Indian Institute of Science - Bangalore - Índia (32)
- Instituto Politécnico do Porto, Portugal (2)
- Lume - Repositório Digital da Universidade Federal do Rio Grande do Sul (1)
- Massachusetts Institute of Technology (6)
- Ministerio de Cultura, Spain (10)
- National Center for Biotechnology Information - NCBI (8)
- Portal de Revistas Científicas Complutenses - Espanha (1)
- Publishing Network for Geoscientific & Environmental Data (2)
- QUB Research Portal - Research Directory and Institutional Repository for Queen's University Belfast (75)
- Queensland University of Technology - ePrints Archive (153)
- ReCiL - Repositório Científico Lusófona - Grupo Lusófona, Portugal (1)
- Repositório Científico da Universidade de Évora - Portugal (2)
- Repositório Científico do Instituto Politécnico de Lisboa - Portugal (2)
- Repositório digital da Fundação Getúlio Vargas - FGV (3)
- Repositório Digital da UNIVERSIDADE DA MADEIRA - Portugal (1)
- Repositório do Centro Hospitalar de Lisboa Central, EPE - Centro Hospitalar de Lisboa Central, EPE, Portugal (1)
- Repositório Institucional da Universidade de Aveiro - Portugal (1)
- Repositório Institucional UNESP - Universidade Estadual Paulista "Julio de Mesquita Filho" (27)
- Research Open Access Repository of the University of East London. (1)
- RUN (Repositório da Universidade Nova de Lisboa) - FCT (Faculdade de Cienecias e Technologia), Universidade Nova de Lisboa (UNL), Portugal (6)
- School of Medicine, Washington University, United States (5)
- The Scholarly Commons | School of Hotel Administration; Cornell University Research (1)
- Universidad de Alicante (12)
- Universidad del Rosario, Colombia (4)
- Universidad Politécnica de Madrid (42)
- Universidade Complutense de Madrid (1)
- Universidade Federal do Rio Grande do Norte (UFRN) (1)
- Universitat de Girona, Spain (10)
- Universitätsbibliothek Kassel, Universität Kassel, Germany (3)
- Université de Lausanne, Switzerland (5)
- Université de Montréal, Canada (40)
- University of Connecticut - USA (4)
- WestminsterResearch - UK (4)
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