Каггл «200 ёлочек 2025»: призы уже раздали, но мы и за идею задачу укладки порешаем. Часть 1

[ChePeter]

А разве Канторовича уже запретили ?

[Andrey_mazo]

Канторовича чтим и помним, но классическое линейное программирование (ЛП) и целочисленное программирование ломают зубы о невыпуклые полигоны (те самые «ёлочки» сложной формы) и свободное вращение деталей.

Чтобы описать укладку 200 сложных геометрических объектов через систему линейных неравенств Канторовича, потребуется такое количество переменных и ограничений, что комбинаторный взрыв случится раньше, чем алгоритм выдаст первый шаг. Поэтому для сложной 2D-геометрии «кожа к коже» эвристика вроде Front-Propagation и Shapely на практике оказывается эффективнее и быстрее.

[noker81]

Хаотичное расположение елочек, по повлекло ли за собой уменьшение скорости производства?

[Andrey_mazo]

Приветствую! Отличный вопрос. Давайте я покажу контекст на примере.

Если посмотреть на официальный Getting Started ноутбук от организаторов Kaggle — вот там действительно хаос https://www.kaggle.com/code/inversion/santa-2025-getting-started. Детали просто раскиданы по сетке, чтобы показать механику конкурса. В моём же случае хаоса минимум — я, скорее, наоборот, привожу всё к жесткому порядку.

Если рассуждать философски, то за фазой войны или пожара всегда следует фаза рождаемости и произрастания. На этом дуализме и построен наш «трехфазный термодинамический двигатель раскроя».

Мы сначала «отжигаем» (даем деталям хаотично найти первые зацепки), затем «закаливаем» (стягиваем их в монолит) и совмещаем в единое целое. По сути — кристаллизуем Материк.

Дальше, если время и силы останутся, можно внедрить еще пару фаз и продолжать телебонить алгоритм, еще ближе продвигаясь к идеальному результату. Так что для реального лазера наш «хаос» гораздо дружелюбнее, чем то, что выдают стандартные подходы на соревнованиях!