Origami raukšlių modelio dizainas pasirodė NP-kietas

Maždaug prieš 20 metų įvairūs asmenys pripažino, kad kvadratinio popieriaus lapo lankstymo į savavališką 3D formą problema turi daug panašumų su skaičiavimo geometrijos problemomis. Šie specialistai pradėjo kurti algoritmus, kurie automatiškai generuoja raukšlių raštus, kurie plokščią lakštą paverčia jūsų pasirinkta sudėtinga forma. Dėl to ir magiškos šiuolaikinių skaičiavimo mašinų galios origami šiuo metu išgyvena techninę ir kūrybinę revoliuciją.

Tačiau šis naujas popieriaus lankstymo mokslas atvedė prie visiškai naujų galvosūkių. Origami pavertę kompiuterių mokslo problema, neilgai trukus origamistai pradėjo sau užduoti į kompiuterių mokslą panašius klausimus. Visų pirma, jie nori žinoti, koks sudėtingas yra origami skaičiavimas. Šiandien jie turi atsakymą dėl darbo Robertas Langas , vienas iš pasaulio kompiuterinio origami lyderių ir pora jo bičiulių: Erikas rytoj MIT ir Sándor Fekete Braunšveigo technologijos universitete, Vokietijoje.

Origami dizaino procesas yra konceptualiai paprastas. Origamistai pradeda nuo formos, kurią reikia atkurti – sakoma voro forma. Tada jie perbraižo jį kaip figūrėlę, kurią šiuo atveju sudaro kūnas ir aštuonios kojos.

Origamistai žino, kad kiekvieną galūnę galima atkurti tam tikru būdu sulenkus popieriaus atvartą. Taigi pagrindinis žingsnis kuriant origami vorą yra surasti būdą, kaip sulankstyti popieriaus lapą taip, kad susidarytų aštuoni tinkamo dydžio atvartai, po vieną kiekvienai kojai. Po to belieka suformuoti atvartus, kad jie atrodytų kojos formos, o tai gana paprasta užduotis.

Šios srities ekspertai jau seniai įtarė, kad lazdos figūrėlės pavertimo raukšlėmis procesas yra sudėtingas skaičiavimais. Dabar Langas ir bendradarbiai įrodo, kad ši intuicija teisinga, parodydami, kad procesas yra NP sunkus. Taigi daug sunkiau sugalvoti raukšlių modelį, kuris sukurtų vorą, nei patikrinti, ar pateiktas sprendimas yra teisingas (ty sulankstyti jį į vorą).

Jie tai padarė naudodami standartinį triuką, parodydami, kad origami problema yra lygiavertė kitai problemai, kuri jau žinoma kaip NP sudėtinga, šiuo atveju – apskritimų supakavimo į tam tikrą erdvę problemai.

Iš pirmo žvilgsnio sunku suprasti, kaip origami gali būti susijęs su ratų pakavimu, bet iš tikrųjų yra tiesioginis ryšys. Prisiminkite voro figūrėlę. Tada aplink kiekvieną mazgą nubrėžkite apskritimą, kurio spindulys yra pusė atstumo iki kito mazgo. Origami problema, ieškant būdo išdėstyti šiuos mazgus taip, kad popierių būtų galima sulankstyti taip, kad kiekvienas mazgas būtų galutinės formos viršūnė, yra lygiavertis optimalaus sferų pakavimo būdo paieškai.

Nors įrodymas bus mažai netikėtas, jis turi įdomių padarinių. Vykdydami šį proveržį, Lang ir bendradarbiai parodo, kad bet kurį apskritimų rinkinį, kurio bendras plotas yra 1, galima sudėti į kvadratą, kurio dydis yra 8/pi = 2,546... Origaminis triumfas pagal bet kurio standartus.

Nuoroda: arxiv.org/abs/1008.1224 : Origami dizaino apskritimo pakuotė yra sudėtinga

paslėpti