Максимальная упаковка прямоугольников в круге - PullRequest
Новая
       22

Максимальная упаковка прямоугольников в круге

9 голосов
/ 13 октября 2010

Я работаю в нанотехнологической лаборатории, где занимаюсь нарезкой кремниевых пластин.(Вафельная пила режет только параллельные линии) Мы, конечно же, пытаемся максимизировать производительность режущей матрицы.Все кубики будут одинакового размера, прямоугольные или квадратные, и все кубики будут вырезаны из круглой пластины.По сути, я пытаюсь упаковать максимальное количество прямоугольников в круг.

У меня есть только довольно базовое понимание MATLAB и промежуточное понимание исчисления.Есть ли какой-нибудь (относительно) простой способ сделать это, или я над головой?

Ответы [ 4 ]

1 голос
/ 23 февраля 2011

Я был очарован, чтобы прочитать ваш вопрос, потому что я сделал проект по этому вопросу для моей подготовки в качестве учителя математики. Мне также очень приятно знать, что это проблема NP, потому что мой проект привел меня к тому же выводу.

Используя базовое исчисление, я вычислил первые несколько «поколений» прямоугольников максимального размера, но они довольно быстро становятся сложными.

Мой проект вы можете прочитать здесь:

Беккет, Р. Посылки Пи: проблема с кривой упаковки . Баня Spa MEC. 2009

Я надеюсь, что некоторые из моих находок будут полезны для вас или, по крайней мере, интересны. Я думал, что применение этой идеи, скорее всего, будет в компьютерных нано технологиях.

С уважением.

1 голос
/ 15 октября 2010

Идите отсюда и удачи:

http://en.wikipedia.org/wiki/Knapsack_problem

и получите здесь:

http://www -sop.inria.fr / mascotte/WorkshopScheduling/2Dpacking.pdf

По крайней мере, у вас будет некоторое представление о том, что вы решаете здесь.

0 голосов
/ 16 ноября 2010

это не похоже на проблему круга Гаусса?См. http://mathworld.wolfram.com/GausssCircleProblem.html

или это можно рассматривать как «проблему упаковки» http://en.wikipedia.org/wiki/Packing_problem#Squares_in_circle

0 голосов
/ 15 октября 2010

Упаковка произвольных прямоугольников в круг для достижения цели эффективности пространства является невыпуклой (NP-Hard) оптимизацией в целом. Это означает, что не будет элегантного или простого решения, которое бы решало эту проблему оптимально. Все методы решения будут зависеть от конкретных знаний предметной области, которые вы можете использовать для сокращения дерева поиска или разработки эвристики. Если у вас нет опыта решения подобных проблем, вам, вероятно, следует проконсультироваться с экспертом.

...