Упаковка контейнеров по принципу «первый подходит — уменьшается»
Алгоритм компьютерной науки

First-fit-decreasing (FFD) — это алгоритм упаковки контейнеров . Его входные данные — список элементов разных размеров. Его выход — упаковка — разбиение элементов на контейнеры фиксированной емкости, так что сумма размеров элементов в каждом контейнере не превышает емкость. В идеале мы хотели бы использовать как можно меньше контейнеров, но минимизация количества контейнеров — это NP-трудная задача, поэтому мы используем приблизительно оптимальную эвристику .

Описание

Алгоритм FFD работает следующим образом.

  • Расположите предметы от большего к меньшему.
  • Откройте новый пустой контейнер, контейнер №1.
  • Для каждого предмета от самого большого к самому маленькому найдите первую ячейку, в которую этот предмет помещается, если таковая имеется.
    • Если такой контейнер найден, поместите новый предмет в него.
    • В противном случае откройте новый пустой контейнер и положите в него новый предмет.

Короче говоря: FFD упорядочивает элементы по убыванию размера, а затем вызывает упаковку в контейнер первого подходящего размера .

Эквивалентное описание алгоритма FFD выглядит следующим образом.

  • Расположите предметы от большего к меньшему.
  • Пока остались следующие пункты:
    • Откройте новый пустой контейнер.
    • Для каждого элемента от наибольшего к наименьшему:
      • Если он помещается в текущую корзину, вставьте его.

В стандартном описании мы циклически обходим элементы один раз, но оставляем много открытых ячеек. В эквивалентном описании мы циклически обходим элементы много раз, но оставляем только одну открытую ячейку каждый раз.

Анализ производительности

Производительность FFD анализировалась в несколько этапов. Ниже обозначает количество бинов, используемых FFD для входного набора S и емкость бинов C. Ф Ф Д ( С , С ) {\displaystyle FFD(S,C)}

  • В 1973 году Д.С. Джонсон доказал в своей докторской диссертации [1] , что для любого примера S и емкости C. Ф Ф Д ( С , С ) ≤ 11 / 9 О П Т ( С , С ) + 4 {\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+4}
  • В 1985 году Б. С. Бэкер [2] дал несколько более простое доказательство и показал, что аддитивная константа не больше 3.
  • Юэ Миньи [3] доказал это в 1991 году, а в 1997 году усовершенствовал этот анализ совместно с Ли Жунхэном. [4] Ф Ф Д ( С , С ) ≤ 11 / 9 О П Т ( С , С ) + 1 {\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+1} Ф Ф Д ( С , С ) ≤ 11 / 9 О П Т ( С , С ) + 7 / 9 {\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+7/9}
  • В 2007 году Дьёрдь Доса [5] доказал тесную границу и представил пример, для которого . Ф Ф Д ( С , С ) ≤ 11 / 9 О П Т ( С , С ) + 6 / 9 {\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+6/9} Ф Ф Д ( С , С ) = 11 / 9 О П Т ( С , С ) + 6 / 9 {\displaystyle FFD(S,C)=11/9\mathrm {OPT} (S,C)+6/9}

Пример наихудшего случая

Пример нижней границы, приведенный Досой, выглядит следующим образом: Рассмотрим две конфигурации ячеек:

  • Б 1 := { 1 / 2 + ε , 1 / 4 + ε , 1 / 4 − 2 ε } {\displaystyle B_{1}:=\{1/2+\varepsilon, 1/4+\varepsilon, 1/4-2\varepsilon \}}  ;
  • Б 2 := { 1 / 4 + 2 ε , 1 / 4 + 2 ε , 1 / 4 − 2 ε , 1 / 4 − 2 ε } {\displaystyle B_{2}:=\{1/4+2\varepsilon,1/4+2\varepsilon,1/4-2\varepsilon,1/4-2\varepsilon \}} .

Если в оптимальном решении имеется 4 копии и 2 копии , FFD вычислит следующие ячейки: Б 1 {\displaystyle B_{1}} Б 2 {\displaystyle B_{2}}

  • 4 контейнера с конфигурацией , { 1 / 2 + ε , 1 / 4 + 2 ε } {\displaystyle \{1/2+\varepsilon ,1/4+2\varepsilon \}}
  • 1 контейнер с конфигурацией , { 1 / 4 + ε , 1 / 4 + ε , 1 / 4 + ε } {\displaystyle \{1/4+\varepsilon ,1/4+\varepsilon ,1/4+\varepsilon \}}
  • 1 контейнер с конфигурацией , { 1 / 4 + ε , 1 / 4 − 2 ε , 1 / 4 − 2 ε , 1 / 4 − 2 ε } {\displaystyle \{1/4+\varepsilon,1/4-2\varepsilon,1/4-2\varepsilon,1/4-2\varepsilon \}}
  • 1 контейнер с конфигурацией , { 1 / 4 − 2 ε , 1 / 4 − 2 ε , 1 / 4 − 2 ε , 1 / 4 − 2 ε } {\displaystyle \{1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}
  • 1 один последний контейнер с конфигурацией , { 1 / 4 − 2 ε } {\displaystyle \{1/4-2\varepsilon \}}

То есть всего 8 ячеек, тогда как оптимум имеет только 6 ячеек. Таким образом, верхняя граница узкая, потому что . 11 / 9 ⋅ 6 + 6 / 9 = 72 / 9 = 8 {\displaystyle 11/9\cdot 6+6/9=72/9=8}

Этот пример можно распространить на все размеры : [5] в оптимальной конфигурации имеется 9 k +6 ячеек: 6 k +4 типа B 1 и 3 k +2 типа B 2. Но для FFD требуется не менее 11 k +8 ячеек, что составляет . OPT ( S , C ) {\displaystyle {\text{OPT}}(S,C)} 11 9 ( 6 k + 4 + 3 k + 2 ) + 6 9 {\displaystyle {\frac {11}{9}}(6k+4+3k+2)+{\frac {6}{9}}}

Производительность с делимыми размерами элементов

Важным частным случаем упаковки в контейнеры является тот случай, когда размеры элементов образуют делимую последовательность (также называемую факторизованной ). Частный случай делимых размеров элементов возникает при распределении памяти в компьютерных системах, где размеры элементов являются степенями 2. В этом случае FFD всегда находит оптимальную упаковку. [6] : Теор.2 

Свойства монотонности

Вопреки интуиции, не является монотонной функцией C. [7] : Рис.4  Аналогично, не является монотонной функцией размеров элементов в S : возможно, что элемент уменьшится в размере, но количество ячеек увеличится. F F D ( S , C ) {\displaystyle FFD(S,C)} F F D ( S , C ) {\displaystyle FFD(S,C)}

Однако алгоритм FFD обладает свойством «асимптотической монотонности», определяемым следующим образом. [7] : Лем.2.1 

  • Для каждого экземпляра S и целого числа m пусть MinCap( S,m ) будет наименьшей емкостью C такой, что O P T ( S , C ) ≤ m {\displaystyle OPT(S,C)\leq m}
  • Для каждого целого числа m пусть MinRatio( m ) будет инфимумом чисел r ≥1 таким образом, что для всех входных наборов S , . Это величина, на которую нам нужно «раздуть» ячейки, чтобы FFD достиг оптимального количества ячеек. F F D ( S , r ⋅ MinCap ( S , m ) ) ≤ m {\displaystyle FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m}
  • Тогда для каждого входа S и для каждого r ≥ MinRatio( m ), . Это показывает, в частности, что инфимум в приведенном выше определении можно заменить минимумом. F F D ( S , r ⋅ MinCap ( S , m ) ) ≤ m {\displaystyle FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m}

Примеры

Например, предположим, что входные данные следующие:

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

Вместимостью 60, FFD упаковывает 3 контейнера:

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

Но при емкости 61 FFD вмещает 4 контейнера:

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

Это происходит потому, что при емкости 61 число 17 помещается в первый контейнер и, таким образом, блокирует путь к следующим 8, 8.

В качестве другого примера [8] : Пример 5.1   предположим, что входы следующие: 51, 28, 28, 28, 27, 25, 12, 12, 10, 10, 10, 10, 10, 10, 10, 10. При емкости 75 FFD упаковывает 4 контейнера:

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

Но при вместимости 76 ему понадобится 5 контейнеров:

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

Рассмотрим приведенный выше пример с емкостью 60. Если 17 станет 16, то результирующая упаковка будет следующей:

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

Модифицированный первый подходящий-убывающий

Модифицированное уменьшение первого соответствия (MFFD) [9] улучшает FFD для элементов, превышающих половину ячейки, классифицируя элементы по размеру на четыре класса: большой, средний, маленький и крошечный, что соответствует элементам с размером > 1/2 ячейки, > 1/3 ячейки, > 1/6 ячейки и более мелким элементам соответственно. Затем он проходит через пять фаз:

  1. Выделите контейнер для каждого крупного предмета, расположив его от большего к меньшему.
  2. Продвигайтесь вперед по корзинам. На каждой: Если наименьший оставшийся средний предмет не помещается, пропустите эту корзину. В противном случае поместите наибольший оставшийся средний предмет, который помещается.
  3. Пройдите назад через те ячейки, которые не содержат средний предмет. На каждой: Если два самых маленьких оставшихся маленьких предмета не помещаются, пропустите эту ячейку. В противном случае поместите самый маленький оставшийся маленький предмет и самый большой оставшийся маленький предмет, который помещается.
  4. Пройдите вперед через все ячейки. Если наименьший оставшийся предмет любого размера не помещается, пропустите эту ячейку. В противном случае поместите наибольший помещающийся предмет и оставьте его в этой ячейке.
  5. Используйте FFD, чтобы упаковать оставшиеся предметы в новые контейнеры.

Этот алгоритм был впервые изучен Джонсоном и Гэри [9] в 1985 году, где они доказали, что . Эта граница была улучшена в 1995 году Юэ и Чжаном [10], которые доказали, что . M F F D ( S , C ) ≤ ( 71 / 60 ) O P T ( S , C ) + ( 31 / 6 ) {\displaystyle MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+(31/6)} M F F D ( S , C ) ≤ ( 71 / 60 ) O P T ( S , C ) + 1 {\displaystyle MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+1}

Другие варианты

Best-fit-decreasing (BFD) очень похож на FFD, за исключением того, что после сортировки списка он обрабатывается с помощью best-fit bin packing . Его асимптотическое отношение аппроксимации такое же, как у FFD - 11/9.

Реализации

  • Python: Пакет prtpy содержит реализацию метода уменьшения по первому подходящему множеству.

Смотрите также

Ссылки

  1. ^ Джонсон, Дэвид С. (1973). «Почти оптимальные алгоритмы упаковки контейнеров» (PDF) . Массачусетский технологический институт .
  2. ^ Бейкер, Бренда С. (1985). «Новое доказательство алгоритма убывающей упаковки ячеек первым подходящим набором». J. Algorithms . 6 (1): 49– 70. doi :10.1016/0196-6774(85)90018-5.
  3. ^ Юэ, Миньи (октябрь 1991 г.). «Простое доказательство неравенства FFD (L) ≤ 11/9 OPT (L) + 1, ∀L для алгоритма упаковки контейнеров FFD». Acta Mathematicae Applicatae Sinica . 7 (4): 321–331 . doi : 10.1007/BF02009683. S2CID  189915733.
  4. ^ Ли, Ронгхэн; Юэ, Миньи (август 1997 г.). «Доказательство FFD(L) < -OPT(L) + 7/9». Chinese Science Bulletin . 42 (15): 1262– 1265. Bibcode : 1997ChSBu..42.1262L. doi : 10.1007/BF02882754. S2CID  93280100.
  5. ^ ab Dósa, György (2007). "The Tight Bound of First Fit Decreasing bin-Packing Algorithm is FFD(I) ≤ 11/9OPT(I) + 6/9". В Chen Bo; Mike Paterson; Zhang Guochuan (ред.). Combinatorics, Algorithms, Probabilistic and Experimental Methodologies . First International Symposium, ESCAPE 2007, Hangzhou, China, April 7–9, 2007. Lecture Notes in Computer Science. Vol. 4614. pp.  1– 11. doi :10.1007/978-3-540-74450-4_1. ISBN 978-3-540-74449-8.
  6. ^ Коффман, Э. Г.; Гарей, М. Р.; Джонсон, Д. С. (1987-12-01). «Упаковка контейнеров с делимыми размерами предметов». Журнал сложности . 3 (4): 406– 428. doi :10.1016/0885-064X(87)90009-4. ISSN  0885-064X.
  7. ^ ab Coffman, EG Jr.; Garey, MR; Johnson, DS (1978-02-01). «Применение упаковки контейнеров к многопроцессорному планированию». SIAM Journal on Computing . 7 (1): 1– 17. doi :10.1137/0207001. ISSN  0097-5397.
  8. ^ Хуан, Синь; Лу, Пиньян (2021-07-18). «Алгоритмическая структура для аппроксимации распределения максиминной доли домашних дел». Труды 22-й конференции ACM по экономике и вычислениям . EC '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр.  630–631 . arXiv : 1907.04505 . doi : 10.1145/3465456.3467555. ISBN 978-1-4503-8554-1. S2CID  195874333.
  9. ^ ab Джонсон, Дэвид С.; Гари, Майкл Р. (октябрь 1985 г.). «Теорема 7160 для упаковки контейнеров». Журнал сложности . 1 (1): 65– 106. doi : 10.1016/0885-064X(85)90022-6 .
  10. ^ Юэ, Миньи; Чжан, Лэй (июль 1995 г.). «Простое доказательство неравенства MFFD(L) ≤ 71/60 OPT(L) + 1,L для алгоритма упаковки ячеек MFFD». Acta Mathematicae Applicatae Sinica . 11 (3): 318– 330. doi :10.1007/BF02011198. S2CID  118263129.
Retrieved from "https://en.wikipedia.org/w/index.php?title=First-fit-decreasing_bin_packing&oldid=1268957036"