4551
правка
Задача об упаковке в контейнеры: различия между версиями
Материал из WEGA
Задача об упаковке в контейнеры (посмотреть исходный код)
Версия от 22:46, 21 января 2024
, 21 январь→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 45: | Строка 45: | ||
'''Теорема 5 [15]. <math>R^{\infty}_{KK} = 1</math> и существует константа c такая, что для всех списков L выполняется соотношение | '''Теорема 5 [15]. <math>R^{\infty}_{KK} = 1</math> и существует константа c такая, что для всех списков L выполняется соотношение''' | ||
<math>KK(L) \le OPT(L) + c \; log^2 \; (OPT(L)).</math> | <math>KK(L) \le OPT(L) + c \; log^2 \; (OPT(L)).</math> | ||
| Строка 58: | Строка 58: | ||
'''Теорема 6 [23]. Если A – онлайновый алгоритм для упаковки контейнеров, то <math>R^{\infty}_{A} \ge 1,540...</math> | '''Теорема 6 [23]. Если A – онлайновый алгоритм для упаковки контейнеров, то <math>R^{\infty}_{A} \ge 1,540...</math>''' | ||
| Строка 67: | Строка 67: | ||
'''Теорема 7 [21]. <math>R^{\infty}_{H++} \le 1,58889.</math> | '''Теорема 7 [21]. <math>R^{\infty}_{H++} \le 1,58889.</math>''' | ||
| Строка 74: | Строка 74: | ||
Алгоритм NF, помимо того, что он работает в режиме онлайн, обладает еще одним свойством, которое стоит отметить: в любой момент времени для приема дополнительных предметов остается открытым не более чем постоянное число частично заполненных контейнеров. В случае NF эта константа равна 1 – поместить дополнительные предметы можно только в последний частично заполненный контейнер. Ограничение количества открытых контейнеров может быть необходимо в некоторых приложениях, например, при загрузке грузовиков на погрузочных платформах. Однако это обстоятельство накладывает дополнительные ограничения на поведение алгоритма. | Алгоритм NF, помимо того, что он работает в режиме онлайн, обладает еще одним свойством, которое стоит отметить: в любой момент времени для приема дополнительных предметов остается открытым не более чем постоянное число частично заполненных контейнеров. В случае NF эта константа равна 1 – поместить дополнительные предметы можно только в последний частично заполненный контейнер. Ограничение количества открытых контейнеров может быть необходимо в некоторых приложениях, например, при загрузке грузовиков на погрузочных платформах. Однако это обстоятельство накладывает дополнительные ограничения на поведение алгоритма. | ||
Константа 1,691 возникает и во многих других контекстах упаковки в контейнеры. Обычно она обозначается | '''Теорема 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 является строгой благодаря существованию алгоритмов <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] было показано, что limk!1 R1H = h1 = 1,691. Это даже лучше, чем асимптотическое наихудшее соотношение 1.7 для алгоритмов FF и BF, работающих с неограниченным количеством контейнеров, хотя следует отметить, что вариант BF с ограниченным их количеством, в котором все контейнеры, кроме двух наиболее полных, закрыты, также имеет | |||
