Версия для печати темы

Автор: tolmach 9.7.2008, 8:01

Добрый день!
Помогите решить задачу фигурного кроя! Все знают об алгоритме размещения прямоугольных объектов на плоскости, однако каково может быть решение размещение объектов со сложными кривыми? Сделал алгоритм укрупнения и упрощения объектов, однако требуемой точности достичь не удалось!
Возможно кто-то уже сталкивался с такой задачей? Какие есть мысли?

Автор: Руководитель проекта 9.7.2008, 12:06

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

Автор: AlexDemche 30.7.2008, 16:43

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

А по задаче размещения прямоугольников на прямоугольном листе какой алгоритм Вы имеете ввиду?

Дело в том, что это задача тоже не простая. Во-первых, она NP-полная. Поэтому точный алгоритм решения весьма трудоемок по времени.
Мне известен алгоритм, основанный на методе ветвей и границ, но по известным мне исследованиям он раскладывает на достаточно сильном ПК за несколько часов всего 20 деталей. Хороших эвристик вроде бы особо-то нет.

Так что на самом-то деле, с прямоугольниками задачка остается открытой.
Открытой в каком смысле. К этой задаче, если говорить с точки зрения экономики, приводят практические задачи промышленного раскроя. Когда есть лист железа, к примеру. И на нем нужно разместить заготовки - чтобы потом их нарезать. И алгоритм, который раскладывает всего 20 деталей промышленности, видимо не устраивает.

Замечу, что когда, я говорю, о задаче размещения, я не говорю ни о какой оптимизации - нужно просто разложить - и эта задача является NP-полной.