Next-fit kärlförpackning

Next-fit är en onlinealgoritm för soppackning . Dess ingång är en lista över föremål av olika storlekar. Dess produktion är en packning - en uppdelning av föremålen i fack med fast kapacitet, så att summan av storlekarna av föremål i varje fack är som mest kapaciteten. Helst skulle vi vilja använda så få papperskorgar som möjligt, men att minimera antalet papperskorgar är ett NP-hårt problem. Next-fit-algoritmen använder följande heuristik :

Den behåller en aktuell papperskorg , som initialt är tom.
När en vara anländer kontrollerar den om varan får plats i den aktuella papperskorgen.
- Om den passar placeras den inuti den.
- Annars stängs den aktuella papperskorgen, en ny papperskorg öppnas och det kommande föremålet placeras i denna nya papperskorg.

Next-Fit är en algoritm för begränsat utrymme - den kräver att endast en delvis fylld papperskorg är öppen när som helst. Algoritmen studerades av David S. Johnson i sin doktorsavhandling 1973.

Körtid

Körtiden för NextFit kan begränsas av ${\mathcal {O}}(n)$ , där $n$ är antalet objekt i listan.

Approximationsförhållande

Ange med NF(L) antalet fack som används av NextFit, och med OPT(L) det optimala antalet fack som är möjligt för listan L.

Övre gräns

Sedan, för varje lista $L$ , $NF(L)\leq 2\cdot \mathrm {OPT} (L)-1$ . Intuitionen till beviset är följande. Antalet fack som används av denna algoritm är inte mer än dubbelt så mycket som det optimala antalet fack. Med andra ord, det är omöjligt att 2 kärl som högst är halvfulla eftersom en sådan möjlighet innebär att vid någon tidpunkt var exakt en behållare högst halvfull och en ny öppnades för att rymma ett föremål av storlek som högst $B/2$ . Men eftersom den första har minst ett mellanslag på $B/2$ , kommer algoritmen inte att öppna en ny papperskorg för något föremål vars storlek är högst $B/2$ . Först efter att papperskorgen fylls med mer än $B/2$ eller om ett föremål med en storlek större än $B/2$ anländer, kan algoritmen öppna en ny papperskorg. Så om vi har $K$ -fack, är åtminstone $K-1$ -fack mer än halvfulla. Därför, $\sum _{i\in I}s(i)>{\tfrac {K-1}{2}}B$ . Eftersom ${\tfrac {\sum _{i\in I}s(i)}{B}}$ är en nedre gräns för det optimala värdet $\mathrm {OPT}$ , vi får att $K-1<2\mathrm {OPT}$ och därför $K\leq 2\mathrm { OPT}$ .

Nedre gräns

För varje $N\in \mathbb {N}$ finns det en lista $L$ så att $\mathrm {OPT} (L)= N$ och $NF(L)=2\cdot \mathrm {OPT} (L)-2$ .

Listfamiljen för vilken det gäller att $NF(L)=2\cdot \mathrm {OPT} (L)-2$ ges av $L:=\left({\ frac {1}{2}},{\frac {1}{2(N-1)}},{\frac {1}{2}},{\frac {1}{2(N-1)} },\dots ,{\frac {1}{2}},{\frac {1}{2(N-1)}}\right)$ med $|L|=4(N-1)$ . Den optimala lösningen för den här listan har $N-1$ fack som innehåller två artiklar med storlek $1/2$ och en fack med $2(N- 1)$ objekt med storlek $\displaystyle 1/2(N-1)}$ (dvs. ${\displaystyle N} fack totalt$ , medan lösningen som genereras av NF har $2(N-1)$ fack med en artikel i storlek $\displaystyle 1/2}$ och en artikel med storlek ${\displaystyle 1/($ .

Avgränsad artikelstorlek

Om den maximala storleken på ett föremål är ${\displaystyle \alpha } , så$ uppfyller det asymptotiska approximationsförhållandet ${\displaystyle R_{NF}^{\infty }} :$

$\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2}$ $\alpha \geq 1/2$ alla ;
$R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\ alpha )$ för alla $\alpha \leq 1/2}$ displaystyle

Övriga fastigheter

Next-Fit packar en lista och dess invers i samma antal papperskorgar.

Next- k -Fit (NkF)

Next-k-Fit är en variant av Next-Fit, men istället för att bara hålla ett fack öppet, håller algoritmen de sista $k$ -fackarna öppna och väljer den första fack som objektet får plats i.

För $k\geq 2$ , levererar NkF resultat som är förbättrade jämfört med resultaten av NF, men en ökning av $k$ till konstanta värden större än $2$ förbättrar dock algoritmen no vidare i sitt värsta tänkbara beteende. Om algoritm $A$ är en AlmostAnyFit-algoritm och $m=\lfloor 1/\alpha \rfloor \geq 2$ så $R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\ infty }({\text{storlek}}\leq \alpha )=1+1/m$ .

Se även

Next-fit-decreasing (NFD) är offlinevarianten av Next-Fit: den accepterar alla inmatningsartiklar, beställer dem efter fallande storlek och anropar Next-Fit. Dess asymptotiska approximationsförhållande är mycket bättre: mindre än 1,7 istället för 2.

^ ^a ^b Johnson, David S (1973). "Nästan optimala bin packing algoritmer" (PDF) . Massachusetts Institute of Technology .
^ Suri, Subhash. "Linpackning" . UCSB datavetenskap . Hämtad 7 oktober 2021 .
^ Vazirani, Vijay V. (2003), Approximation Algorithms , Berlin: Springer, ISBN 3-540-65367-8
^ "Next-fit packar en lista och dess baksida i samma antal fack" . Operations Research Letters . 7 (6): 291–293. 1988-12-01. doi : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .

[johnson73-1] Johnson, David S (1973). "Nästan optimala bin packing algoritmer" (PDF) . Massachusetts Institute of Technology .

[2] Suri, Subhash. "Linpackning" . UCSB datavetenskap . Hämtad 7 oktober 2021 .

[3] Vazirani, Vijay V. (2003), Approximation Algorithms , Berlin: Springer, ISBN 3-540-65367-8

[:0-4] "Next-fit packar en lista och dess baksida i samma antal fack" . Operations Research Letters . 7 (6): 291–293. 1988-12-01. doi : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .