Ile ciasteczek w polu ciasteczek? - Dachówka gwiazd

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:

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:

^{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 :$\frac{\pi}{6}$$r_i$$r_o$

^{[ ź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. .$r_i = \frac{\sqrt{3}}{2} \cdot r_o$$r_i = \frac{1}{\sqrt{3}} \cdot r_o$$\frac{r_i}{r_0} \in \Bigl[\frac{1}{\sqrt{3}}, \frac{\sqrt{3}}{2}\Bigr]$

Moje ciasteczka mają i ignorując niedoskonałości - szedłem po smak, a nie formę raz!$r_i \approx 17\mathrm{mm}$$r_o \approx 25\mathrm{mm}$

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?

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

Możesz wykonać następujące kafelki

$\hskip1.2in$

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?

$\hskip20mm$

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

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

$\hskip30mm$

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:

• przykładowe zastosowanie algorytmów genetycznych. Algorytmy genetyczne do pakowania wielokątów / Jacobsa

• Algorytmy dla problemów z pakowaniem geometrycznym i skalowaniem Praca doktorska / Michael Formann 1992, 92p, s 3.6 Skalowanie obiektów w kształcie gwiazdy monotonicznej p30

• GEOMETRYCZNY ALGORYTM OPAKOWAŃ NA KUCHNIE ARBITRAŻOWE / ARFATH PASHA 2003 Praca dyplomowa 87p

• to pytanie dotyczące wymiany stosów jest również bliskie. pakowanie dowolnych wielokątów w dowolną granicę . jest dla arbitralnych granic

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 .