Opakowanie do pojemnika na pierwsze dopasowanie

First-fit (FF) 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ą. Idealnie chcielibyśmy użyć jak najmniejszej liczby pojemników, ale minimalizacja liczby pojemników jest problemem NP-trudnym. Algorytm pierwszego dopasowania wykorzystuje następującą heurystykę :

• Przechowuje listę otwartych pojemników, które początkowo są puste.
• Po przybyciu przedmiotu znajdź pierwszy pojemnik, do którego przedmiot się zmieści, jeśli taki istnieje.
  • Jeśli taki pojemnik zostanie znaleziony, nowy przedmiot zostanie w nim umieszczony.
  • W przeciwnym razie otwierany jest nowy pojemnik i umieszczany jest w nim nadchodzący element.

Współczynnik przybliżenia

Oznaczmy przez FF(L) liczbę pojemników używanych przez First-Fit, a przez OPT(L) optymalną liczbę pojemników możliwą dla listy L. Analiza FF(L) została wykonana w kilku krokach.

• Pierwsza górna $_$
• W 1972 roku ta górna granica została poprawiona do $równoważnik 1,7 \ operatorname {OPT} +2} .$ , Grahama i Ullmana, Johnsona i Demersa do
• W 1976 roku został ulepszony przez Gareya, Grahama, Johnsona, Yao i Chi-Chih do ${\ Displaystyle FF (L) \ równoważnik \ lceil 1,7 \ operatorname {OPT} \ rceil }$ , co jest równoważne ze względu na integralność ${\ Displaystyle FF (L) \ równoważnik 1,7 \$$operatorname$ i ${\ Displaystyle \ operatorname {OPT}}$ .
• $. ,$ Xia granicę
• Ostatecznie w 2013 roku ta granica została poprawiona przez Dósę i Sgalla do $Displaystyle FF (L) \ równoważnik \ lfloor 1,7 \ operatorname {OPT}$ ⌊ Przedstawiają również przykładową $do$$dla$ której tej

Pomysł na dowód

Poniższy dowód jest adaptacją z . Zdefiniuj wagę elementu wejściowego jako rozmiar przedmiotu plus x pewną premię v ( x ), obliczoną w następujący sposób:

${\ styl wyświetlania v(x):={\begin{przypadki}0&x\równoważnik 1/6\\x/2-1/12&1/6<x<1/3\\1/12&1/3\równik x\równoważnik 1/ 2\\1/3&1/2<x\end{przypadki}}}$

${\ Displaystyle w (x): = x + v (x)}$ .

Zdefiniuj wagę/premię zestawu przedmiotów jako sumę wag/premii jego zawartości. Współczynnik aproksymacji asymptotycznej wynika z dwóch twierdzeń:

1. W optymalnym opakowaniu waga każdego pojemnika wynosi maksymalnie 17/12;
2. W opakowaniu First-Fit średnia waga każdego pojemnika wynosi co najmniej 5/6 = 10/12.

Dlatego asymptotycznie liczba pojemników w opakowaniu FF musi wynosić co najwyżej 17/10 * OPT.

Dla twierdzenia 1 wystarczy udowodnić, że dla dowolnego zbioru B o sumie co najwyżej 1 premia v ( x ) wynosi co najwyżej 5/12. Rzeczywiście:

• Jeśli B nie ma przedmiotu większego niż 1/2, to ma co najwyżej pięć przedmiotów większych niż 1/6, a premia za każdy z nich wynosi co najwyżej 1/12;
• Jeśli B ma przedmiot większy niż 1/2, ale nie ma przedmiotu w [1/3,1/2], to ma miejsce na co najwyżej dwa przedmioty w (1/6,1/3) i sumę ich premii wynosi co najwyżej (1/2 / 2 - 1/6) = 1/12, więc łączna premia wynosi 4/12 + 1/12 = 5/12.
• Jeśli B ma przedmiot większy niż 1/2 i przedmiot i [1/3,1/2], to nie ma już miejsca na przedmioty o rozmiarze większym niż 1/6, więc łączna premia wynosi ponownie 4/12+ 1/12 = 5/12.

Dlatego waga B wynosi co najwyżej 1 + 5/12 = 17/12.

W przypadku twierdzenia 2 rozważ najpierw pojemnik FF B z pojedynczym elementem.

• Jeśli sum( B )<1/2, to - tak jak działa FF - wszystkie elementy przetwarzane po B muszą być większe niż 1/2 (inaczej zostałyby wstawione do B ). Dlatego istnieje co najwyżej jeden pojemnik FF z sumą <1/2.
• Rozważmy teraz wszystkie inne kosze B z pojedynczym elementem z sumą ( B )>1/2. Dla wszystkich tych pojemników waga( B )>1/2+1/3 = 5/6.

Rozważmy teraz pojemniki FF B z dwoma lub więcej przedmiotami.

• Jeśli sum( B )<2/3, to - tak jak działa FF - wszystkie elementy przetwarzane po B muszą być większe niż 1/3 (inaczej zostałyby wstawione do B ). Dlatego wszystkie kolejne kosze z dwoma lub więcej elementami są większe niż 2/3. Jest więc co najwyżej jeden pojemnik FF z dwoma lub więcej elementami i sumą <2/3.
• Rozważmy teraz wszystkie inne kosze z dwoma lub więcej przedmiotami i sumą >2/3. Oznacz je B[1],B[2],...B[k], według kolejności otwierania. Dla każdego i w 1,..., k udowadniamy, że suma B[i] plus premia B[i+1] wynosi co najmniej 5/6: sum(B[i])+bonus(B [i+1]) >=5/6. Rzeczywiście, jeśli sum(B[i]) >= 5/6, to nierówność jest trywialna. W przeciwnym razie niech sum(B[i]) := 5/6 - x . Zauważ, że x wynosi od 0 do 1/6, ponieważ suma(B[i])>2/3. Ponieważ B[i+1] jest otwarte po B[i], B[i+1] zawiera co najmniej dwie pozycje, powiedzmy c 1 i c 2, które nie pasują do B[i], czyli: c1,c2 > 1-suma(B[i]) = x+1/6. Wtedy premia każdego z c1 i c2 wynosi co najmniej (x+1/6)/2 - 1/12 = x/2. Zatem premia B[i+1] wynosi co najmniej x, więc suma(B[i]) + premia(B[i+1]) >= (5/6-x)+x = 5/6.
• Możemy zastosować powyższą nierówność do kolejnych par i otrzymać: suma(B[1]) + premia(B[2]) + suma(B[2]) + premia(B[3]) + ... + suma (B[k-1]) + premia(B[k]) >= 5/6*(k-1).

Zatem łączna waga wszystkich pojemników FF wynosi co najmniej 5/6*(FF - 3) (gdzie odejmujemy 3 dla pojedynczego pojemnika jednoelementowego o sumie <1/2, pojedynczego pojemnika dwuelementowego o sumie <2/ 3, a k-1 z przedziałów dwuelementowych z sumą>=2/3).

W sumie otrzymujemy, że 17/12*OPT >= 5/6*(FF-3), więc FF <= 17/10*OPT+3.

Dósa i Sgall przedstawiają dokładniejszą analizę, która eliminuje 3 i otrzymuje FF <= 17/10*OPT.

Wyrafinowane pierwsze dopasowanie

Refined-First-Fit (RFF) to kolejny algorytm online do pakowania w pojemniki , który ulepsza wcześniej opracowany algorytm FF. Przedstawił go Andrew Chi-Chih Yao.

Algorytm

Przedmioty są podzielone na cztery klasy, zgodnie z ich rozmiarami (gdzie pojemność pojemnika wynosi 1):

• ${\ Displaystyle A} -$ kawałek - rozmiar w ${\ Displaystyle (1/2,1]}$ .
• ${\ Displaystyle B_ {1}} -$ kawałek - rozmiar w ${\ Displaystyle (2/5,1/2]}$ .
• ${\ Displaystyle B_ {2}}$ - kawałek - rozmiar w ${\ Displaystyle (1/3,2/5]}$ .
• ${\ Displaystyle X}$ - kawałek - rozmiar w ${\ Displaystyle (0,1/3]}$ .

Podobnie, pojemniki są podzielone na cztery klasy: 1, 2, 3 i 4.

Niech ${\ Displaystyle m \ in \ {6,7,8,9 \}}$ będzie stałą liczbą całkowitą. Następny element jest przypisany do kosza w - ${\ displaystyle i \ in L}$

• Klasa 1, jeśli $}$ kawałkiem, ZA { $displaystyle A$
• Klasa 2, jeśli jest $\ displaystyle$$i$ }
• $mk)}$ 3, jeśli $kawałkiem$${2}}$ ale nie m $Displaystyle$ th B_ - kawałek widziany do tej pory dla dowolnej liczby całkowitej ${\ Displaystyle k \ geq 1}$ .
• Klasa 1, jeśli $)$ to dotychczas widziany kawałek ${\ Displaystyle (mk)}$ b $\ Displaystyle B_ {2}}$
• Klasa $,$$-częścią$ jest .

Po wybraniu klasy elementu jest on umieszczany w pojemnikach tej klasy przy użyciu pakowania pojemników pierwszego dopasowania.

Zauważ, że RFF nie jest algorytmem Any-Fit, ponieważ może otworzyć nowy pojemnik, mimo że bieżący element mieści się w otwartym pojemniku (z innej klasy).

Współczynnik przybliżenia

RFF ma gwarancję przybliżenia ${\ Displaystyle RFF (L) \ równoważnik (5/3) \ cdot \ operatorname {OPT} (L )+5}$ . Istnieje rodzina list z $R$$L_ {k} ) = (5/3) \ operatorname {OPCJA} (L_ {k}) + 1/3}$ dla ${\ Displaystyle \ operatorname {OPT} (L) = 6k + 1 }$ .

Zobacz też

• First-Fit-Decreasing (FFD) to wariant offline First-Fit: akceptuje wszystkie elementy wejściowe, porządkuje je według malejącego rozmiaru i wywołuje First-Fit. Jego współczynnik aproksymacji asymptotycznej jest znacznie lepszy: około 1,222 zamiast 1,7.

Implementacje

• Python: Pakiet prtpy zawiera implementację pierwszego dopasowania .