Logotipo del repositorio
  • English
  • Español
  • Iniciar sesión
    ¿Nuevo Usuario? Pulse aquí para registrarse¿Has olvidado tu contraseña?
Logotipo del repositorio
  • ¿Qué es SIC?
  • Estadísticas
  • Guía de Usuario
  • English
  • Español
  • Iniciar sesión
    ¿Nuevo Usuario? Pulse aquí para registrarse¿Has olvidado tu contraseña?
  • Inicio
  • Personal de Investigación
  • Unidad Académica
  • Publicaciones
  • Colecciones
    • Datos de investigación
    • Divulgación Científica
    • Personal de investigación
    • Protecciones
    • Proyectos externos
    • Proyectos internos
    • Publicaciones
    • Tesis
  1. Inicio
  2. Universidad de Santiago de Chile
  3. Publicaciones
  4. Un algoritmo para el Strip Packing Problem obtenido mediante la extracción de habilidades de expertos usando minería de datos
 
  • Details
Options

Un algoritmo para el Strip Packing Problem obtenido mediante la extracción de habilidades de expertos usando minería de datos

ISSN
1405-7743
Date Issued
2016
Author(s)
Contreras-Bolton, C 
Departamento de Ingeniería Informática 
Escobar, John Willmer
Gatica, Gustavo
Linfati, Rodrigo
Reyes, Pablo
Abstract
Abstract: The ability of the humans to manually solve NP-hard problems had not received much attention of the scientific community. This paper considers the Strip Packing Problem (SPP), in which a set of rectangular pieces has to be placed orthogonally in a container with a given width and an infinite length. The pieces are not allowed to overlap (i.e. be stacked one over the other). The aim of the SPP is to minimize the overall length of the strip. In this paper, we have developed a computational game to allow manual solutions by expert gamers for different instances of the problem. The main contribution of the paper is the presentation of an algorithm based on patterns and data mining retrieved from the results achieved by expert gamers. The proposed algorithm is based on decision-trees and heuristics proposed in literature. Finally, the proposed approach is able to find the best-known solutions for the 94.3% of a set of instances proposed in the literature, and 79% for instances generated randomly.
Subjects

Strip Packing Problem...

data mining of algori...

skills of experts

...
Universidad de Santiago de Chile Avenida Libertador Bernardo O'Higgins nº 3363. Estación Central. Santiago Chile. admin.dspace@usach.cl © 2023 The DSpace CRIS Project - Modificado por VRIIC USACH.
...