Problema împachetării

Când vă mutați, umpleți o cutie după alta și vă întrebați dacă o ordine mai isteață ar fi necesitat mai puține. Aceasta este problema împachetării și este cunoscută ca fiind grea: chiar și calculatoarele găsesc cel mai mic număr de containere pentru date mari doar printr-o căutare ingenioasă. Totuși, regulile simple se apropie surprinzător de mult.

Containere de aceeași înălțime pline cu obiecte colorate stivuite, de dimensiuni diferite, cu alte obiecte care așteaptă deasupra lor
Containere de aceeași înălțime pline cu obiecte colorate stivuite, de dimensiuni diferite, cu alte obiecte care așteaptă deasupra lor

Problema

Se dau obiecte cu dimensiuni și containere care au toate aceeași capacitate. Fiecare obiect trebuie pus într-un container fără ca vreun container să se umple peste măsură, folosind cât mai puține containere. Dimensiunile pot reprezenta greutăți, lungimi, durate sau dimensiuni de fișiere. Pare un joc pentru o după-amiază ploioasă, dar problema este NP-dificilă: nu se cunoaște nicio metodă care să găsească rapid cel mai mic număr de containere pentru orice date.

Reguli rapide

Next Fit umple un container până când următorul obiect nu mai încape, apoi începe un container nou și nu se mai uită înapoi. First Fit ține toate containerele deschise și pune fiecare obiect în primul container care are loc. Best Fit pune fiecare obiect în containerul cel mai plin care mai are loc. Toate trei decid imediat, lucru util când obiectele sosesc pe rând și trebuie așezate pe loc.

Mai întâi sortarea

Obiectele mari sunt cele dificile, pentru că au nevoie de mult spațiu liber. Dacă sortați obiectele de la cel mai mare la cel mai mic și apoi folosiți First Fit sau Best Fit, cele mari intră cât timp containerele sunt încă goale, iar cele mici umplu golurile. First Fit Decreasing nu folosește niciodată mai mult de 11/9 din numărul minim de containere, plus o constantă, față de 1,7 ori pentru First Fit pe obiecte nesortate.

Un exemplu

Luați containere de dimensiune 10 și obiectele 2, 3, 2, 1, 3, 4, 5, 6, 7 și 7, care însumează 40. First Fit pune 2, 3, 2 și 1 în primul container și 3 și 4 în al doilea, apoi 5, 6, 7 și 7 au nevoie fiecare de un container propriu: 6 containere. Cu obiectele sortate de la cel mai mare, First Fit Decreasing formează 7 + 3, 7 + 3, 6 + 4 și 5 + 2 + 2 + 1: 4 containere pline, exact limita inferioară de 40 / 10 = 4.

Găsirea celui mai mic număr de containere

Pentru puține obiecte, răspunsul exact se poate găsi prin programare dinamică pe submulțimi: pentru fiecare mulțime de obiecte, cel mai mic număr de containere și cel mai gol ultim container care o cuprind, construite din mulțimile cu un obiect mai puțin. Asta înseamnă aproximativ 2ⁿ·n pași pentru n obiecte. Instanțele mai mari se rezolvă prin branch and bound sau programare în numere întregi, iar limita inferioară arată cât de departe de cea mai bună poate fi o împachetare.

Unde se folosește

Încărcarea camioanelor și a containerelor de transport, tăierea țevilor sau a rolelor de hârtie din lungimi standard cu cât mai puțină pierdere (problema tăierii), plasarea mașinilor virtuale pe servere și așezarea fișierelor pe discuri sunt toate probleme de împachetare. În două și trei dimensiuni, cu cutii în loc de numere, problema este și mai grea.

Întrebări frecvente

Care este diferența dintre împachetarea online și cea offline?

Online, fiecare obiect trebuie așezat imediat ce sosește, fără a le cunoaște pe celelalte; așa funcționează Next Fit, First Fit și Best Fit. Offline, toate obiectele sunt cunoscute dinainte, așa că pot fi sortate mai întâi, cum face First Fit Decreasing.

Cât de aproape de optim ajunge First Fit Decreasing?

Folosește cel mult 11/9 din numărul minim de containere plus 6/9 dintr-un container, o margine despre care György Dósa a demonstrat în 2007 că este exactă. Pe date obișnuite este de regulă optim sau la un container distanță.

Este problema împachetării același lucru cu problema rucsacului?

Sunt înrudite, dar diferite. Problema rucsacului umple un singur rucsac cu obiectele cele mai valoroase; problema împachetării pune toate obiectele în cât mai puțini rucsaci. Metodele exacte pentru împachetare lucrează adesea rezolvând iar și iar probleme asemănătoare cu cea a rucsacului.

De ce permite aplicația doar 12 obiecte?

Pentru că răspunsul exact examinează fiecare mulțime de obiecte, iar 12 obiecte formează deja 4.096 de mulțimi. Regulile rapide s-ar descurca cu mii de obiecte, dar desenul și comparația cu răspunsul exact nu.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Încercați problema împachetării