Задача об упаковке в контейнеры: различия между версиями

Три из вышеупомянутых алгоритмов (FF, BF и NF) являются ''онлайновыми'', поскольку они упаковывают предметы в заданном порядке, не принимая во внимание размеры или количество последующих предметов. Как было замечено впоследствии во многих контекстах, ограничение онлайновыми ситуациями может серьезно ограничить способность алгоритма производить хорошие решения. Возможно, первым доказанным ограничением такого типа была теорема Яо [ ] о том, что ни один онлайновый алгоритм A для упаковки в контейнеры не может иметь <math>R^{\infty}_{A} < 1,5</math>. С тех пор это ограничение было улучшено до следующего:

В работе Яо также был представлен онлайн-алгоритм ''Revised First Fit'' (RFF), который имел <math>R^{\infty}_{RFF} = 5/3 = 1,666...</math>  и, следовательно, был ближе к этой нижней границе, чем FF и BF. Этот алгоритм работал путем разделения предметов на четыре класса по критерию размера и индекса, а затем использования различных правил упаковки (и самих упаковок) для каждого класса. Последующие алгоритмы улучшали его за счет введения все большего количества классов. В настоящее время самым эффективным является онлайновый алгоритм ''Harmonic++'' (H++) из работы [21]:

Константа 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. Тогда определим

'''Теорема 9 [16, 20]. Для <math>A \in \{ FFD, BFD, OPT \}</math> выполняется <math>EW^n_A(U(0, 1]) = \Theta(\sqrt{n}).</math>

Теорема 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>

'''1. Если <math>EW^n_{OPT}(F) = \Theta(\sqrt{n})</math>, то <math>EW^n_{SS}(F) = \Theta(\sqrt{n}).</math>'''

'''Кроме того, простая модификация SS позволяет исключить случай <math>\Theta(log \; n) \}</math> в условии 2.

Данная задача является благодатной почвой для экспериментального анализа, и многие из приведенных выше теорем были впервые предположены на основе экспериментальных результатов. Например, эксперименты, описанные в [ ], послужили основой для теорем 10 и 12, а исследования в [ ] – для теоремы 14.