Using Relaxations in Maximum Density Still Life
作者： Geoffrey Chu , Peter J. Stuckey , Maria Garcia de la Banda
DOI: 10.1007/978-3-642-04244-7_22
关键词:
摘要: The Maximum Density Sill-Life Problem is to fill an n × board of cells with the maximum number live so that stable under rules Conway's Game Life. We reformulate problem into one minimising "wastage" rather than maximising cells. This reformulation allows us compute strong upper bounds on By combining this several relaxation techniques, as well exploiting symmetries via caching, we are able find close optimal solutions up size = 100, and for instances large 69. best previous method could only 20.
springer.com
sci-hub.st 参考文章(6)
Javier Larrosa, Rina Dechter, Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems Constraints - An International Journal. ,vol. 8, pp. 303- 326 ,(2003) , 10.1023/A:1025627211942
Noam David Elkies, The Still-Life Density Problem and its Generalizations Voronoi's Impact on Modern Science, Book I. ,(1998)
Robert Bosch, Michael Trick, Constraint Programming and Hybrid Formulations for Three Life Designs Annals of Operations Research. ,vol. 130, pp. 41- 56 ,(2004) , 10.1023/B:ANOR.0000032569.86938.2F
Robert A. Bosch, Integer Programming and Conway's Game of Life SIAM Review. ,vol. 41, pp. 594- 604 ,(1999) , 10.1137/S0036144598338252
J. Larrosa, E. Morancho, D. Niso, On the practical use of variable elimination in constraint optimization problems: 'still-life' as a case study Journal of Artificial Intelligence Research. ,vol. 23, pp. 421- 440 ,(2005) , 10.1613/JAIR.1541
Rina Dechter, None, Constraint Processing ,(2003)