211service.com
Wzór zagnieceń origami Udowodniono, że NP-Twardy
Około 20 lat różne osoby uznały, że problem składania kwadratowej kartki papieru w dowolny kształt 3D ma wiele podobieństw do problemów w geometrii obliczeniowej. Ci praktycy zaczęli opracowywać algorytmy, które automatycznie generują wzory fałd, które przekształcają płaski arkusz w wybrany przez Ciebie skomplikowany kształt. Dzięki temu oraz magicznej mocy nowoczesnych maszyn liczących origami przechodzi obecnie techniczną i twórczą rewolucję.
Ale ta nowa nauka o składaniu papieru doprowadziła do kilku zupełnie nowych zagadek. Po przekształceniu origami w problem informatyki nie minęło dużo czasu, zanim origamiści zaczęli zadawać sobie pytania przypominające informatykę. W szczególności chcą wiedzieć, jak trudne obliczeniowo jest origami. Dziś mają odpowiedź dzięki pracy Robert Lang , jeden ze światowych liderów origami obliczeniowego, i kilku jego kumpli: Eryk jutro w MIT i Sandor Fekete na Politechnice w Brunszwiku w Niemczech.
Proces projektowania origami jest koncepcyjnie prosty. Orygamiści zaczynają od kształtu, który ma zostać odtworzony – powiedzmy, pająka. Następnie przerysowują to jako postać z patyka składającą się w tym przypadku z ciała i ośmiu nóg.
Orygamiści wiedzą, że każdą kończynę można odtworzyć, składając w określony sposób kartkę papieru. Tak więc kluczowym krokiem w projektowaniu pająka origami jest znalezienie sposobu na złożenie kawałka papieru, aby wytworzył osiem klapek o odpowiednich rozmiarach i odstępach, po jednym na każdą nogę. Potem wystarczy ukształtować klapki, aby wyglądały na nogi, co jest stosunkowo prostym zadaniem.
Eksperci w tej dziedzinie od dawna podejrzewali, że proces przekształcania postaci z patyka we wzór zagnieceń jest niewykonalny obliczeniowo. Teraz Lang i spółka udowadniają słuszność tej intuicji, pokazując, że proces jest NP-trudny. O wiele trudniej więc wymyślić wzór fałd, który utworzy pająka, niż sprawdzić, czy dane rozwiązanie jest poprawne (np. przez złożenie go w pająka).
Zrobili to, używając standardowej sztuczki polegającej na pokazaniu, że problem origami jest równoważny z innym problemem, o którym już wiadomo, że jest NP-trudny, w tym przypadku problemem upakowania kół w danej przestrzeni.
Na pierwszy rzut oka trudno jest dostrzec, jak origami może być powiązane z pakowaniem w kółko, ale w rzeczywistości istnieje prosty związek. Wróć myślami do patyczkowej postaci pająka. Następnie narysuj okrąg wokół każdego węzła o promieniu równym połowie odległości od innego węzła. Problem origami, polegający na znalezieniu sposobu rozmieszczenia tych węzłów tak, aby kartkę można było złożyć w taki sposób, że każdy węzeł reprezentuje wierzchołek w ostatecznym kształcie, jest wtedy równoznaczny ze znalezieniem optymalnego sposobu pakowania kul.
Chociaż dowód nie będzie zaskoczeniem, ma ciekawy wniosek. W trakcie dokonywania tego przełomu Lang i współpracownicy pokazują, że każdy zestaw kół o łącznej powierzchni 1 można upakować w kwadrat o rozmiarze 8/pi = 2,546… Triumf origamiczny według czyichkolwiek standardów.
Nr ref.: arxiv.org/abs/1008.1224 : Pakowanie koła dla projektu Origami jest trudne