Ile ciasteczek w polu ciasteczek? - Dachówka gwiazd


19

W związku z nadchodzącym okresem świątecznym postanowiłem zrobić gwiazdy cynamonu . To było zabawne (a wynik smaczny), ale mój wewnętrzny kujon skurczył się, gdy włożyłem pierwszą tacę gwiazd do pudełka i nie zmieściłyby się w jednej warstwie:

wprowadź opis zdjęcia tutaj

Prawie! Czy istnieje sposób, w jaki mogliby pasować? Jak dobrze potrafimy kafelkować gwiazdy? Biorąc pod uwagę, że są to zwykłe sześcioramienne gwiazdy, z pewnością moglibyśmy użyć dobrze znanych sześciokątnych pochyłości jako przybliżenia, jak na przykład:

wprowadź opis zdjęcia tutaj
Zepsuty ten w prawym górnym rogu, ups.

Ale czy to jest optymalne? Pomiędzy wskazówkami jest dużo miejsca.

W tym celu ograniczmy się do prostokątnych pudeł i sześcioramiennych, regularnych gwiazd, tj. Pomiędzy każdą końcówką a sąsiednimi zakątkami są trzydzieści stopni (lub ). Gwiazdy charakteryzują się wewnętrznym promieniem i zewnętrznym promieniem :π6rjaro

wprowadź opis zdjęcia tutaj
[ źródło ]

Zauważ, że mamy sześciokąty dla i heksagramy dla . Myślę, że uzasadnione jest wzięcie pod uwagę tych ekstremów (w przypadku plików cookie) i ograniczenie się do zakresu pomiędzy, tj. .rja=3)2)rorja=13)rorjar0[13),3)2)]

Moje ciasteczka mają i ignorując niedoskonałości - szedłem po smak, a nie formę raz!rja17mmro25mm

Jakie jest optymalne kafelkowanie gwiazd, jak opisano powyżej? Jeśli nie ma statycznego najlepszego kafelkowania, czy istnieje algorytm umożliwiający skuteczne znalezienie dobrego kafelka?


1
Tak, wiem: czego próbowałeś i gdzie utknąłeś? To po prostu uroczy „problem” na żywo, o którym myślałem, że fajnie jest myśleć w sezonie ciasteczek, szczególnie dla tych, którzy są myślicielami, a nie piekarzami. Baw się dobrze!
Raphael

4
Przypuszczalnie utknąłeś w lukrze. W kuchni. * rimshot *
David Richerby,

Odpowiedzi:


15

Pozwól, że częściowo odpowiem na twoje pytanie dotyczące przypadku heksagramu.

Możesz wykonać następujące kafelki

wprowadź opis zdjęcia tutaj

Przez to pokryjesz 12/14 = 6/7 samolotu (policz trójkąty w przerywanym czworoboku).

Czy to jest optymalne? Tak myślałbym. Chociaż nie przedstawię dowodu, przedstawię kilka argumentów. Można zapytać, jak dobrze możemy wypełnić przestrzeń (trójkąt) pomiędzy spiczastymi kolcami. W powyższym kafelku wypełniamy jego połowę. Czy możemy zrobić lepiej?

wprowadź opis zdjęcia tutaj

Możliwe, że dwa heksagramy przecinają tę przestrzeń, ale wtedy zajmują bardzo mało jej powierzchni (bez dowodu). Jeśli przecina się tylko jeden heksagram, zakładam, że jego końcówka dotyka wklęsłego rogu drugiego heksagramu, jak pokazano na zdjęciu. Jeśli tak nie jest, możemy to poprawić, przenosząc przecinający się heksagram do tego rogu (znowu nie ma tutaj dowodu). Przy tych założeniach nietrudno dostrzec, że przypadek, w którym występuje kontakt boczny, maksymalizuje przecięcie. Jeśli wykonasz matematykę, przekonasz się, że obszar przecięcia jest równy

sec2)(x)2)3)dębnik(x)+2).

Fabuła tej funkcji wygląda tak i pokazuje, że nasza intuicja miała rację.

wprowadź opis zdjęcia tutaj


0

Poniższy artykuł nie jest oferowany jako ostateczny lub specyficzny / lepszy atak na ten prawdopodobnie nieoczekiwanie złożony problem, ale jako dodatkowe kąty naukowe / teoretyczne / badania ogólne, które nie zostały do ​​tej pory uwzględnione.

1 st ta ogólna powierzchnia jest znany / sklasyfikowany jako „bin pakowania” i jest to sprawa 2d. istnieją pewne znane dowody matematyczne, które są powiązane, np. 3d przypadek dochodzenia Keplerów w sprawie pakowania sfer, który był otwartym problemem przez wieki i „niedawno” rozwiązany za pomocą komputerowego dowodu przez Halesa. przykładowym przypadkiem 2d stosowanym codziennie w przemyśle jest optymalizacja układów czipów. to oczywiście różni się od problemu, ale może wskazywać na złożoność tego rodzaju problemów. na przykład nie wydaje się, aby istniała jakaś teoria, która wymagałaby / wskazuje, że przypadek 2d byłby prostszy niż przypadek 3d. zauważ także, że prosta prostokątna granica niekoniecznie pomaga uprościć rozwiązanie inne niż, powiedzmy, granica wieloboczna.

mogłoby być możliwe rozwiązanie analityczne, gdyby w opisie problemu podano jakąś podstawową definicję / schemat „regularnego układania płytek”, taką jak umieszczenie na siatce itp., w którym to przypadku równania rachunku różniczkowego mogą być możliwe do wyprowadzenia i można je znaleźć optymalnie.

warunki problemu (być może sprzeczne z intuicją) nie wydają się prowadzić do optymalnego rozwiązania analitycznego. może to być zaskakujące dla niektórych, ale bardzo podobnych problemów związanych z kafelkami samolotu, o których wiadomo, że są nierozstrzygalne (był to słynny wynik lata temu i istnieje wiele referencji, a nawet trwających badań). kluczową różnicą między rozstrzygającymi (rozwiązanymi / analitycznymi) a nierozstrzygalnymi problemami jest to, czy układanie płytek jest „regularne”. powyższy problem dotyczy „zwykłych gwiazd”, ale nie odnosi się do „regularnego układania płytek”. druga aktualna odpowiedź zakłada rodzaj regularnego kafelkowania lub porządku, ale zauważ, że nawet zdefiniowanie „regularnego kafelkowania” może być bardzo trudne pod względem formalnym / matematycznym.

problemy takie jak ten są na ogół podatne na algorytmy genetyczne . taki algorytm może znaleźć „bardzo dobre” pakiety, które prawdopodobnie nie zostaną znacznie poprawione, i być może pewne granice mogą zostać nałożone na ich optymalność za pomocą bardzo pomysłowych metod (tj. muszą zawierać się w granicach procentowego błędu optymalnego), ale nie mogą udowodnić żadnego są optymalne.

oto niektóre znalezione referencje, które zasadniczo mają bezpośrednie zastosowanie:


podobna teoria patrz także pakowanie czworościanów przez Chang / NYT. domysł (nieco zainspirowany artykułem): w przypadku tego konkretnego problemu istnieje nieregularne opakowanie, które jest lepsze od każdego zwykłego.
vzn

0

Chociaż ten konkretny problem prawdopodobnie nie został zbadany, Laszlo Fejes Toth zadał takie pytania i są znane jako problemy z pakowaniem. Zdecydowanie polecam trzeci rozdział książki Pach-Agarwal .


1
W tej chwili nie jest to odpowiedź, ale komentarz. Czy możesz streścić, co zawiera cytowana książka na ten temat i jak może ona mieć zastosowanie tutaj?
Raphael
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.