4551
правка
Задача об упаковке в контейнеры: различия между версиями
Материал из WEGA
Задача об упаковке в контейнеры (посмотреть исходный код)
Версия от 23:24, 21 января 2024
, 21 январь→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 134: | Строка 134: | ||
'''Дискретные распределения''' | '''Дискретные распределения''' | ||
Во многих приложениях размеры предметов берутся из конечного множества, а не из непрерывного распределения, рассмотренного выше. Поэтому в последнее время при изучении поведения алгоритмов упаковки контейнеров в среднем случае обращаются к ''дискретным распределениям''. Такое распределение задается конечным списком | Во многих приложениях размеры предметов берутся из конечного множества, а не из непрерывного распределения, рассмотренного выше. Поэтому в последнее время при изучении поведения алгоритмов упаковки контейнеров в среднем случае обращаются к ''дискретным распределениям''. Такое распределение задается конечным списком <math>s_1, s_2, ..., s_d</math> рациональных размеров и соответствующей рациональной вероятностью <math>p_i</math> для каждого <math>s_i</math>. Замечательный результат Куркубетиса и Вебера [7] гласит: | ||
Дискретным аналогом непрерывного распределения U(0, b] является распределение U{j, k}, где размеры равны 1/k | '''Теорема 13 [7]. Для любого дискретного распределения F значение <math>EW^n_{OPT}(F)</math> равно <math>\Theta(n)</math>, <math>\Theta(\sqrt{n})</math> либо <math>O(1)</math>.''' | ||
Дискретным аналогом непрерывного распределения U(0, b] является распределение U{j, k}, где размеры равны 1/k, 2/k, ... j/k, а все вероятности равны 1/j. Моделирование показывает, что поведение FF и BF в дискретном случае качественно схоже с поведением в непрерывном случае, в то время как поведение FFD и BFD значительно более причудливо [3]. Особо следует отметить распределение F = U{6, 13}, для которого <math>ER^{\infty}_{FFD}(F)</math> строго больше <math>ER^{\infty}_{FF}(F)</math>, что противоречит всем ранее проведенным сравнениям между двумя алгоритмами. | |||
Однако в случае дискретных распределений все стандартные алгоритмы уступают новому онлайновому алгоритму, которые называется ''алгоритмом суммы квадратов'' (SS). Обратите внимание, что поскольку все размеры предметов рациональны, их можно масштабировать так, чтобы они (также как размер контейнера B) были целочисленными. Тогда в любой момент работы онлайнового алгоритма текущую схему упаковки можно обобщить, указав для каждого <math>h, 1 \le h \le B</math>, количество <math>n_h</math> контейнеров, содержащих предметы общей величиной h. В алгоритме SS каждый предмет упаковывается таким образом, чтобы минимизировать <math>\sum_{h = 1}^{B - 1} \; n^2_h</math>. | |||
'''Теорема 14 [9]. Для любого дискретного распределения F справедливы следующие утверждения.''' | |||
Кроме того, простая модификация SS позволяет устранить случай ©(log n) условия 2. | Кроме того, простая модификация SS позволяет устранить случай ©(log n) условия 2. | ||
