4430
правок
Задача об упаковке в контейнеры: различия между версиями
Материал из WEGA
Задача об упаковке в контейнеры (посмотреть исходный код)
Версия от 23:14, 21 января 2024
, 21 январь→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 120: | Строка 120: | ||
Все приведенные выше результаты, кроме двух последних, используют тот факт, что распределение U(0, 1] симметрично относительно 1/2; и, следовательно, оптимальная упаковка состоит в основном из двухэлементных контейнеров, причем элементы размера s > 1/2 сопоставляются с элементами меньшего размера, очень близкого к 1 – s. Доказательства, по сути, показывают, что рассматриваемые алгоритмы хорошо справляются с построением таких паросочетаний. Однако на практике, очевидно, будут возникать ситуации, когда требуется нечто большее, чем простое соответствие. Для моделирования таких ситуаций исследователи сначала обратились к распределениям U(0, b], 0 < b < 1, где размеры элементов выбираются равномерно из интервала (0, b]. Моделирование показало, что такие распределения ухудшают работу онлайновых алгоритмов FF и BF, у которых | Все приведенные выше результаты, кроме двух последних, используют тот факт, что распределение U(0, 1] симметрично относительно 1/2; и, следовательно, оптимальная упаковка состоит в основном из двухэлементных контейнеров, причем элементы размера s > 1/2 сопоставляются с элементами меньшего размера, очень близкого к 1 – s. Доказательства, по сути, показывают, что рассматриваемые алгоритмы хорошо справляются с построением таких паросочетаний. Однако на практике, очевидно, будут возникать ситуации, когда требуется нечто большее, чем простое соответствие. Для моделирования таких ситуаций исследователи сначала обратились к распределениям U(0, b], 0 < b < 1, где размеры элементов выбираются равномерно из интервала (0, b]. Моделирование показало, что такие распределения ухудшают работу онлайновых алгоритмов FF и BF, у которых <math>ER^{\infty}_A(U(0, b]) > 1</math> для всех <math>b \in (0, 1)</math>. Как ни удивительно, они улучшают ситуацию для FFD и BFD (и оптимальной упаковки). | ||
Теорема 12 [2, 14]. | Теорема 12 [2, 14]. | ||
1. Для <math>0 < b \le 1/2</math> '''и''' <math>A \in \{FFD, BFD\}</math> выполняется <math>EW^n_A(U(0, b]) = O(1).</math> | |||
2. Для <math>1/2 < b < 1</math> '''и''' <math>A \in \{FFD, BFD\}</math> выполняется <math>EW^n_A(U(0, b]) = \Theta(n^{1/3}).</math> | |||
3. Для <math>0 < b < 1</math> выполняется <math>EW^n_{OPT}(U(0, b]) = O(1).</math> | |||
'''Дискретные распределения''' | '''Дискретные распределения''' | ||
Во многих приложениях размеры предметов берутся из конечного множества, а не из непрерывного распределения, рассмотренного выше. Поэтому в последнее время при изучении поведения алгоритмов упаковки контейнеров в среднем случае обращаются к дискретным распределениям. Такое распределение задается конечным списком s1, s2, ..., sd рациональных размеров и соответствующей рациональной вероятностью pi для каждого si. Замечательный результат Куркубетиса и Вебера [ ] гласит: | |||
Во многих приложениях размеры предметов берутся из конечного множества, а не из непрерывного распределения, рассмотренного выше. Поэтому в последнее время при изучении поведения алгоритмов упаковки контейнеров в среднем случае обращаются к ''дискретным распределениям''. Такое распределение задается конечным списком s1, s2, ..., sd рациональных размеров и соответствующей рациональной вероятностью pi для каждого si. Замечательный результат Куркубетиса и Вебера [ ] гласит: | |||
Теорема 13 [ ]. Для любого дискретного распределения F, EWnopT{F) является либо &(n), &{jn), либо O(l). | Теорема 13 [ ]. Для любого дискретного распределения F, EWnopT{F) является либо &(n), &{jn), либо O(l). | ||
