Сколько куки в коробке для печенья? - Черепица звезд

19

С приближением праздничного сезона я решил сделать несколько звезд с корицей . Это было весело (и результат вкусно), но мой внутренний ботаник съежился, когда я положил первый поднос со звездами в коробку, и они не поместились бы в один слой:

введите описание изображения здесь

Почти! Есть ли способ, которым они могли бы соответствовать? В любом случае, насколько хорошо мы можем изразить звезды? Учитывая, что это правильные шестиконечные звезды, мы, конечно, могли бы использовать известные шестиугольники в качестве приближения, например так:

введите описание изображения здесь
Перепутал один в верхнем правом углу.

Но так ли это оптимально? Между советами много места.

В связи с этим давайте ограничимся прямоугольными прямоугольниками и шестиконечными правильными звездами, т. Е. Между каждым наконечником и соседними уголками есть тридцать градусов (или ). Звезды характеризуются внутренним радиусом и внешним радиусом : гягOπ6riro

введите описание изображения здесь
[ источник ]

Обратите внимание, что у нас есть шестиугольники для и гексаграммы для . Я думаю, что разумно рассмотреть эти крайности (для файлов cookie) и ограничиться диапазоном между ними, т.е. .тя=1ri=32roтяri=13rorir0[13,32]

Мои печенья имеют и игнорируя недостатки - я собирался по вкусу, а не в форме ни разу!r o25 м мri17mmro25mm

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

Рафаэль
источник
1
Да, я знаю: что вы пробовали и где застряли? Это просто милая настоящая «проблема», о которой я подумал, что в сезоне печенья было бы интересно подумать, особенно для тех, кто мыслит, а не пекарь. Веселиться!
Рафаэль
4
Предположительно, вы застряли на глазури. На кухне. * rimshot *
Дэвид Ричерби

Ответы:

15

Позвольте мне ответить на ваш вопрос частично для случая гексаграммы.

Вы можете сделать следующую плитку

введите описание изображения здесь

Таким образом вы покроете 12/14 = 6/7 плоскости (считайте треугольники в пунктирном четырехугольнике).

Это оптимально? Я бы так подумал. Хотя я не даю доказательств, я приведу некоторые аргументы. Можно спросить, насколько хорошо мы можем заполнить пространство (треугольник) между острыми шипами. В вышеупомянутой плитке мы заполняем половину. Можем ли мы сделать лучше?

введите описание изображения здесь

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

sec2(x)23tan(x)+2.

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

введите описание изображения здесь

A.Schulz
источник
0

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

Во- первых, эта общая область известна / классифицируется как "упаковка бункера", и это 2-й случай. Есть некоторые известные доказательства из математики, которые связаны, например, с 3-м случаем исследования Кеплера в сфере упаковки сфер, которое веками было открытой проблемой и "недавно" решено с помощью компьютерного доказательства Хейлзом. Пример 2d случая, который ежедневно используется в промышленности, предназначен для оптимизации расположения чипов. очевидно, это отличается от проблемы, но может указывать на некоторые сложности этих типов проблем. например, не существует какой-либо теории, которая требует / указывает, что 2-мерный случай будет проще, чем 3-й случай. также отметим, что простая прямоугольная граница не обязательно помогает упростить решение, отличное от, скажем, полигональной границы.

аналитическое решение могло бы быть возможным, если бы в постановке задачи было дано какое-то базовое определение / схема «регулярного разбиения на листы», такое как размещение на сетке и т. д., в этом случае уравнения исчисления могли бы быть выводимыми и оптимально обнаруживаемыми.

условия задачи (возможно, нелогично), по-видимому, не приводят к аналитически оптимальному решению. это может быть удивительным для некоторых, но очень похожих проблем плиточного самолета, которые, как известно, неразрешимы (это был известный результат много лет назад, и есть много ссылок и даже продолжающихся исследований). ключевое различие между разрешимыми (решаемыми / аналитическими) и неразрешимыми проблемами заключается в том, является ли мозаика «регулярной». проблема выше относится к «обычным звездам», но не относится к «регулярным плиткам». другой текущий ответ предполагает своего рода регулярное разбиение или порядок, но обратите внимание, что даже определение «обычного разбиения» может быть очень сложным формально / математически.

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

Вот некоторые ссылки, которые обычно применимы:

ВЗН
источник
аналогичная теория см. также упаковку тетраэдров Чанг / Нью-Йорк Таймс. гипотеза (несколько вдохновленная статьей): для этой конкретной проблемы существует нерегулярная упаковка, которая превосходит любую обычную.
vzn
0

Хотя эта конкретная проблема, вероятно, не изучалась, такие вопросы были заданы Ласло Фейесом Тотом и известны как проблемы с упаковкой. Я настоятельно рекомендую третью главу книги Паха-Агарвала .

domotorp
источник
1
На самом деле это не ответ, а комментарий. Не могли бы вы обобщить, что цитируется в книге по этому вопросу и как она может применяться здесь?
Рафаэль