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

Конечно. Математически ясно, что точное решение задачи раскроя — NP-сложная задача, и с увеличением размеров деталей пространство поиска растёт экспоненциально. На практике мы используем эвристики — например, метод ветвей и границ с хорошим верхним пределом, или жадная упаковка с последующим локальным поиском. Для очень больших панелей мы разбиваем форму на более мелкие выпуклые части, решаем каждую отдельно, а затем сшиваем их обратно. Это позволяет времени выполнения оставаться примерно линейным от количества частей, а не экспоненциальным от общей площади панели. Главное — минимизировать число степеней свободы, но при этом достигать цели по сокращению отходов.

На сетке 10 на 10 грубая сила выжимает решение процентов на 99, но это занимает часы. Моя эвристика "жадный плюс перестановка" обычно даёт процентов на 95 – всё равно на 5 пунктов лучше, чем отправлять в топ, и она завершается за секунды. Так что мы жертвуем парой лишних процентов ради практичного и масштабируемого алгоритма.

На сетке 50 на 50 эвристика работает мгновенно и сохраняет выход на уровне 94–95 процентов, всего 1–2 процента меньше, чем у наилучшего решения методом полного перебора. Остаточные отходы обычно образуют небольшие, нерегулярные скопления по краям упакованной фигуры. Если присмотреться к этим скоплениям, видно, что они часто возникают из-за смещения одной панели. Локальный поиск, переворачивающий всего одну или две панели в этих скоплениях, позволяет снизить отходы еще на процент или два. Получается: краевые скопления, ошибки из-за отдельных панелей, целенаправленные перевороты. Это отличная цель для эвристики нового поколения.