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

Răcire radiantă și încălzire solară de către un sistem – Nu este necesară electricitate

Sistemul a scăzut temperatura în interiorul unui sistem de testare într-un mediu exterior sub lumina directă a soarelui cu peste 12 grade Celsius (22...

Moarte animală falsă pentru perioade lungi de timp pentru a scăpa de prădători

Antilopul european (Euroleon nostras) pe partea sa dorsală, jucând mort. Credit: profesorul Nigel R. Franks, Universitatea din Bristol Multe animale își bat joc de...

Perseverance Rover al NASA conduce pentru prima dată pe Pământ

Această imagine a fost făcută pe 4 martie 2021 pe primul disc al vehiculului Perseverance al NASA. Credit: NASA / JPL-Caltech Prima rută a...

A fost descoperită o mașină de ucis veche de 260 de milioane de ani

Recuperarea vie a Anteosaurului atacă Moshognathusul erbivor. Credit: Alex Bernardini (@SimplexPaleo) Anteosaurul sălbatic în vârstă de 260 de milioane de ani, considerat anterior a...

Fizicienii particulelor rezolvă o problemă care îi „bântuie” de mai bine de 20 de ani

Ilustrația urmărește traseul fasciculului pe măsură ce trece prin quadrupolul de radiofrecvență de cupru, magnetul dipol negru și sistemul de măsurare fisurat și către...

Newsletter

Subscribe to stay updated.