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