Problem med containerpakning

Containeriseringsproblemet er et NP - hårdt kombinatorisk problem. Opgaven er at pakke objekter med en foruddefineret form i et begrænset antal beholdere med en foruddefineret form på en sådan måde, at antallet af brugte beholdere er det mindste eller antallet eller volumen af objekter (denne pakke) er størst.

Varianter og metoder til løsning af pakkeproblemer

Der er mange variationer af dette problem ( todimensionel pakning , lineær pakning , pakning efter vægt , pakning efter værdi , osv.), som kan anvendes på forskellige områder, såsom optimal fyldning af containere, lastning af lastbiler med en vægtgrænse, skabelse redundante kopier på flytbare medier osv. Da problemet er NP-hårdt , er brugen af en nøjagtig opregningsalgoritme kun mulig for små dimensioner. Normalt bruges heuristiske tilnærmede polynomielle algoritmer til at løse problemet.

Problemet med at pakke i endimensionelle identiske beholdere

Udtalelse af problemet

Lad der være et sæt beholdere af størrelse og et sæt objekter af størrelse . Det er nødvendigt at finde et helt antal beholdere og en opdeling af sættet i undersæt , således at for alle . En løsning kaldes optimal, hvis den er minimal. Minimum er yderligere angivet ved OPT . $V$ $n$ $a_1,\prikker,a_n$ $B$ $\{1,\dots,n\}$ $B$ $S_1 \kop \prikker \kop S_B$ $\sum_{i \in S_k} a_i \leq V$ $k=1,\prikker,B$ $B$ $B$

Pakning som et heltals programmeringsproblem

Containeriseringsproblemet kan formuleres som et heltalsprogrammeringsproblem som følger:

Minimer $B = \sum_{i=1}^n y_i$
under restriktioner	$\sum_{j=1}^n a_j x_{ij} \leq V y_i,$	$\forall i \i \{1,\ldots,n\}$
	$\sum_{i=1}^n x_{ij} = 1,$	$\forall j \in \{1,\ldots,n\}$
	$y_i \in\{0,1\},$	$\forall i \i \{1,\ldots,n\}$
	$x_{ij} \i \{0,1\},$	$\forall i \in \{1,\ldots,n\} \, \forall j \in \{1,\ldots,n\}$

hvor , hvis beholderen er brugt , og hvis varen er placeret i beholderen . [en] $y_i = 1$ $jeg$ $x_{ij} = 1$ $j$ $jeg$

Tilnærmede polynomielle algoritmer

De enkleste polynomielle pakningsalgoritmer er Best Fit Decreasing - BFD (Best Fit Descending) og First Fit Decreasing - FFD (First Fit Descending). Varerne sorteres i ikke-stigende størrelse og pakkes sekventielt enten i en beholder, hvori der efter pakning er det mindste ledige volumen tilbage - BFD, eller i den første beholder, hvor det er placeret - FFD. Disse algoritmer har vist sig at bruge højst

$\frac{11}{9}OPT + 1$

beholdere [2] .

Der er dog også asymptotisk ε-optimale polynomielle algoritmer til pakningsproblemet.

Problemet med at afgøre, om OPT er to eller tre, er NP-hårdt. For enhver ε > 0 er det derfor vanskeligt at pakke varer i (3/2 − ε)OPT- beholdere. (Hvis en sådan polynomiel algoritme eksisterer, så er det i polynomiel tid muligt at bestemme, om n ikke-negative tal deler sig i to mængder med samme sum af elementer. Dette problem er dog kendt for at være NP-hårdt.) Derfor, hvis P falder ikke sammen med NP, så for pakningsproblemet er der ingen Approximate Polynomial Time SchemePTAS-algoritme ( . På den anden side kan man for enhver ε >0 finde en løsning med højst (1 + ε)OPT + 1 beholdere i polynomisk tid. Sådanne algoritmer hører til den asymptotiske PTAS. [3] Men da begge konstanter vilkårligt afhænger af ε ved estimering af kompleksiteten af denne klasse af algoritmer, kan sådanne algoritmer, i modsætning til FFD og BFD, være praktisk talt ubrugelige. $an^b$

Probabilistisk tilgang

For en bestemt klasse af sandsynlighedsfordelinger af størrelserne af pakkede emner, inklusive fordelingsfunktioner konveks op og ned, er der en praktisk polynomiel pakkealgoritme, der er asymptotisk optimal næsten sikkert , da antallet af emner stiger i det uendelige. For fordelinger, der ikke er inkluderet i denne klasse, kan individuelle polynomiske asymptotisk optimale algoritmer konstrueres. [fire]

Noter

↑ Silvano Martello og Paolo Toth. Rygsækproblemer (neopr.) . - Chichester, Storbritannien: John Wiley and Sons , 1990. - S. 221. - ISBN 0471924202 .
↑ Yue, Minyi (1991), Et simpelt bevis på uligheden FFD(L) ≤ (11/9)OPT(L) + 1, for alle L, for FFD bin-packing algoritmen , Et simpelt bevis på uligheden FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for FFD bin-packing-algoritmen, Acta Mathematicae Applicatae Sinica T. 7 (4): 321–331, ISSN 0168-9673 , DOI 10.80207/B.
↑ Fernandez de la Vega, W. & Lueker, GS (1981), Beholderpakning kan løses inden for 1 + ε i lineær tid , Beholderpakning kan løses inden for 1 + ε i lineær tid, Combinatorica (Springer Berlin / Heidelberg) . — V. 1 (4): 349–355, ISSN 0209-9683 , DOI 10.1007/BF02579456
↑ A. V. Smirnov. Om problemet med at pakke i containere. UMN, 1991, bind 46, udgave 4(280), side 173-174. . Dato for adgang: 19. februar 2016. Arkiveret fra originalen 7. marts 2016. (ubestemt)

Se også

Emballeringsopgaver
Pakke cirkler	I en cirkel / i en retvinklet trekant / i en ligebenet retvinklet trekant / i en firkant Apollonius tæppe Cirkelpakningssætning Tammes problem (på kuglen)
Ballonpakning	Apolloniev i en bold tæt pakning kontakt nummer Sfærisk pakningsgrænse (hamming)
Andre pakker	Til containere Tetraeder Sæt
Gåde	Conway Slotobera - Graatsmy

NP-komplette problemer
Maksimeringsproblem ved stabling (pakning)	Emballering i containere todimensionel pakning lineær pakning pakning efter vægt emballage efter værdi Rygsækproblemet
grafteori mængdeteori	Vertex Cover Problem Klik problem Problemet med et uafhængigt sæt (sæt) Sæt dækningsproblem Steiners problem Problemet med den rejsende sælger Generaliseret rejsende sælger problem
Algoritmiske problemer	Tilfredshedsproblem for booleske formler (i konjunktiv normal form)
Logiske spil og puslespil	Generaliserede tags (spil i N 2 -1) korteste løsningsproblem Problemer, hvis løsninger anvendes i Tetris Generaliseret Sudoku problem Latinsk kvadratisk påfyldningsproblem Kakuros opgave
Sværhedsklasser Operationsforskning Optimering Kombinatorisk optimering Anvendt matematik Teori om algoritmer Dynamisk programmering 21 NP-komplet Karp problem