Un algoritmo para el Strip Packing Problem obtenido mediante la extracción de habilidades de expertos usando minería de datos
作者： Gatica Gustavo , Reyes Pablo , Contreras-Bolton Carlos , Linfati Rodrigo , Escobar John Willmer
DOI: 10.1016/J.RIIT.2016.06.003
关键词:
摘要: La capacidad del ser humano para resolver problemas NP-Duro de forma manual no ha recibido la debida atencion por comunidad cientifica. Este articulo considera el problema Strip Packing, que consiste en posicionar ortogonalmente un conjunto piezas rectangulares dentro contenedor ancho fijo y altura infinita, sin solaparlas, minimizando alcanzada las contenedor. Se desarrollo juego computacional permite obtener soluciones manuales, propuestas jugadores expertos, distintas instancias problema. contribucion presentar algoritmo se extrajo mediante patrones mineria datos aplicada a encontradas los expertos. El generado basa elementos arboles heuristicas presentes literatura. Adicionalmente presentan resultados computacionales, donde logra encontrar mejor solucion conocida 94.3% literatura 79% generadas aleatoriamente.
elsevier.es
core.ac.uk参考文章(15)
Mark A. Hall, Ian H. Witten, Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques ,(1999)
Kenneth A. De Jong, Alan C. Schultz, Using experience-based learning in game playing international conference on machine learning. pp. 284- 290 ,(1988) , 10.1016/B978-0-934613-64-4.50034-7
Mordechai (Moti) Ben-Ari, Minesweeper as an NP-complete problem technical symposium on computer science education. ,vol. 37, pp. 39- 40 ,(2005) , 10.1145/1113847.1113873
Daniel E. Acuña, Víctor Parada, People Efficiently Explore the Solution Space of the Computationally Intractable Traveling Salesman Problem to Find Near-Optimal Tours PLoS ONE. ,vol. 5, pp. e11685- ,(2010) , 10.1371/JOURNAL.PONE.0011685
R. Alvarez-Valdes, F. Parreño, J.M. Tamarit, Reactive GRASP for the strip-packing problem Computers & Operations Research. ,vol. 35, pp. 1065- 1083 ,(2008) , 10.1016/J.COR.2006.07.004
Andrea Lodi, Silvano Martello, Daniele Vigo, Recent advances on two-dimensional bin packing problems Discrete Applied Mathematics. ,vol. 123, pp. 379- 396 ,(2002) , 10.1016/S0166-218X(01)00347-X
E.K. Burke, G. Kendall, E. Soubeiga, A Tabu-Search Hyperheuristic for Timetabling and Rostering Journal of Heuristics. ,vol. 9, pp. 451- 470 ,(2003) , 10.1023/B:HEUR.0000012446.94732.B6
D Epstein, On the NP-completeness of cryptarithms Sigact News. ,vol. 18, pp. 38- 40 ,(1987) , 10.1145/24658.24662
Annick Dubois, Olivier Raymond, Marion Maene, Sylvie Baudino, Nicolas B. Langlade, Véronique Boltz, Philippe Vergne, Mohammed Bendahmane, Tinkering with the C-Function: A Molecular Frame for the Selection of Double Flowers in Cultivated Roses PLOS ONE. ,vol. 5, pp. 10- 1371 ,(2010) , 10.1371/JOURNAL.PONE.0009288
Guillermo Campitelli, Fernand Gobet, Amanda Parker, Structure and Stimulus Familiarity: A Study of Memory in Chess-Players with Functional Magnetic Resonance Imaging Spanish Journal of Psychology. ,vol. 8, pp. 238- 245 ,(2005) , 10.1017/S1138741600005126