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

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

<math>R^n_A = max \{ A(L)/OPT(L): L</math> – список с <math>OPT(L) = n\}</math>

'''Теорема 3 [13]. <math>R^{\infty}_{BF} = 17/10.</math>'''

'''Теорема 4 [12, 13]. <math>R^{\infty}_{FFD} = R^{\infty}_{BFD} = 11/9 = 1,222...</math>'''

<math>KK(L) \le OPT(L) + c \; log^2 \; (OPT(L)).</math>

К сожалению, время работы KK оказывается больше <math>O(n^8)</math>, так что BFD и FFD остаются гораздо более практичными альтернативами.

'''Теорема 7 [21]. <math>R^{\infty}_{H++} \le 1,58889.</math>'''

'''Теорема 8 [17]. Для любого онлайнового алгоритма с ограниченным количеством контейнеров <math>R^{\infty}_{A} \ge 1,691...</math>'''

Константа 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 является строгой благодаря существованию алгоритмов ''Нarmonic''<math>_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>.

<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, у которых <math>ER^{\infty}_A(U(0, b]) > 1</math> для всех <math>b \in (0, 1)</math>. Как ни удивительно, они улучшают ситуацию для FFD и BFD (и оптимальной упаковки).

'''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>'''

 

 

'''Теорема 13 [7]. Для любого дискретного распределения F значение <math>EW^n_{OPT}(F)</math> равно <math>\Theta(n)</math>, <math>\Theta(\sqrt{n})</math> либо <math>O(1)</math>.'''

 

 

Дискретным аналогом непрерывного распределения U(0, b] является распределение U{j, k}, где размеры равны 1/k, 2/k, ... j/k, а все вероятности равны 1/j. Моделирование показывает, что поведение FF и BF в дискретном случае качественно схоже с поведением в непрерывном случае, в то время как поведение FFD и BFD значительно более причудливо [3]. Особо следует отметить распределение F = U{6, 13}, для которого <math>ER^{\infty}_{FFD}(F)</math> строго больше <math>ER^{\infty}_{FF}(F)</math>, что противоречит всем ранее проведенным сравнениям между двумя алгоритмами.

 

 

Однако в случае дискретных распределений все стандартные алгоритмы уступают новому онлайновому алгоритму, которые называется ''алгоритмом суммы квадратов'' (SS). Обратите внимание, что поскольку все размеры предметов рациональны, их можно масштабировать так, чтобы они (также как размер контейнера B) были целочисленными. Тогда в любой момент работы онлайнового алгоритма текущую схему упаковки можно обобщить, указав для каждого <math>h, 1 \le h \le B</math>, количество <math>n_h</math> контейнеров, содержащих предметы общей величиной h. В алгоритме SS каждый предмет упаковывается таким образом, чтобы минимизировать <math>\sum_{h = 1}^{B - 1} \; n^2_h</math>.

 

'''Теорема 14 [9]. Для любого дискретного распределения F справедливы следующие утверждения:'''

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

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

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

Возможно, наиболее фундаментальной нерешенной проблемой, связанной с упаковкой контейнеров, является следующая. Как было отмечено выше, существует алгоритм с полиномиальным временем выполнения (KK), упаковка которого находится в пределах <math>O(log^2 \; (OPT))</math> контейнеров от оптимальной. Возможно ли улучшить этот коэффициент? Насколько известно на данный момент, может существовать алгоритм с полиномиальным временем выполнения, который всегда отличается на один контейнер от оптимального, даже если <math>P \ne NP</math>.

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

*  [[Аппроксимационные схемы для задачи об упаковке в контейнеры]]