Matematicienii au refuzat să rezolve

La un moment dat în viață, majoritatea oamenilor stăteau pe o foaie de copt și se gândeau cum să bată biscuiții cu cât mai puține deșeuri. Acum, matematicienii au renunțat și la găsirea unui algoritm computerizat pentru a răspunde la aceste tipuri de probleme geometrice.

Cum putem înmulți aluatul atunci când tăiem fursecurile de Crăciun? Cum împachetăm o valiză sau umplem un dulap de bucătărie folosind spațiul eficient? Poate că cineva s-a gândit: „Acesta trebuie să fie cel mai bun mod de ao face”. Gândirea profundă la astfel de întrebări pare acum o pierdere de timp. Știința este acum disponibilă pentru a confirma că este imposibil să se determine care este cea mai bună slujbă pentru patru sau mai mulți bărbați turtici dulci sau biscuiți din pomul de Crăciun.

Mikkel Abrahamsen, profesor asociat de informatică, și doi colegi de cercetare au studiat cât de dificil este să găsești cel mai optim mod de asamblare a obiectelor în două dimensiuni fără a le suprapune unul peste celălalt – un puzzle pe care informaticienii l-au rezolvat de zeci de ani.

“În timp ce algoritmii pot rezolva probleme complexe grave, acest lucru este foarte important pentru computerele actuale. Nu este încă posibil să asamblați optim mai mult de 5-10 dispozitive. Și rezultatele noastre arată că acest număr este foarte mare chiar acum.” „Nu contează”, explică Mikkel Abramsen.

Optimizarea lucrurilor la domiciliu nu este doar o problemă ocazională, ci într-o varietate de industrii, inclusiv producția de îmbrăcăminte și prelucrarea metalelor. În orice caz, este important să tăiați materialele cu cât mai puține deșeuri posibil. La transport, acest lucru se aplică ambalării containerelor.

Ambalarea pătratelor

În stânga: setul optim de cinci pătrate. Dreapta: 11 unități pătrate, acum cele mai cunoscute, sunt mai mari ca suprafață. Credit: Mikkel Abrahamsen

Doar patru biscuiți din turtă dulce

Știm cea mai mică dimensiune a containerului pătrat pe care o putem împacheta până la o bază de 10 metri pătrați 1 × 1 metru. Dar prin adăugarea unei scheme suplimentare, devine imposibil să se calculeze dimensiunea optimă a containerului. Abrahamsen explică:

„Când se adaugă mai mulți paleți, timpul de calcul este excesiv. Chiar și cele mai bune computere nu pot merge mai departe. Teoretic, acest lucru este posibil. Dar pe baza ritmului de creștere a puterii de calcul, putem lucra cu obiecte suplimentare. va dura milioane de ani pentru a optimiza “.

De asemenea, dacă cineva lucrează cu forme mai complexe, cum ar fi o turtă dulce în formă de pom de Crăciun, Mikkel Abrahamsen spune că este posibil să găsim soluții optime pentru patru obiecte astăzi.

Un număr nelimitat de opțiuni

Ce o face atât de dificilă? Abrahamsen explică faptul că această problemă este similară cu rezolvarea ecuațiilor de gradul cinci sau superior și cu multe incertitudini. Se știe aici că o astfel de soluție nu poate fi întotdeauna scrisă folosind operații aritmetice simple.

„Cercetările noastre demonstrează că această problemă are ceea ce numim continuitate în matematică – pe scurt, cookie-urile trebuie să cunoască toate coordonatele în care pot fi plasate și toate unghiurile în care pot fi inversate”, explică Abrahamsen.

Deoarece combinațiile posibile sunt nesfârșite, nu este posibil să faceți o listă cu toate locurile de care aveți nevoie pentru a încerca să găsiți cea mai optimă soluție pentru ambalare. În schimb, algoritmii care rezolvă în mod optim problemele de ambalare trebuie să fie mai analitice, ceea ce necesită mult timp. Acest lucru este în contrast puternic cu multe alte probleme algoritmice bine cunoscute, unde un număr limitat de combinații pot fi încercate înainte de a găsi cea mai optimă. Deci, problemele de ambalare sunt mult mai dificile.

În practică, nu există o soluție mai bună la problemele ambalajului decât problemele pe care le putem rezolva noi oamenii.

„Atât în ​​industrie, cât și în bucătărie, trebuie să continuăm să fim mulțumiți de soluții care nu sunt acceptabile pentru noi și trebuie să ne asigurăm că noi, oamenii, suntem încă mai buni decât computerele pentru a realiza aceste tipuri de sarcini – deocamdată”, conchide el. Mikkel Abramsen.

  • Problemele de ambalare în informatică și matematică sunt o clasă de probleme de optimizare care implică încercarea de a asambla o serie de obiecte cât mai aproape posibil în două sau trei dimensiuni. Matematicienii lucrează la rezolvarea problemelor de ambalare de sute de ani.
  • Cu noul rezultat, problema ambalajului bidimensional sa mutat la o clasă superioară de complexitate de calcul, care este notată cu ∃ℝ. Anterior, această întrebare a fost legată de clasa NP, care se ocupă cu popularul „problema furnizorului călătorului”, care se ocupă cu calcularea celui mai scurt tur pentru a vizita toate orașele dintr-o listă dată.
  • Cercetarea a fost realizată de Mikkel Abrahamsen de la Centrul BARC de la Universitatea din Copenhaga, Departamentul de Informatică; Tillmann Miltzow de la Universitatea din Utrecht din Olanda și Nadja Seyfert de la Freie Universität din Berlin, Germania. Studiul a fost finanțat, printre altele, de Fundația VILLUM.
  • Studiul a fost prezentat la prestigioasa conferință FOCS 2020 (IEEE Symposium on the Fundamentals of Computer Science) în perioada 16-19 noiembrie.

Referință: „Fundamentele pentru completarea ∃R a problemelor de ambalare bidimensională”, de Mikkel Abrahamsen, Tillmann Miltzov și Nadja Seifert, 16 aprilie 2020 ,.
arXiv: 2004.07558

Related articles

Comments

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Share article

Latest articles

Ouă de pasăre marine contaminate cu cocktail chimic de aditivi din plastic

Pui de pescăruș și ouă. Credit: profesorul Jon Blount Aditivii chimici utilizați în producția de plastic au fost găsiți în ouăle de pescăruș hering,...

Oglinzi comutabile create din metal lichid

Cercetătorii au dezvoltat o modalitate de a schimba în mod dinamic suprafața metalului lichid între stările reflectante (stânga sus și dreapta jos) și dispersie...

Dieta cu junk food poate crește riscul conducerii periculoase în rândul șoferilor de camioane

Dietele nesănătoase sunt asociate cu mai multă oboseală: principalul motiv al riscului crescut de accidente, spun cercetătorii. O dietă cu junk food poate crește oboseala...

Fotosinteza artificială promite o sursă de energie curată și durabilă

Oamenii pot face multe lucruri pe care plantele nu le pot face. Putem să ne plimbăm, putem vorbi, putem auzi și vedea și...

Gheața de mare din Arctica devine mai subțire de două ori mai repede decât era de așteptat

Gheața arctică în declin a Pământului este fără îndoială una dintre cele mai mari victime ale schimbărilor climatice, ale căror consecințe sunt de anvergură,...

Newsletter

Subscribe to stay updated.