Zmniejszające się opakowanie z pierwszego dopasowania

Zmniejszanie pierwszego dopasowania (FFD) to algorytm 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, dlatego używamy w przybliżeniu optymalnej heurystyki .

Opis

Algorytm FFD działa w następujący sposób.

Uporządkuj elementy od największego do najmniejszego.
Otwórz nowy pusty pojemnik, pojemnik nr 1.
Dla każdego elementu od największego do najmniejszego znajdź pierwszy pojemnik, do którego pasuje element, jeśli taki istnieje.
- Jeśli taki pojemnik zostanie znaleziony, umieść w nim nowy przedmiot.
- W przeciwnym razie otwórz nowy pusty pojemnik i umieść w nim nowy przedmiot.

W skrócie: FFD porządkuje artykuły według malejącego rozmiaru, a następnie wywołuje pakowanie w pojemnikach pierwszego dopasowania .

Równoważny opis algorytmu FFD jest następujący.

Uporządkuj elementy od największego do najmniejszego.
Dopóki są pozostałe elementy:
- Otwórz nowy pusty pojemnik.
- Dla każdego elementu od największego do najmniejszego:
  - jeśli mieści się w bieżącym pojemniku, włóż go.

W standardowym opisie przeglądamy elementy raz, ale pozostawiamy wiele otwartych pojemników. W równoważnym opisie powtarzamy elementy wiele razy, ale za każdym razem pozostawiamy tylko jeden otwarty pojemnik.

Analiza wydajności

Wydajność FFD analizowano w kilku krokach. Poniżej oznacza liczbę pojemników używanych przez FFD dla zestawu wejściowego S i pojemności pojemnika C. ${\ Displaystyle FFD (S, C)}$

W 1973 roku DS Johnson udowodnił w swojej pracy doktorskiej, że ${\ Displaystyle FFD (S, C) \ równoważnik 11/9 \ operatorname { OPT} (S,C)+4}$ dla dowolnej instancji S i pojemności C .
W 1985 roku BS Backer podał nieco prostszy dowód i wykazał, że stała addytywna nie przekracza 3.
Yue Minyi udowodnił, że $\ Displaystyle FFD (S, C) \ równoważnik 11/9 \ operatorname {OPT} (S, C) +1}$ $(S, C)$ 1991 r., aw 1997 r. poprawił tę analizę do wraz z Li Ronghengiem.
W 2007 roku György Dósa udowodnił ścisłe powiązanie ${\ Displaystyle FFD (S, C) \ równoważnik 11/9 \ operatorname {OPT } (S, C) + 6/9}$ i przedstawił przykład, dla którego ${\ Displaystyle FFD (S, C) =11/9\mathrm {OPCJA} (S,C)+6/9}$ .

Najgorszy przykład

Przykład dolnej granicy podany przez Dósę jest następujący: Rozważmy dwie konfiguracje pojemników:

${\ Displaystyle B_ {1}: = \ {1/2 + \ varepsilon, 1/4 + \ varepsilon, 1 /4-2\varepsilon \}}$ ;
${\ Displaystyle B_ {2}: = \ {1/4 + 2 \ varepsilon ,1/4+2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$ .

$} , FFD$ optymalnym rozwiązaniu są 4 kopie i 2 kopie ${2}$

4 pojemniki z konfiguracją ${\ Displaystyle \ {1/2 + \ varepsilon, 1/4 + 2 \ varepsilon \}}$ ,
1 pojemnik z konfiguracją ${\ Displaystyle \ {1/4+ \ varepsilon, 1/4+ \ varepsilon, 1/4+ \ varepsilon \} }$ ,
1 pojemnik z konfiguracją ${\ Displaystyle \ {1/4 + \ varepsilon, 1/4-2 \ varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$ ,
1 pojemnik z konfiguracją ${\ Displaystyle \ {1/4-2 \ varepsilon, 1/4- 2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$ ,
1 ostatni pojemnik z konfiguracją ${\ Displaystyle \ {1/4-2 \ varepsilon \}$ }

To znaczy łącznie 8 pojemników, podczas gdy optymalny ma tylko 6 pojemników. Dlatego górna granica jest ciasna, ponieważ ${\ Displaystyle 11/9 \ cdot 6 + 6/9 = 72/9 = 8}$ .

Ten przykład można rozszerzyć na wszystkie rozmiary ${\ Displaystyle {\ tekst {OPT}} (S, C)}$ : w optymalnej konfiguracji jest 9 k + 6 pojemników: 6 k + 4 typu B ₁ i 3 k +2 typu B ₂ . Ale FFD potrzebuje co najmniej 11 k + 8 pojemników, czyli ${\ Displaystyle {\ Frac {11} {9}} (6 k + 4) + {\ Frac {6} 9}}}$ .

Właściwości monotoniczności

Wbrew intuicji, nie jest monotoniczną funkcją C . $\ Displaystyle FFD (S, C)}$ Załóżmy na przykład, że dane wejściowe to:

44, 24, 24, 22, 21, 17, 8, 8, 6, 6.

Przy pojemności 60 FFD pakuje 3 pojemniki:

44, 8, 8;
24, 24, 6, 6;
22, 21, 17.

Ale przy pojemności 61 FFD pakuje 4 pojemniki:

44, 17;
24, 24, 8;
22, 21, 8, 6;
6.

Dzieje się tak, ponieważ przy pojemności 61 17 mieści się w pierwszym pojemniku, a tym samym blokuje drogę do kolejnych 8, 8.

Inny przykład

Jako inny przykład załóżmy, że dane wejściowe to: 51, 28, 28, 28, 27, 25, 12, 12, 10, 10, 10, 10, 10, 10, 10, 10. Przy pojemności 75 FFD pakuje 4 pojemniki:

51, 12, 12
28, 28, 10
28, 27, 10, 10
25, 10, 10, 10, 10, 10

Ale przy pojemności 76 potrzebuje 5 pojemników:

51, 25
28, 28, 12
28, 27, 12
10, 10, 10, 10, 10, 10, 10
10

Podobnie, nie jest monotoniczną funkcją rozmiarów przedmiotów w $S :$ się ale liczba Rozważmy powyższy przykład z pojemnością 60. Jeśli 17 staje się 16, to wynikowe opakowanie to:

44, 16;
24, 24, 8;
22, 21, 8, 6;
6.

Jednak algorytm FFD ma właściwość „asymptotycznej monotoniczności”, zdefiniowaną w następujący sposób.

Dla każdego przypadku S i liczby całkowitej m , niech MinCap ( S, m ) będzie najmniejszą pojemnością C taką, że ${\ Displaystyle OPT (S, C) \ równoważnik m}$
Dla każdej liczby całkowitej m niech MinRatio( m ) będzie najmniejszą liczbą r ≥1 taką, że dla wszystkich zestawów wejściowych S , $\ Displaystyle FFD ( S, r \ cdot {\ text {MinCap}} (S, m)) \ równoważnik m}$ . Jest to ilość, o jaką musimy „nadmuchać” pojemniki tak, aby FFD osiągnął optymalną liczbę pojemników.
Wtedy dla każdego wejścia S i dla każdego r ≥ MinRatio ( m ), $\ Displaystyle FFD (S, r \ cdot {\ tekst {MinCap}} (S,m))\równik m}$ . Pokazuje to w szczególności, że infimum w powyższej definicji można zastąpić minimum.

Zmodyfikowane pierwsze dopasowanie malejące

Zmodyfikowane zmniejszanie pierwszego dopasowania (MFFD) poprawia FFD dla przedmiotów większych niż pół pojemnika, klasyfikując elementy według rozmiaru na cztery klasy wielkości: duży, średni, mały i mały, odpowiadające elementom o rozmiarze > 1/2 pojemnika, > 1/3 kosz, > 1/6 kosza i odpowiednio mniejsze przedmioty. Następnie przechodzi przez pięć faz:

Przydziel pojemnik na każdy duży przedmiot, uporządkowany od największego do najmniejszego.
Idź dalej przez pojemniki. Na każdym: Jeśli najmniejszy pozostały średni element nie mieści się, pomiń ten kosz. W przeciwnym razie umieść największy pozostały średni przedmiot, który pasuje.
Przejdź wstecz przez te pojemniki, które nie zawierają średniego przedmiotu. Na każdym: Jeśli pozostałe dwa najmniejsze małe przedmioty nie mieszczą się, pomiń ten kosz. W przeciwnym razie umieść najmniejszy pozostały mały przedmiot i największy pozostały mały przedmiot, który się mieści.
Przejdź dalej przez wszystkie pojemniki. Jeśli najmniejszy pozostały element dowolnej klasy wielkości nie mieści się, pomiń ten kosz. W przeciwnym razie umieść największy przedmiot, który się mieści i pozostań w tym koszu.
Użyj FFD, aby zapakować pozostałe elementy do nowych pojemników.

$_ S,C)\równoważnik (71/60)\mathrm {OPCJA} (S,C)+(31/6)}$ udowodnili . Ta granica została poprawiona w 1995 roku przez Yue i Zhanga, którzy udowodnili, że ${\ Displaystyle MFFD (S, C) \ leq (71/60)\mathrm {OPCJA} (S,C)+1}$ .

Inne warianty

Metoda best-fit-decreasing (BFD) jest bardzo podobna do metody FFD, z tą różnicą, że po posortowaniu lista jest przetwarzana przez najlepiej dopasowane opakowanie bin . Jego współczynnik aproksymacji asymptotycznej jest taki sam jak FFD - 11/9.

Implementacje

Python: pakiet prtpy zawiera implementację pierwszego dopasowania malejącego .

Zobacz też

Algorytm Multifit - algorytm szeregowania identycznych maszyn , który wykorzystuje FFD jako podprogram.

^ Johnson, David S. (1973). „Niemal optymalne algorytmy pakowania w pojemniki” (PDF) . Instytut Technologii Massachusetts .
^ Baker, Brenda S. (1985). „Nowy dowód na malejący algorytm pakowania w pojemniki po pierwszym dopasowaniu” . J. Algorytmy . 6 (1): 49–70. doi : 10.1016/0196-6774(85)90018-5 .
^ Yue, Minyi (październik 1991). „Prosty dowód nierówności FFD (L) ≤ 11/9 OPT (L) + 1, ∀ L dla algorytmu pakowania binarnego FFD”. Acta Mathematicae Applicatae Sinica . 7 (4): 321–331. doi : 10.1007/BF02009683 . S2CID 189915733 .
Bibliografia _ Yue, Minyi (sierpień 1997). „Dowód FFD (L) <-OPT (L) + 7/9”. Chiński biuletyn naukowy . 42 (15): 1262–1265. Bibcode : 1997ChSBu..42.1262L . doi : 10.1007/BF02882754 . S2CID 93280100 .
^ ^a ^b Dosa, György (2007). „Ścisła granica pierwszego dopasowania algorytmu zmniejszania pakowania w pojemnikach wynosi FFD (I) ≤ 11/9OPT (I) + 6/9”. Kombinatoryka, algorytmy, metodologie probabilistyczne i eksperymentalne. UCIECZKA . doi : 10.1007/978-3-540-74450-4_1 .
^ ^a ^b Coffman, Jr., EG; Garey, MR; Johnson, DS (1978-02-01). „Zastosowanie bin-packingu do planowania wieloprocesorowego” . SIAM Journal o informatyce . 7 (1): 1–17. doi : 10.1137/0207001 . ISSN 0097-5397 .
Bibliografia _ Lu, Pinyan (2021-07-18). „Algorytmiczne ramy przybliżania przydziału zadań Maximin Share” . Materiały z 22. Konferencji ACM na temat ekonomii i obliczeń . KE '21. Nowy Jork, NY, USA: Association for Computing Machinery: 630–631. ar Xiv : 1907.04505 . doi : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1 .
^ ^a ^b Johnson, David S; Garey, Michael R (październik 1985). „Twierdzenie 7160 dotyczące pakowania w pojemniki” . Dziennik złożoności . 1 (1): 65–106. doi : 10.1016/0885-064X(85)90022-6 .
Bibliografia _ Zhang, Lei (lipiec 1995). „Prosty dowód nierówności MFFD (L) ≤ 71/60 OPT (L) + 1, L dla algorytmu pakowania bin MFFD”. Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. doi : 10.1007/BF02011198 . S2CID 118263129 .

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

[Backer85-2] Baker, Brenda S. (1985). „Nowy dowód na malejący algorytm pakowania w pojemniki po pierwszym dopasowaniu” . J. Algorytmy . 6 (1): 49–70. doi : 10.1016/0196-6774(85)90018-5 .

[3] Yue, Minyi (październik 1991). „Prosty dowód nierówności FFD (L) ≤ 11/9 OPT (L) + 1, ∀ L dla algorytmu pakowania binarnego FFD”. Acta Mathematicae Applicatae Sinica . 7 (4): 321–331. doi : 10.1007/BF02009683 . S2CID 189915733 .

[4] Bibliografia _ Yue, Minyi (sierpień 1997). „Dowód FFD (L) <-OPT (L) + 7/9”. Chiński biuletyn naukowy . 42 (15): 1262–1265. Bibcode : 1997ChSBu..42.1262L . doi : 10.1007/BF02882754 . S2CID 93280100 .

[Dosa07-5] Dosa, György (2007). „Ścisła granica pierwszego dopasowania algorytmu zmniejszania pakowania w pojemnikach wynosi FFD (I) ≤ 11/9OPT (I) + 6/9”. Kombinatoryka, algorytmy, metodologie probabilistyczne i eksperymentalne. UCIECZKA . doi : 10.1007/978-3-540-74450-4_1 .

[:0-6] Coffman, Jr., EG; Garey, MR; Johnson, DS (1978-02-01). „Zastosowanie bin-packingu do planowania wieloprocesorowego” . SIAM Journal o informatyce . 7 (1): 1–17. doi : 10.1137/0207001 . ISSN 0097-5397 .

[:3-7] Bibliografia _ Lu, Pinyan (2021-07-18). „Algorytmiczne ramy przybliżania przydziału zadań Maximin Share” . Materiały z 22. Konferencji ACM na temat ekonomii i obliczeń . KE '21. Nowy Jork, NY, USA: Association for Computing Machinery: 630–631. ar Xiv : 1907.04505 . doi : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1 .

[JohnsonGarey19852-8] Johnson, David S; Garey, Michael R (październik 1985). „Twierdzenie 7160 dotyczące pakowania w pojemniki” . Dziennik złożoności . 1 (1): 65–106. doi : 10.1016/0885-064X(85)90022-6 .

[YueZhang19952-9] Bibliografia _ Zhang, Lei (lipiec 1995). „Prosty dowód nierówności MFFD (L) ≤ 71/60 OPT (L) + 1, L dla algorytmu pakowania bin MFFD”. Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. doi : 10.1007/BF02011198 . S2CID 118263129 .