Математические модели задачи об упаковке единичных квадратов
Автор: Арсланов Марат Зуфарович
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая информатика
Статья в выпуске: 4 (29), 2015 года.
Бесплатный доступ
Одной из известных нерешенных проблем комбинаторной оптимизации является задача 56 в списке открытых проблем вычислительной геометрии The Open Problems Project http: //cs.smith.edu/~orourke/T0PP/P56.html: Packing Unit Squares in a Simple Polygon, формулировка которой заключается в выяснении вычислительной сложности задачи об упаковке единичных квадратов внутри простого многоугольника (т. е. многоугольника без дырок), когда необходимо разработать эффективные алгоритмы оптимальной упаковки единичных квадратов для различных односвязных областей. В статье разработаны математические модели, методы и алгоритмы решения задачи об упаковке единичных квадратов внутри различных односвязных областей, обобщающие известные в литературе.
Задача упаковки, математические модели, единичный квадрат
Короткий адрес: https://sciup.org/14320292
IDR: 14320292
Список литературы Математические модели задачи об упаковке единичных квадратов
- DYCKHOFF Н. A typology of cutting and packing problems//European Journal of Operational Research. 1990. V. 44. P. 145-160.
- ARSLANOV M. Z. A polynomial algorithm for one problem of guillotine cutting//Oper. Res. Let. 2007. V. 35. № 5. P. 636-644.
- ARSLANOV M.Z. Continued fractions in optimal cutting a rectangular sheet into equal small rectangles//European Journal of Operational Research. 2000. V. 125. P. 239-248.
- FOWLER R. J., PATERSON M.S. AND TANIMOTO S.L. Optimal packing and covering in the plane are NP-complete//Information Processing Letters. 1981. V. 12(3). P. 133-137.
- HOCHBAUM D. S. AND MAAS W. Approximation schemes for covering and packing problems in image processing and VLSI//Journal of Association of Computer Machinery. 1985. V. 32. P. 130-136.
- EL-KHACHEN D. Decomposing and Packing Problems. 2009. PhD thesis. Concordia University.
- ШТЕЙНГАУЗ Г. Задачи и размышления. М.: Мир, 1974.
- The Open Problems Project. : http://cs.smith.edu/~orourke/TOPP/. A project to record open problems of interest to researchers in computational geometry and related fields. 2011.
