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

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