Вложение максимального количества фигур на поверхность

Question

В промышленности часто возникает проблема, когда вам нужно рассчитать наиболее эффективное использование материала, будь то ткань, дерево, металл и т. Д. Таким образом, отправной точкой является X количество форм заданные размеры, выполненные из полигонов и/или кривых линий, а цель - другой полигон заданных размеров.

Я предполагаю, что многие из существующих наборов CAM реализуют это, но не имея опыта использования их или их внутренних компонентов, какой вычислительный алгоритм используется для наиболее эффективного использования пространства? Может ли кто-нибудь указать мне на книгу или другую ссылку, которая обсуждает эту тему?

Answer 1

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

Это действительно проблема с упаковкой, а точнее, проблема с гнездом. Проблема математически NP-жесткая, и, следовательно, используемые в настоящее время алгоритмы являются эвристическими подходами. Кажется, не существует решений, которые могли бы решить проблему в линейном времени, за исключением тривиальных наборов задач. Решение сложных проблем занимает от минут до часа с использованием текущего оборудования, если вы хотите достичь решения с хорошим использованием материала. Существуют десятки коммерческих программных решений, которые предлагают вложение форм, но я не смог найти какие-либо решения с открытым исходным кодом, поэтому нет реальных примеров, где можно было бы увидеть, какие алгоритмы действительно реализованы.

Отличное описание проблемы гнездования и разложения лент с помощью исторических решений можно найти в статье, написанной Бенни Кьяром Нильсеном из Копенгагенского университета (Nielsen).

Общий подход состоит в том, чтобы смешивать и использовать несколько известных алгоритмов, чтобы найти лучшее решение для вложенности. Эти алгоритмы включают (Guided/Кратные) Локальный поиск, Быстрый поиск Район, который не основан на No-Fit Polygon и толкаются эвристики. Я нашел замечательную статью по этому вопросу с фотографиями о том, как работают алгоритмы. До сих пор он также имел контрольные показатели различных программных реализаций. Этот документ был представлен на Международном симпозиуме по планированию 2006 г. С. Уметани и др. (Umetani).

Относительно новые и, возможно, наилучший подход к настоящему времени основан на гибридных генетического алгоритма (С), гибрид, состоящий из имитации отжига и генетического алгоритма, который был описан Ву Цинмин и др. Из Уханьского университета (Quanming). Они реализовали это с помощью инструментария Visual Studio, базы данных SQL и инструментария оптимизации генетического алгоритма (GAOT) в MatLab.

Answer 2

Вы имеете в виду хорошо известную область информатики в области упаковки, для которой существует множество определенных задач и исследований, как для 2-мерного пространства, так и для 3-мерного пространства.

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

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

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