Origami kroku raksta dizains izrādījās NP-ciets

Apmēram 20 gadus dažādi cilvēki saprata, ka kvadrātveida papīra loksnes salocīšanas problēmai patvaļīgā 3D formā ir daudz līdzību ar skaitļošanas ģeometrijas problēmām. Šie praktiķi sāka izstrādāt algoritmus, kas automātiski ģenerē krokas, kas pārvērš plakanu loksni sarežģītā formā pēc jūsu izvēles. Pateicoties tam un moderno skaitļošanas iekārtu maģiskajam spēkam, origami šobrīd piedzīvo tehnisku un radošu revolūciju.

Taču šī jaunā papīra locīšanas zinātne ir radījusi pilnīgi jaunas problēmas. Pārvēršot origami par datorzinātņu problēmu, nepagāja ilgs laiks, kad origamisti sāka sev uzdot datorzinātnei līdzīgus jautājumus. Jo īpaši viņi vēlas uzzināt, cik skaitļošanas grūtības patiesībā ir origami. Šodien viņiem ir atbilde, pateicoties darbam Roberts Lengs , viens no pasaules līderiem skaitļošanas origami jomā un pāris viņa draugi: Ēriks rīt MIT un Šāndors Fekete Braunšveigas Tehnoloģiju universitātē Vācijā.

Origami dizaina process ir konceptuāli vienkāršs. Origamisti sāk ar formu, kas jāveido no jauna, piemēram, zirnekļa forma. Pēc tam viņi to pārzīmē kā figūriņu, kas šajā gadījumā sastāv no ķermeņa un astoņām kājām.

Origamisti zina, ka katru ekstremitāti var atveidot, īpašā veidā salokot papīra atloku. Tāpēc galvenais solis origami zirnekļa projektēšanā ir atrast veidu, kā salocīt papīra lapu tā, lai izveidotu astoņus piemērota izmēra atlokus, pa vienam katrai kājai. Pēc tam atliek tikai veidot atlokus, lai tie izskatītos kājveidīgi, un tas ir samērā vienkāršs uzdevums.

Šīs jomas speciālistiem jau sen ir aizdomas, ka nūjas figūriņas pārvēršana kroku paraugā ir skaitļošanas ziņā grūti izpildāma. Tagad Langs un kolēģi pierāda, ka šī intuīcija ir pareiza, parādot, ka process ir NP grūts. Tāpēc ir daudz grūtāk izveidot kroku modeli, kas rada zirnekli, nekā pārbaudīt, vai dotais risinājums ir pareizs (ti, salokot to zirneklī).

Viņi to ir izdarījuši, izmantojot standarta triku, lai parādītu, ka origami problēma ir līdzvērtīga citai problēmai, kas jau ir zināma kā NP sarežģīta, šajā gadījumā problēmai, kas saistīta ar apļu ievietošanu noteiktā telpā.

No pirmā acu uzmetiena ir grūti saprast, kā origami var būt saistīts ar apļa iepakošanu, taču patiesībā ir tieša saikne. Padomājiet par zirnekļa nūju figūru. Pēc tam ap katru mezglu uzvelciet apli ar rādiusu, kas ir puse no attāluma līdz citam mezglam. Origami problēma, atrast veidu, kā šos mezglus novietot tā, lai papīru varētu salocīt tā, lai katrs mezgls attēlotu virsotni galīgajā formā, ir līdzvērtīga optimāla sfēru iepakošanas veida atrašanai.

Lai gan pierādījums būs neliels pārsteigums, tam ir interesants rezultāts. Veicot šo izrāvienu, Langs un līdzi parāda, ka jebkuru apļu kopu ar kopējo laukumu 1 var ielikt kvadrātā, kura izmērs ir 8/pi = 2,546… Origamisks triumfs pēc jebkura standarta.

Atsauce: arxiv.org/abs/1008.1224 : Origami dizaina apļa iepakošana ir sarežģīta

paslēpties