Вложенная максимальная сумма форм на поверхности
В промышленности часто существует проблема, где необходимо вычислить наиболее эффективное использование материала, быть ею матрица, древесина, металл и т.д. Таким образом, начальная точка является X суммами форм данных размеров, сделанных из полигонов и/или кривых линий, и цель является другим полигоном данных размеров.
Я предполагаю, что многие текущие комплекты CAM реализуют это, но имеющий опыт с помощью них или их внутренностей, какой вычислительный алгоритм используется для нахождения наиболее эффективного использования пространства? Кто-то может указать на меня на книгу или другую ссылку, которая обсуждает эту тему?
2 ответа
После того, как Эндрю в своем ответе указал мне правильное направление и назвал проблему за меня, я решил выложить здесь результаты своих исследований в виде отдельного ответа.
Это действительно проблема упаковки, а точнее, проблема вложенности. Задача является математически NP-сложной, и поэтому используемые в настоящее время алгоритмы представляют собой эвристические подходы. Кажется, что нет никаких решений, которые решали бы проблему за линейное время, за исключением тривиальных наборов задач. Решение сложных проблем с использованием современного оборудования занимает от минут до часов, если вы хотите найти решение с хорошим использованием материала. Существуют десятки коммерческих программных решений, которые предлагают вложение фигур, но мне не удалось найти никаких решений с открытым исходным кодом, поэтому нет реальных примеров, где можно было бы увидеть, как действительно реализованы алгоритмы.
Прекрасное описание проблемы вложенности и раздельного вложения с историческими решениями можно найти в статье, написанной Бенни Кьером Нильсеном из Копенгагенского университета ( Nielsen ).
Общий подход, по-видимому, заключается в смешивании и использовании нескольких известных алгоритмов, чтобы найти лучшее решение для вложения.Эти алгоритмы включают в себя (управляемый / итерационный) локальный поиск , быстрый поиск соседства , который основан на многоугольнике неподходящего размера , и эвристике Джостлинга . Я нашел отличную статью на эту тему с изображениями того, как работают алгоритмы. До сих пор он также имел тесты различных программных реализаций. Этот документ был представлен на Международном симпозиуме по планированию в 2006 г. С. Уметани и др. ( Уметани ).
Относительно новый и, возможно, лучший подход на сегодняшний день основан на гибридном генетическом алгоритме (HGA), гибриде, состоящем из моделированного отжига и генетического алгоритма это было описано Wu Qingming и др. из Уханьского университета ( Quanming ). Они реализовали это с помощью Visual Studio, базы данных SQL и инструментария оптимизации генетических алгоритмов (GAOT) в MatLab.
Вы имеете в виду хорошо известную область информатики упаковки, для которой определено множество задач и проведены исследования как для двумерного пространства. а также 3-х мерное пространство.
В сети имеется значительный материал, доступный по определенным проблемам, но чтобы найти его, вы должны знать название проблемы, которую нужно искать.
Некоторые пакеты вполне могут принять эвристическую оценку (что, я подозреваю, так и будет), а некоторые могут пойти на самое большое вычисление всех возможностей для получения абсолютно правильного ответа.