Задача об упаковке в контейнеры: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 78: | Строка 78: | ||
Константа 1,691 возникает и во многих других контекстах упаковки в контейнеры. Обычно она обозначается <math>h_{\infty}</math> и равна <math>\sum_{i = 1}^{\infty} (1/t_i)</math>, где <math>t_1 = 1</math>, а для i > 1 <math>t_i = t_{i - 1}(t_{i - 1} + 1)</math>. Нижняя граница в Теореме 8 является строгой благодаря существованию алгоритмов <math>Нarmonic_k</math> (<math>H_k</math>) из [17]. <math>H_k</math> – это алгоритм, основанный на классах, в котором предметы делятся на классы <math>C_h, 1 \le h \le k</math>, причем <math>C_k</math> состоит из всех предметов размером 1/k или меньше, а <math>C_h, 1 \le h < k</math>, состоит из всех <math>a_i</math>, таких, что <math>1/(h + 1) < s(a_i) \le 1/h</math>. Затем предметы каждого класса упаковываются NF в отдельную упаковку, предназначенную только для этого класса. Таким образом, в любой момент времени открыто не более k контейнеров. В [17] было показано, что | Константа 1,691 возникает и во многих других контекстах упаковки в контейнеры. Обычно она обозначается <math>h_{\infty}</math> и равна <math>\sum_{i = 1}^{\infty} (1/t_i)</math>, где <math>t_1 = 1</math>, а для i > 1 <math>t_i = t_{i - 1}(t_{i - 1} + 1)</math>. Нижняя граница в Теореме 8 является строгой благодаря существованию алгоритмов <math>Нarmonic_k</math> (<math>H_k</math>) из [17]. <math>H_k</math> – это алгоритм, основанный на классах, в котором предметы делятся на классы <math>C_h, 1 \le h \le k</math>, причем <math>C_k</math> состоит из всех предметов размером 1/k или меньше, а <math>C_h, 1 \le h < k</math>, состоит из всех <math>a_i</math>, таких, что <math>1/(h + 1) < s(a_i) \le 1/h</math>. Затем предметы каждого класса упаковываются NF в отдельную упаковку, предназначенную только для этого класса. Таким образом, в любой момент времени открыто не более k контейнеров. В [17] было показано, что <math>lim_{k \to \infty} R^{\infty}_{H_k} = h_{\infty} = 1,691...</math> Это даже лучше, чем асимптотическое наихудшее соотношение 1,7 для алгоритмов FF и BF, работающих с неограниченным количеством контейнеров, хотя следует отметить, что вариант BF с ограниченным их количеством, в котором все контейнеры, кроме двух наиболее полных, закрыты, также имеет <math>R^{\infty}_A = 1,7</math>. | ||
'''Поведение в среднем случае''' | '''Поведение в среднем случае''' | ||
'''Непрерывные распределения''' | |||
Задача об упаковке в контейнеры также послужила ранним испытательным полигоном для изучения поведения аппроксимационных алгоритмов в среднем случае. Пусть F – распределение на интервале (0, 1], а <math>L_n</math> – список из n элементов с размерами элементов, выбранными независимо в соответствии с распределением F. Для любого списка L обозначим за s(L) нижнюю границу OPT(L), полученную суммированием размеров всех элементов в L. Тогда определим | |||
<math>ER^n_A(F) = E [ A(L_n) / OPT(L_n)],</math> | |||
<math>ER^{\infty}_A(F) = lim_{n \to \infty} sup \; ER^n_A,</math> | |||
<math>EW^n_A(F) = E [ A(L_n) - s(L_n)].</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>, как следствие последующих более детальных результатов. | ||
Theorem 9 [16, 20]. Для A 2 fFFD; BFD; OPTg, | Theorem 9 [16, 20]. Для A 2 fFFD; BFD; OPTg, | ||