Неуловимая загадка: как лучше всего нарезать рождественское печенье?

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

Как мы можем максимизировать тесто, вырезая рождественское печенье? Как упаковать чемодан или заполнить кухонный шкаф, максимально используя пространство? Кто-то мог подумать: «Должен быть лучший способ сделать это». Слишком глубокое размышление над такими вопросами сейчас кажется пустой тратой времени. Наука сейчас здесь, чтобы подтвердить, что в настоящее время невозможно выяснить, что лучше всего подходит для более чем четырех или пяти пряничных человечков или рождественского печенья.

Доцент Миккель Абрахамсен из факультета компьютерных наук и двое его коллег-исследователей изучали, насколько сложно найти оптимальный способ упаковки двухмерных объектов без перекрытия — загадка, над которой ученые-компьютерщики ломали голову десятилетиями.

«Хотя алгоритмы позволяют решать серьезные сложные проблемы, эта проблема остается слишком сложной для современных компьютеров. На данный момент невозможно оптимально упаковать более 5-10 объектов. И наш результат предполагает что это число, вероятно, пока не сильно увеличится », — объясняет Миккель Абрахамсен.

Оптимальная упаковка вещей — не просто случайная проблема дома, но и в самых разных отраслях, включая производство одежды и металлообработку. В любом случае важно вырезать материалы с минимальным количеством отходов. При транспортировке это касается упаковки контейнеров.

Всего четыре пряника

Нам известен размер самого маленького квадратного контейнера, в который мы можем упаковать до 10 квадратных поддонов размером 1×1 метр. Но просто добавив еще один поддон, невозможно рассчитать оптимальный размер контейнера. Абрахамсен объясняет:

«По мере добавления поддонов время вычислений увеличивается сверх экспоненциально. Даже самые лучшие компьютеры не могут справиться с этим. Теоретически это возможно. Но, судя по скорости роста вычислительной мощности, это, вероятно, займет миллионы лет, прежде чем мы можем оптимизировать обработку нескольких дополнительных объектов. «

Кроме того, если кто-то работает с более сложными формами, такими как пряники в форме рождественской елки, Миккель Абрахамсен говорит, что сегодня оптимальные решения можно найти только для четырех предметов.

Бесконечное количество вариантов

Что делает это таким сложным? Абрахамсен объясняет, что проблема аналогична решению уравнений пятой степени или выше и со многими неизвестными. Здесь известно, что такое решение не всегда можно записать с помощью обычных арифметических операций.

«Наше исследование доказывает, что проблема имеет характер, который мы в математике называем непрерывным, что в двух словах означает, что нужно знать все координаты, в которые можно размещать файлы cookie, и все углы под которые они могут вращаться «, — объясняет Абрахамсен.

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

Итак, на практике нет лучшего решения проблем с упаковкой, чем те, которые могут придумать люди.

«Как в промышленности, так и на кухне, мы должны продолжать довольствоваться нашими неоптимальными решениями и быть уверены, что мы, люди, по-прежнему лучше компьютеров для решения таких задач — на данный момент», — заключает Миккель Абрахамсен.

FACTS:

• В информатике и математике задачи упаковки — это класс задач оптимизации, которые включают попытку максимально упаковать несколько объектов в двух или трех измерениях. Математики занимались проблемами упаковки на протяжении сотен лет.
• С новым результатом задача двумерной упаковки перешла к более высокому классу вычислительной сложности, который обозначается как & exist; & # 8477 ;. Ранее считалось, что этот вопрос принадлежит классу NP вместе со знаменитой «задачей коммивояжера», которая касается расчета самого короткого маршрута для посещения всех городов в данном списке.
• Исследование проводилось Миккель Абрахамсен из Центра BARC Копенгагенского университета на факультете компьютерных наук; Тилльман Мильцов из Утрехтского университета в Нидерландах и Надя Зейферт из Свободного университета Берлина в Германии. Исследование получило финансирование, в том числе от фонда VILLUM.
• Исследование было представлено на конференции FOCS 2020 (симпозиум IEEE по основам компьютерных наук), которая пройдет с 16 по 19 ноября.