Уменьшающаяся упаковка в контейнер по принципу «первая установка»

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

Описание

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

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

Вкратце: FFD упорядочивает товары по убыванию размера, а затем вызывает упаковку в корзину по первому требованию .

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

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

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

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

Анализ эффективности FFD проводился в несколько этапов. Ниже, $FFD(S,C)$ обозначает количество ячеек, используемых FFD для входного набора S и емкости ячеек C.

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

Худший пример

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

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

Если имеется 4 копии $B_{1}$ и 2 экземпляра $B_{2}$ в оптимальном решении FFD вычислит следующие интервалы:

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

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

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

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

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

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

Вопреки интуиции, $FFD(S,C)$ является не монотонной функцией C . ^{[ 7 ]}^{: Рис.4} Сходным образом, $FFD(S,C)$ не является монотонной функцией размеров предметов в S : возможно, что предмет уменьшается в размерах, но количество ячеек увеличивается.

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

Для каждого экземпляра S и целого числа m пусть MinCap( S,m ) будет наименьшей емкостью C такой, что $OPT(S,C)\leq m$
Для каждого целого числа m пусть MinRatio( m ) будет нижней границей чисел r ≥1 таких, что для всех входных наборов S , $FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m$ . Это величина, на которую нам нужно «раздуть» ячейки, чтобы FFD достиг оптимального количества ячеек.
Тогда для каждого входа S и для каждого r ≥ MinRatio( m ) $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 корзины и более мелкие предметы соответственно. Затем он проходит пять этапов:

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

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

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

Метод наилучшего соответствия (BFD) очень похож на FFD, за исключением того, что после сортировки списка он обрабатывается методом наилучшей упаковки в корзину . Его коэффициент асимптотической аппроксимации такой же, как у FFD – 11/9.

Реализации

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

См. также

Алгоритм Multifit — алгоритм планирования идентичных машин , который использует FFD в качестве подпрограммы.

Ссылки

^ Джонсон, Дэвид С. (1973). «Почти оптимальные алгоритмы упаковки контейнеров» (PDF) . Массачусетский технологический институт .
^ Бейкер, Бренда С. (1985). «Новое доказательство алгоритма убывающей упаковки контейнеров первого подходящего». Дж. Алгоритмы . 6 (1): 49–70. дои : 10.1016/0196-6774(85)90018-5 .
^ Юэ, Миньи (октябрь 1991 г.). «Простое доказательство неравенства FFD(L) ≤ 11/9 OPT(L) + 1, ∀L для алгоритма упаковки контейнеров FFD». Acta Mathematicae Applicatae Sinica 7 (4): 321–331. дои : 10.1007/BF02009683 . S2CID 189915733 .
^ Ли, Жунхэн; Юэ, Миньи (август 1997 г.). «Доказательство FFD(L) <-OPT(L) + 7/9». Китайский научный бюллетень . 42 (15): 1262–1265. Бибкод : 1997ЧСБу..42.1262Л . дои : 10.1007/BF02882754 . S2CID 93280100 .
^ Jump up to: ^а ^б Доса, Дьёрдь (2007). «Точная граница алгоритма упаковки контейнеров с уменьшением первого соответствия составляет FFD(I) ≤ 11/9OPT(I) + 6/9». В Чэнь Бо; Майк Патерсон; Чжан Гоочуань (ред.). Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии . Первый международный симпозиум ESCAPE 2007, Ханчжоу, Китай, 7–9 апреля 2007 г. Конспекты лекций по информатике. Том. 4614. стр. 1–11. дои : 10.1007/978-3-540-74450-4_1 . ISBN 978-3-540-74449-8 .
^ Коффман, Э.Г.; Гэри, MR; Джонсон, Д.С. (1 декабря 1987 г.). «Корзинная упаковка с предметами, делящимися по размеру» . Журнал сложности . 3 (4): 406–428. дои : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .
^ Jump up to: ^а ^б Коффман, Э.Г. младший; Гэри, MR; Джонсон, DS (1 февраля 1978 г.). «Применение упаковки контейнеров для многопроцессорного планирования» . SIAM Journal по вычислительной технике . 7 (1): 1–17. дои : 10.1137/0207001 . ISSN 0097-5397 .
^ Хуан, Синь; Лу, Пиньян (18 июля 2021 г.). «Алгоритмическая основа для приближенного распределения долей по дому» . Материалы 22-й конференции ACM по экономике и вычислениям . ЭК '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 630–631. arXiv : 1907.04505 . дои : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1 . S2CID 195874333 .
^ Jump up to: ^а ^б Джонсон, Дэвид С; Гэри, Майкл Р. (октябрь 1985 г.). «Теорема 7160 для упаковки контейнеров» . Журнал сложности . 1 (1): 65–106. дои : 10.1016/0885-064X(85)90022-6 .
^ Юэ, Миньи; Чжан, Лей (июль 1995 г.). «Простое доказательство неравенства MFFD(L) ≤ 71/60 OPT(L) + 1,L для алгоритма упаковки контейнеров MFFD». Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. дои : 10.1007/BF02011198 . S2CID 118263129 .

[johnson73-1] Джонсон, Дэвид С. (1973). «Почти оптимальные алгоритмы упаковки контейнеров» (PDF) . Массачусетский технологический институт .

[Backer85-2] Бейкер, Бренда С. (1985). «Новое доказательство алгоритма убывающей упаковки контейнеров первого подходящего». Дж. Алгоритмы . 6 (1): 49–70. дои : 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. дои : 10.1007/BF02009683 . S2CID 189915733 .

[4] Ли, Жунхэн; Юэ, Миньи (август 1997 г.). «Доказательство FFD(L) <-OPT(L) + 7/9». Китайский научный бюллетень . 42 (15): 1262–1265. Бибкод : 1997ЧСБу..42.1262Л . дои : 10.1007/BF02882754 . S2CID 93280100 .

[Dosa07-5] Jump up to: ^а ^б Доса, Дьёрдь (2007). «Точная граница алгоритма упаковки контейнеров с уменьшением первого соответствия составляет FFD(I) ≤ 11/9OPT(I) + 6/9». В Чэнь Бо; Майк Патерсон; Чжан Гоочуань (ред.). Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии . Первый международный симпозиум ESCAPE 2007, Ханчжоу, Китай, 7–9 апреля 2007 г. Конспекты лекций по информатике. Том. 4614. стр. 1–11. дои : 10.1007/978-3-540-74450-4_1 . ISBN 978-3-540-74449-8 .

[6] Коффман, Э.Г.; Гэри, MR; Джонсон, Д.С. (1 декабря 1987 г.). «Корзинная упаковка с предметами, делящимися по размеру» . Журнал сложности . 3 (4): 406–428. дои : 10.1016/0885-064X(87)90009-4 . ISSN 0885-064X .

[:0-7] Jump up to: ^а ^б Коффман, Э.Г. младший; Гэри, MR; Джонсон, DS (1 февраля 1978 г.). «Применение упаковки контейнеров для многопроцессорного планирования» . SIAM Journal по вычислительной технике . 7 (1): 1–17. дои : 10.1137/0207001 . ISSN 0097-5397 .

[:3-8] Хуан, Синь; Лу, Пиньян (18 июля 2021 г.). «Алгоритмическая основа для приближенного распределения долей по дому» . Материалы 22-й конференции ACM по экономике и вычислениям . ЭК '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 630–631. arXiv : 1907.04505 . дои : 10.1145/3465456.3467555 . ISBN 978-1-4503-8554-1 . S2CID 195874333 .

[JohnsonGarey19852-9] Jump up to: ^а ^б Джонсон, Дэвид С; Гэри, Майкл Р. (октябрь 1985 г.). «Теорема 7160 для упаковки контейнеров» . Журнал сложности . 1 (1): 65–106. дои : 10.1016/0885-064X(85)90022-6 .

[YueZhang19952-10] Юэ, Миньи; Чжан, Лей (июль 1995 г.). «Простое доказательство неравенства MFFD(L) ≤ 71/60 OPT(L) + 1,L для алгоритма упаковки контейнеров MFFD». Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. дои : 10.1007/BF02011198 . S2CID 118263129 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]