4551
правка
Задача об упаковке в контейнеры: различия между версиями
Материал из WEGA
Задача об упаковке в контейнеры (посмотреть исходный код)
Версия от 23:08, 21 января 2024
, 21 январь→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 96: | Строка 96: | ||
Последнее определение включено, поскольку <math>ER^{\infty}_A(F) = 1</math> встречается достаточно часто, чтобы более тонкие различия имели смысл. Например, в начале 1980-х годов было замечено, что для распределения F = U(0, 1], в котором размеры элементов равномерно распределены на интервале (0, 1], <math>ER^{\infty}_{FFD}(F) = ER^{\infty}_{BFD}(F) = 1</math>, как следствие последующих более детальных результатов. | Последнее определение включено, поскольку <math>ER^{\infty}_A(F) = 1</math> встречается достаточно часто, чтобы более тонкие различия имели смысл. Например, в начале 1980-х годов было замечено, что для распределения F = U(0, 1], в котором размеры элементов равномерно распределены на интервале (0, 1], <math>ER^{\infty}_{FFD}(F) = ER^{\infty}_{BFD}(F) = 1</math>, как следствие последующих более детальных результатов. | ||
'''Теорема 9 [16, 20]. Для <math>A \in \{ FFD, BFD, OPT \}</math> выполняется <math>EW^n_A(U(0, 1]) = \Theta(\sqrt{n}).</math> | |||
Однако это хорошее поведение не распространяется на алгоритмы с ограниченным количеством контейнеров NF и | К некоторому удивлению, позже было обнаружено, что онлайновые алгоритмы FF и BF также имеют сублинейные ожидаемые потери и, следовательно, <math>ER^{\infty}_A(U(0, 1]) = 1.</math> | ||
'''Теорема 10 [5, 19].''' | |||
<math>EW^n_{FF}(U(0, 1]) = \Theta(n^{2/3})</math> | |||
<math>EW^n_{BF}(U(0, 1]) = \Theta(n^{1/2} \; log^{3/4} \; n)</math> | |||
Однако это хорошее поведение не распространяется на алгоритмы с ограниченным количеством контейнеров NF и <math>H_k</math>: | |||
'''Теорема 11 [6, 18].''' | |||
<math>ER^{\infty}_{NF}(U(0, 1]) = 4/3 = 1,333...</math> | |||
<math>lim_{k \to \infty} ER_{H_k}(U(0, 1]) = \pi^2/3 - 2 = 1,2899...</math> | |||
Все приведенные выше результаты, кроме двух последних, используют тот факт, что распределение U(0, 1] симметрично относительно 1/2; и, следовательно, оптимальная упаковка состоит в основном из двухэлементных контейнеров, причем элементы размера s > 1/2 сопоставляются с элементами меньшего размера, очень близкого к 1 – s. Доказательства, по сути, показывают, что рассматриваемые алгоритмы хорошо справляются с построением таких паросочетаний. Однако на практике, очевидно, будут возникать ситуации, когда требуется нечто большее, чем простое соответствие. Для моделирования таких ситуаций исследователи сначала обратились к распределениям U(0, b], 0 < b < 1, где размеры элементов выбираются равномерно из интервала (0, b]. Моделирование показало, что такие распределения ухудшают работу онлайновых алгоритмов FF и BF, у которых ER1A(U(0, b]) > 1 для всех b 2 (0, 1). Как ни удивительно, они улучшают ситуацию для FFD и BFD (и оптимальной упаковки). | Все приведенные выше результаты, кроме двух последних, используют тот факт, что распределение U(0, 1] симметрично относительно 1/2; и, следовательно, оптимальная упаковка состоит в основном из двухэлементных контейнеров, причем элементы размера s > 1/2 сопоставляются с элементами меньшего размера, очень близкого к 1 – s. Доказательства, по сути, показывают, что рассматриваемые алгоритмы хорошо справляются с построением таких паросочетаний. Однако на практике, очевидно, будут возникать ситуации, когда требуется нечто большее, чем простое соответствие. Для моделирования таких ситуаций исследователи сначала обратились к распределениям U(0, b], 0 < b < 1, где размеры элементов выбираются равномерно из интервала (0, b]. Моделирование показало, что такие распределения ухудшают работу онлайновых алгоритмов FF и BF, у которых ER1A(U(0, b]) > 1 для всех b 2 (0, 1). Как ни удивительно, они улучшают ситуацию для FFD и BFD (и оптимальной упаковки). | ||
