Opakowanie do pojemnika Next Fit

Next-fit to algorytm online do pakowania w pojemniki . Jego dane wejściowe to lista elementów o różnych rozmiarach. Jego wyjściem jest pakowanie - podział przedmiotów na pojemniki o ustalonej pojemności, tak aby suma rozmiarów przedmiotów w każdym pojemniku była co najwyżej pojemnością. W idealnej sytuacji chcielibyśmy użyć jak najmniejszej liczby pojemników, ale minimalizacja liczby pojemników jest problemem NP-trudnym. Algorytm następnego dopasowania wykorzystuje następującą heurystykę :

Przechowuje bieżący pojemnik , który początkowo jest pusty.
Po przybyciu przedmiotu sprawdza, czy pasuje on do bieżącego pojemnika.
- Jeśli pasuje, umieszcza się go w środku.
- W przeciwnym razie bieżący pojemnik zostanie zamknięty, nowy pojemnik zostanie otwarty, a nadchodzący element zostanie umieszczony w tym nowym pojemniku.

Next-Fit to algorytm ograniczonej przestrzeni — wymaga otwarcia tylko jednego częściowo wypełnionego pojemnika w dowolnym momencie. Algorytm został zbadany przez Davida S. Johnsona w jego pracy doktorskiej w 1973 roku.

Czas działania

Czas działania NextFit może być ograniczony $,$ $.$ jest elementów

Współczynnik przybliżenia

Oznaczmy przez NF(L) liczbę pojemników używanych przez NextFit, a przez OPT(L) optymalną liczbę pojemników możliwą dla listy L.

Górna granica

Następnie dla każdej listy ${\ Displaystyle L}$ , ${\ Displaystyle NF (L) \ równoważnik 2 \ cdot \ operatorname {OPT} (L) -1 }$ . Intuicja do dowodu jest następująca. Liczba pojemników używanych przez ten algorytm jest nie większa niż dwukrotność optymalnej liczby pojemników. Innymi słowy, niemożliwe jest, aby 2 pojemniki były co najwyżej w połowie zapełnione, ponieważ taka możliwość oznacza, że w pewnym momencie dokładnie jeden pojemnik był co najwyżej w połowie zapełniony, a nowy został otwarty, aby pomieścić przedmiot o rozmiarze co najwyżej ${\ displaystyle B/2}$ . Ale ponieważ pierwszy ma co najmniej miejsce , algorytm nie otworzy nowego pojemnika dla żadnego elementu, którego rozmiar jest co najwyżej $B$ $/2}$ . Dopiero po zapełnieniu kosza więcej niż ${\ displaystyle B/2}$ lub pojawieniu się elementu o rozmiarze większym niż ${\ displaystyle B/2}$ , algorytm może otworzyć nowy kosz. Zatem jeśli mamy $pojemniki$ , przynajmniej $pojemniki$ są w ponad Dlatego ${\ Displaystyle \ suma _ {i \ w I} s (i)> {\ tfrac {K-1} {2}} B}$ . Ponieważ jest dolną granicą optymalnej wartości ${\ Displaystyle {\ tfrac {\ suma _ {i \ w I} s (i)} {B}}}$ ${\ Displaystyle \ operatorname {OPT}}$ , otrzymujemy, że ${\ Displaystyle K-1 <2 \ operatorname {OPT}}$ i dlatego ${\ Displaystyle K \ leq 2\mathrm {OPCJA} }$ .

Dolna granica

Dla każdego $że$ lista taka, że ${\ Displaystyle L},$ $N}$ ${\ Displaystyle \ operatorname {OPT} (L) = N ∈ N {\ Displaystyle N \ in \ mathbb {N$ i ${\ Displaystyle NF (L) = 2 \ cdot \ operatorname {OPT} (L) -2}$ .

Rodzina list, dla których utrzymuje, że dana jest przez ${\ Displaystyle NF (L) = 2 \ cdot \ operatorname {OPT} (L) -2}$ ${\ Displaystyle L: = \ lewo ({\ Frac {1} {2}}, {\ Frac {1} {2 (N-1)}}, {\ frac {1}{2}},{\frac {1}{2(N-1)}},\kropki,{\frac {1}{2}},{\frac {1}{2(N- 1)}}\right)}$ z ${\ Displaystyle | L | = 4 (N-1)}$ . Optymalnym rozwiązaniem dla tej listy są pojemniki zawierające dwa elementy o rozmiarze ${\ displaystyle N-1}$ ${\ Displaystyle 1/2}$ i jeden pojemnik z przedmiotami o rozmiarze ${\ Displaystyle 2 (N-1)}$ ${\ Displaystyle 1/2 (N-1) }$ (tj. $pojemników$ ), podczas gdy rozwiązanie wygenerowane przez NF ma ${\ Displaystyle 2 (N-1$ pojemniki z jednym elementem o rozmiarze ${\ Displaystyle 1/2}$ i jeden przedmiot o rozmiarze ${\ Displaystyle 1 / (2 (N-1))}$ .

Ograniczony rozmiar przedmiotu

Jeśli maksymalny rozmiar elementu wynosi $R$ to współczynnik aproksymacji asymptotycznej spełnia: $\ Displaystyle R_ {NF} ^ {\ infty}}$

${\ Displaystyle R_ {NF} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa) \ równoważnik 2}$ dla wszystkich ${\ Displaystyle \alpha \geq 1/2}$ ;
${\ Displaystyle R_ {NF} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa) \ równoważnik 1 / (1- \ alfa )}$ dla wszystkich ${\ Displaystyle \ alpha \ równoważnik 1/2}$ .

Inne właściwości

Next-Fit pakuje listę i jej odwrotność do tej samej liczby pojemników.

Następny- k -Fit (NkF)

Next-k-Fit jest wariantem Next-Fit, ale zamiast pozostawiać otwarty tylko jeden pojemnik, algorytm utrzymuje otwarte ostatnie pojemniki $pojemnik$ , w którym mieści się przedmiot.

Dla ${\ Displaystyle k \ geq 2}$ NkF zapewnia wyniki, które są lepsze w porównaniu z wynikami NF, jednak zwiększenie do stałych wartości większych niż poprawia algorytm nie $displaystyle k$ $\ geq 2}$ dalej w swoim najgorszym przypadku. Jeśli algorytm $wtedy$ algorytmem AlmostAnyFit i m $\ Displaystyle m = \ lfloor 1/\ alfa \ rfloor \ geq 2}$ ${\ Displaystyle R_ {A} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa) \leq R_{N2F}^{\infty}({\text{rozmiar}}\leq \alpha )=1+1/m}$ .

Zobacz też

Next-Fit-Decreasing (NFD) to wariant offline Next-Fit: akceptuje wszystkie elementy wejściowe, porządkuje je według malejącego rozmiaru i wywołuje Next-Fit. Jego asymptotyczny współczynnik aproksymacji jest znacznie lepszy: mniejszy niż 1,7 zamiast 2.

^ ^a ^b Johnson, David S (1973). „Niemal optymalne algorytmy pakowania w pojemniki” (PDF) . Instytut Technologii Massachusetts .
Bibliografia _ „Pakowanie do kosza” . UCSB Informatyka . Źródło 7 października 2021 r .
^ Vazirani, Vijay V. (2003), algorytmy aproksymacji , Berlin: Springer, ISBN 3-540-65367-8
^ „Next-fit pakuje listę i jej odwrotną stronę do tej samej liczby pojemników” . Listy z badań operacyjnych . 7 (6): 291–293. 1988-12-01. doi : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .

[johnson73-1] Johnson, David S (1973). „Niemal optymalne algorytmy pakowania w pojemniki” (PDF) . Instytut Technologii Massachusetts .

[2] Bibliografia _ „Pakowanie do kosza” . UCSB Informatyka . Źródło 7 października 2021 r .

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

[:0-4] „Next-fit pakuje listę i jej odwrotną stronę do tej samej liczby pojemników” . Listy z badań operacyjnych . 7 (6): 291–293. 1988-12-01. doi : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .