Математические модели задачи об упаковке единичных квадратов

Автор: Арсланов Марат Зуфарович

Журнал: Проблемы информатики @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://readera.ru/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.
Статья научная