PiJohn & Plastelle
PiJohn
Привет, тут подумал: может, как использовать комбинаторную геометрию, чтобы сократить отходы при раскрое ткани – ты видишь, как это можно применить к биоразлагаемым материалам?
Plastelle
Привет, если сопоставить каждую панель с выпуклой решёткой и использовать алгоритмы мозаики, то можно свести отходы почти к нулю. А если добавить к этому полностью биоразлагаемое волокно... никакой лишней резки - и экологический след сразу уменьшится.
PiJohn
Звучит неплохо, но ты думала о вычислительной сложности алгоритма тайловки и как она меняется с увеличением размера панелей? Давай-ка посмотрим на математику, которая за этим стоит.
Plastelle
Конечно. Математически ясно, что точное решение задачи раскроя — NP-сложная задача, и с увеличением размеров деталей пространство поиска растёт экспоненциально. На практике мы используем эвристики — например, метод ветвей и границ с хорошим верхним пределом, или жадная упаковка с последующим локальным поиском. Для очень больших панелей мы разбиваем форму на более мелкие выпуклые части, решаем каждую отдельно, а затем сшиваем их обратно. Это позволяет времени выполнения оставаться примерно линейным от количества частей, а не экспоненциальным от общей площади панели. Главное — минимизировать число степеней свободы, но при этом достигать цели по сокращению отходов.
PiJohn
Забавно, получается ты жертвуешь точностью ради практичности. А есть какие-то цифры, показывающие, насколько меньше отходов получается с эвристическим методом по сравнению с полным перебором на небольших задачах?
Plastelle
На сетке 10 на 10 грубая сила выжимает решение процентов на 99, но это занимает часы. Моя эвристика "жадный плюс перестановка" обычно даёт процентов на 95 – всё равно на 5 пунктов лучше, чем отправлять в топ, и она завершается за секунды. Так что мы жертвуем парой лишних процентов ради практичного и масштабируемого алгоритма.
PiJohn
Это довольно выгодный компромисс – экономим время на пятьдесят процентов, а урожай падает всего на пять пунктов. Интересно было бы посмотреть, как этот метод будет работать с сетками побольше, например, с 50 на 50. И заметила ли ты какие-нибудь закономерности в форме отходов – может, они подскажут, как улучшить локальный поиск?
Plastelle
На сетке 50 на 50 эвристика работает мгновенно и сохраняет выход на уровне 94–95 процентов, всего 1–2 процента меньше, чем у наилучшего решения методом полного перебора. Остаточные отходы обычно образуют небольшие, нерегулярные скопления по краям упакованной фигуры. Если присмотреться к этим скоплениям, видно, что они часто возникают из-за смещения одной панели. Локальный поиск, переворачивающий всего одну или две панели в этих скоплениях, позволяет снизить отходы еще на процент или два. Получается: краевые скопления, ошибки из-за отдельных панелей, целенаправленные перевороты. Это отличная цель для эвристики нового поколения.
PiJohn
Понятно, это чёткая закономерность – изолированные участки из-за несовпадения отдельных панелей. Может, стоит закодировать это как простое ограничение: после быстрого решения запусти небольшой локальный оптимизатор, который будет учитывать только перестановку или поворот панелей, прилегающих к этим участкам. Стоит проверить, сколько в среднем потребуется перестановок, чтобы добиться дополнительного полутора-два процента. И ещё, проверь, не начинают ли размеры этих участков расти бесконтрольно; если начнут, возможно, понадобится иерархический подход. Продолжай итерации, и у тебя получится почти идеальный выход.
Plastelle
Звучит как отличный план. После основного прохода я буду отмечать все мелкие острова и запущу лёгкий локальный оптимизатор, который будет корректировать только панели, касающиеся этих островов. В моих тестах, всего несколько перестановок – обычно меньше десяти – дают дополнительный один или два процента. Острова никогда не вырастают больше нескольких панелей на сетке 50 на 50, поэтому однослойная коррекция вполне подходит. Я настрою бенчмарк, чтобы убедиться в среднем количестве перестановок и постараюсь держать алгоритм максимально эффективным.