Algoritmos Genéticos Basados en Criterios para rompecabezas NP-Completos

• Gindre, Francisco ^[1] ; Jafelle, Nicolás ^[1] ; Kotlirevsky, David ^[1] ; Scaine, Santiago ^[1] ; Trejo Pizzo, David ^[1] ; Barrera, Gabriel ^[1] ; López De Luise, Daniela ^[1]
  1. [1] Universidad de Palermo
• Localización: Ciencia y tecnología, ISSN 1850-0870, ISSN-e 2344-9217, Nº. 12, 2012, págs. 105-116
• Idioma: español
• DOI: 10.18682/cyt.v1i12.653
• Enlaces
  • Texto completo
• Resumen
  • español

    El objetivo principal de esta investigación es desarrollar un Sistema Inteligente Robotizado (SIR) resuelva un rompecabezas desconocido en un lapso de tiempo reducido. SIR aplica técnicas de reconocimiento de patrones junto con Algoritmos Genéticos. Investigando el estado del arte, la naturaleza NP-Completa del problema aparece como el común denominador. SIR se basa en esas experiencias para aportar una nueva aproximación al problema. Este enfoque involucra la conversión del puzzle a un modelo de Teoría de Grafos. El estudio de este modelo sumado a la inclusión de una analogía y enfoque de solución diferentes son los principales aportes de este trabajo. A su vez describe marcos teóricos y prácticos y el estado actual del proyecto y el trabajo a futuro.

  • English

    The primary goal of this research is to develop an Intelligent Robotic System (SIR in Spanish) that solves unknown jigsaw puzzles in a reduced amount of time. This model applies pattern recognition techniques and feature detection in conjunction with Genetic Algorithms. It relies on the knowledge of authors as a working base for a new approach to the problem; involving a conversion of the puzzle model to a Graph Theory model.