Задача об оптимальной раскройке материала.

[vedro-compota]

Здравствуйте, уважаемые программисты.

Собственно, хочу поинтересоваться -
не пытался ли кто программно решить проблему "оптимальной раскройки материала" - а именно хотелось бы понять в чём вообще суть проблемы этой самой раскройки! Видимо это что-то вроде .
Препод. задал товарищу вот такую задачу -

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

Возможно, кто-то знает решал подобные задачи - просьба написать в теме. (может у задачи есть какоето более научное название - "озвучте" его)
Заранее благодарю за ответы )
-----------------------------------------------
по теме здесь - цитирую оттуда -

Хотелось бы увидеть определение "оптимального раскроя".

[mv28jam]

Хотелось бы увидеть определение "оптимального раскроя".

Раскрой при котором потере в материале минимальны.

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

Задача достаточно сложная, если искать идеальное решение то нужен серьёзный мат аппарат. Если форма может быть любой и расположенной под любым углом, то надо с определённым шагом(сдвиг относительно прошлого положения) и поворотом(угол относительно начального положения) перебрать все возможные варианты и выбрать тот при котором незанятая площадь минимальна. Если форма фигуры может быть любой то задачу будет сложно оптимизировать. Если фигур будет больше 1 то задача станет в разы сложнее.

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

Какую часть то? При такой постановке задачи не понятно что нужно вообще.

[vedro-compota]

нужен серьёзный мат аппарат.

да. как говорят -

Где взять я не знаю, но алгоритм в общем виде не сложный, а его реализация невероятно сложная, похожий алгоритм был придуман ещё в 1932г (ну только ж не мной !

При такой постановке задачи не понятно что нужно вообще.

mv28jam, это тоже верно. У индивидуума (однокурсник)) которому эту задачу задали ничего конкретного узнать не получается - сам уточню у препода ,чего последний хочет - надеюсь что не типа "любую форму разместить на любой форме с минимальными отходами....."

[mihali4]

А в инете поискать ?
http://www.sapr.ru/article.aspx?id=18388&iid=851

[vedro-compota]

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

А в инете поискать ?
http://www.sapr.ru/article.aspx?id=18388&iid=851

Спасибо)) читаю...

[Virtson]

Используйте Генетические алгоритмы.
Проверены на подобных задачах.

[vedro-compota]

Спасибо,Virtson.