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

Для большинства задач минимизации стандартной метрикой наихудшего случая для аппроксимационного алгоритма A является максимальное для всех экземпляров I отношение A(I)/OPT(I), где A(I) – величина решения, генерируемого A, а OPT(I) – величина оптимального решения. Однако в случае упаковки контейнеров имеются ограничения на эту метрику «абсолютно наихудшего отношения». Задача определения того, является ли OPT(I) = 2, уже является NP-трудной – и, следовательно, ни один аппроксимационный алгоритм с полиномиальным временем выполнения не может иметь абсолютное наихудшее отношение лучше 1,5, если не выполняется P = NP. Чтобы лучше понимать поведение алгоритмов упаковки в контейнеры в типичной ситуации, когда заданный список L требует большого количества контейнеров, исследователи используют более тонкую метрику упаковки – ''асимптотическое отношение в наихудшем случае'', <math>R_A^{\infty}</math>. Оно определяется в два этапа следующим образом.

В дополнение к FF, еще пять простых эвристик были изучены в самом начале и послужили вдохновением для более поздних исследований. ''Best Fit'' (BF) – это вариант задачи FF, в котором каждый предмет помещается в контейнер, в который он может поместиться с наименьшим остатком свободного места; при наличии нескольких подходящих вариантов выбирается самый ранний из таких контейнеров. И FF, и BF могут быть реализованы за время O(n log n) [12]. ''Next Fit'' (NF) – еще более простой алгоритм с линейным временем выполнения, в котором первый предмет помещается в первый контейнер, а каждый следующий предмет помещается в последний непустой контейнер, если он в него помещается, в противном случае открывается новый контейнер. ''First Fit Decreasing'' (FFD) и ''Best Fit Decreasing'' (BFD) – варианты этих алгоритмов, в которых входной список сначала сортируется по размеру в порядке невозрастания, а затем применяется соответствующее правило упаковки. Для этих алгоритмов получены следующие результаты.

Приведенные выше алгоритмы относительно просты и интуитивно понятны. Если мы готовы рассмотреть более сложные алгоритмы, мы сможем добиться значительно лучших результатов. Лучший на сегодняшний день полиномиальный алгоритм упаковки в контейнеры действительно очень хорош. Это алгоритм Кармаркара-Карпа 1982 года [15], который далее будет обозначаться как KK. Он использует метод эллипсоидов, аппроксимационные алгоритмы для задачи о рюкзаке и хитроумную схему округления для получения следующих гарантий:

'''Теорема 5 [15]. <math>R^{\infty}_{KK} = 1</math> и существует константа c такая, что для всех списков L выполняется соотношение'''

Три из вышеупомянутых алгоритмов (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.