Następne dopasowane zmniejszające się opakowanie pojemnika

Next-fit-decreasing (NFD) 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. Algorytm NFD wykorzystuje następującą heurystykę :

• Uporządkuj elementy od największego do najmniejszego.
• Zainicjuj pusty pojemnik i nazwij go „otwartym pojemnikiem”.
• Dla każdego zamówienia sprawdź, czy zmieści się do otwartego kosza:
  • Jeśli pasuje, umieść w nim nowy przedmiot.
  • W przeciwnym razie zamknij bieżący pojemnik, otwórz nowy i umieść w nim bieżący przedmiot.

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

Górna granica wydajności

Baker i Coffman udowodnili, że dla każdej liczby całkowitej r , gdy rozmiar wszystkich pozycji wynosi co najwyżej 1/ r , asymptotyczny współczynnik aproksymacji RFD spełnia

${\ Displaystyle R_ {NFD} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik 1/r) = h_ {\ infty} (r)}$ ,

gdzie jest sekwencją, której pierwsze elementy to w przybliżeniu $1,69103$ W szczególności przyjęcie r = 1 implikuje to

${\ Displaystyle R_ {NFD} ^ {\ infty} = h _ {\ infty} (1) \ około 1,69103}$ .

Później NFD był również analizowany probabilistycznie.

Warianty

Next-Fit pakuje listę i jej odwrotność do tej samej liczby pojemników. W związku z tym, Next-Fit-Increasing ma taką samą wydajność jak Next-Fit-Decreasing.

Jednak Next-Fit-Increasing działa lepiej, gdy istnieją ogólne struktury kosztów.