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.
Î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