Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу

Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу

МЛ. Трутников, ctsvdimndex.ru

Аннотация. В 1993 году Коффман и Шор предложили онлайновый алгоритм упаковки прямоугольников в полосу с оценкой 0(iV“ 3) для математического ожидания незаполненной площади полосы в стандартной вероятностной модели. С тех пор вопрос о возможности улучшения этой оценки в классе онлайновых алгоритмов оставался открытым. В данной работе проанализирован принципиально новый онлайновый алгоритм упаковки, предложенный ранее

автором. Для него доказана оценка 0(_/V' “(logiV)3 “) для математического ожидания незаполненной площади полосы.

Ключевые слова: онлайновый алгоритм упаковки, вероятностный анализ качества упаковки.

Введение

Задача упаковки в полосу (в англоязычной литературе Strip packing problem) состоит в размещении множества открытых прямоугольников внутри полубесконечной вертикальной полосы единичной ширины, при этом стороны прямоугольников должны быть параллельны сторонам полосы (вращения запрещены) и прямоугольники не должны пересекаться. Нужно минимизировать «высоту упаковки» — расстояние от основания полосы до верхней грани верхнего прямоугольника в упаковке [1,2].

Задача имеет следующую естественную интерпретацию. Каждый прямоугольник — вычислительная задача, ширина прямоугольника соответствует количеству процессоров необходимых для вычисления задачи, высота — времени. Эффективное размещение прямоугольников внутри полосы требуется также в задачах разработки СБИС и раскройки материалов. Частным случаем упаковки в полосу при равенстве высот всех прямоугольников является NP -трудная задача упаковки в

контейнеры [3]. Поэтому для общей задачи упаковки в полосу интерес представляют приближенные полиномиальные алгоритмы.

Особый интерес представляют «онлайновые» алгоритмы, размещающие прямоугольники в полосе по мере их поступления, без знания параметров всех последующих прямоугольников. При анализе в среднем минимизируемой функцией является математическое ожидание незаполненной прямоугольниками площади полосы от основания полосы до верхней грани самого верхнего прямоугольника в упаковке. При этом в стандартной вероятностной модели ширины и высоты всех прямоугольников являются независимыми в совокупности равномерно распределенными на (0,1] случайными величинами [4].

Известно, что математическое ожидание незаполненной площади полосы у оптимальной упаковки есть 0{Ы112), где N — число прямоугольников. В 1993 году Коффман и Шор предложили «офлайновый»

алгоритм [4], для которого по порядку достигается оценка 0(Ш112} . В той же работе они предложили онлайновый алгоритм упаковки с оценкой 0{Ш213) для математического ожидания незаполненной площади полосы.

В 2010 году [5] был предложен новый онлайновый алгоритм с той же оценкой 0(Ы213), но не требующий знания числа прямоугольников заранее. Тем не менее вопрос о возможности улучшения оценки 0(Ы213) в классе онлайновых алгоритмов оставался открытым. Известно было, в частности, что в классе шельфовых алгоритмов [6], [7] эту оценку улучшить нельзя.

В данной работе дан положительный ответ на этот вопрос. Для принципиально нового онлайнового алгоритма упаковки из [8] доказана

оценка ^(Л^^С^Л^)372) для математического ожидания

незаполненной площади полосы.

Постановка задачи

1 Вход: N — число прямоугольников; , Ьг., / = 1,..., N — ширины

и высоты прямоугольников, являющиеся значениями независимых в совокупности равномерно распределенных на (0,1] случайных величин;

Выход: х, у, / = 1,..., N — координаты центров прямоугольников,

удовлетворяющие условию: прямоугольники без вращений и

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

ширины. Основание полосы совпадает с отрезком [(0,0), (1,0)] в Л2 , а боковые стороны полосы параллельны оси у .

Высотой упаковки назовем величину

Н = тах1(^у1+^ |

Требуется минимизировать величину

5 = Я

1=1

равную незаполненной площади полосы.

Алгоритм

В [8] предложен новый онлайновый алгоритм для рассматриваемой задачи, который мы будем анализировать в данной работе. Нпомним некоторые особенности алгоритма.

Рассмотрим следующие величины:

N14 _ N14 _ г- 1

и-------------у N + 0(1), 8----

(1 (1

а =

В основании полосы выделается <ї +1 горизонтальная область, каждая высоты и , причем і-я область имеет ширину і 8 . Таким образом получаем две одинаковые пирамиды (одна из них перевернутая). Каждый четный прямоугольник будем упаковывать в одну пирамиду, каждый нечетный — в другую.

Прямоугольники, из которых состоит пирамида будем называть контейнерами. Пронумеруем контейнеры внутри пирамиды числами от

1 до й так, что І -й имеет ширину І 8 . Прямоугольники внутри контейнеров будут упаковываться просто друг над другом: первый упаковываемый прямоугольник кладется на дно контейнера, следующий

— поверх первого и так далее.

Пусть некоторое количество прямоугольников упаковано в пирамиду и следующим для упаковки в данную пирамиду приходит прямоугольник ширины М>.

• Найдем такое /', что (/—1)8 <1У <і8 . Будем говорить, что этот прямоугольник назначен в І -й контейнер (тем не менее он не обязательно будет упакован именно в І -й контейнер).

• Далее ищем минимальное такое ], что І< ] <СІ ив ] -ом контейнере достаточно места, чтобы поместить туда данный прямоу гольник.

• Если такое j существует — помещаем данный прямоугольник в j -й контейнер.

• Если нет — просто кладем прямоугольник сверху текущей упаковки. Такие прямоугольники, которым не нашлось места ни в одном из контейнеров, в которые они помещаются по ширине будем называть выпавшими.

Анализ алгоритма

Корректность и онлайновость алгоритма очевидны. Оценим математическое ожидание незаполненной площади полосы.

Теорема2. Математическое ожидание незаполненной площади полосы упаковки, полученной алгоритмом из [8] есть ()(N1 2 (log N)3 2 ) .

План доказательства теоремы. Обозначим за S суммарную площадь N прямоугольников. Ясно, что ES = N/4 . Высота выделенной части полосы есть

(d + \)U = N/4\ -^-1 = N/4 + —= N/4 + 0(Nm). { d J 4[_mj *Jn

Будем рассматривать только одну из двух пирамид и соответственно

только \_N/2j прямоугольников упакованных в эту пирамиду.

Пронумеруем эти \_N/2j прямоугольников числами от 1 до lN/2] в соответствии с порядком поступления прямоугольников на вход алгоритму.

Обозначим за М{/2а, /22} математическое ожидание числа выпавших (смотри определение в описании алгоритма) прямоугольников при упаковке прямоугольников с номерами из диапазона \пх, п2 ] в данную пирамиду.

Таким образом, для доказательства теоремы требуется доказать, что

m{l,|JV72J}= 0(iV1/2(logiV)3/2).

Определим 2 целых числа к0 и к1:

К = In/2 J - In314 ViogivJ, кг = In/2 J - In112 1 m{l, Uv/2_|}= M{l ,k0}+ M{&0 +1 ,кг}+ +1, Uv/2_|}

Далее будут доказаны несколько лемм, из которых следует утверждение теоремы.

Лемма 1.

+1,|_М2_|}= 0(Л^1/2).

Очевидно, так как кх = \_NI2 J — \_Ы112 J и следовательно всего прямоугольников в этом диапазоне 0{Ы112) .

Для любого прямоугольника вероятность быть назначенным (смотри определение в описании алгоритма) в каждый конкретный контейнер есть \Ш, так как всего (I контейнеров. Пусть в пирамиду было упаковано к прямоугольников. Зафиксируем любой контейнер пирамиды. Через Хг, 1 < / < к обозначим случайную величину, равную высоте / -го прямоугольника в случае, если / -й прямоугольник назначается в данный контейнер, и 0 иначе. Можно записать Xj = ^j}]j , где — случайная величина, равная 1 с вероятностью р и 0 и вероятностью 1 — р, а — равномерно распределенная на отрезке

(ОД] случайная величина. Введем X — Хх + Х2 + ... + Хк случайную величину, равную суммарной высоте прямоугольников, назначенных в данный контейнер, где к — количество упакованных прямоугольников. Далее нам потребуется следующий вариант неравенства больших уклонений.

Лемма 2.

Пусть случайная величина X = X] + X2 + ... + Xк, где X/ = £.//.,

принимает значение 1 с вероятностью р и 0 с вероятностью 1 — р,

— равномерно распределенная на отрезке (0,1 ] случайная величина,

причем все случайные величины .,Т]г.,/ = 1 независимы в

совокупности. Тогда для любого ОС из интервала (0,1) выполняется неравенство

, -1а2ЕХ Р{Х>(\ + а)ЕХ}<е 9

Лемма 3.

М{1,£0}->0, оо

Доказательство. Оценим вероятность переполнения любого контейнера с помощью леммы 2. Для к = к0 = \_Ы!2\ — 1л^3/4 J

1(0 і Е(Х)=- -ї- =-2 {сі ) 2

( \ 1ы/2]-1ыму1\о&ы]

— + 0

4

;л/ІУ-2Л^1/4^/ІовЇУ+0(1).

Возьмем а , удовлетворяющее равенству и -1 = (1 + а)ЕХ . 1/-1-ЕХ 2Л?1/4*/к^7У

« =-----------= -г=----- , +0

ЕХ у/ії -2МшфоёМ Следовательно, по лемме 2

(27У1/4-у/1оё7У +Р(1))2 ^

Г

Р{Х>£/-і}<елр

-

< ехр

-(5/9)-

47У 1оё7У

/V1'2-2МУі^\о%М +0

/V1'2 -2М1'4 +0

Для достаточно больших N

Р{Х>и-1)<-^п

Обозначим событие, соответствующее переполнению хотя бы одного любого контейнера за А, через Д — событие переполнения / -го контейнера,

л = Ц4

2=1

1

<--------

2 Лг1.1

№ N

Следовательно

М{іД0}^0, 00.

Лемма 4.

Пусть алгоритмом бьшо упаковано LiV/2J — |_Л^1/2+^ прямоугольников в одну пирамиду и 0 < (3 < 1/4 . Зафиксируем любое у такое, что

1/2-2/?+ 1п(51пЛГ)<г <1/2.

ІпіУ

Обозначим через С — событие, заключающееся в том, что хотя бы

один из нижних контейнеров пирамиды заполнен не более чем

на II — 1. Тогда для достаточно больших N

462

Доказательство. Рассмотрим любые Г1 контейнеров пирамиды. Для к = \_Ы12\-\_Ыт+р \ рассмотрим

Х = Х1+Х2 + ... + Х,.

Где Х{ — высота / -го прямоугольника в случае, если он назначен в один из Г1 рассматриваемых контейнеров пирамиды и 0 иначе.

Ег_1 (Руу2]-Ру1/2+/?])Руг1

2 а

ЕХ <

2(М2-7У1/2+/?+1)у?'

Ыт-\

Докажем сначала для произвольного множества из Г№ ~\ контейнеров пирамиды, что

Р{*>(Е/-1)ГЛГ1}<-^.

Найдем а , которое удовлетворяет равенству (Ц - 1)Га^1 = (1 + а)ЕХ.

12\-1ы1П*11 \

_{и- 1)Г^1-ЕХ _ 11 ~1 ы _ N !2-2с1-1ы 12\ + 1ы1П+11 \

а ЕХ 12\-1ыш*11 \ |_Л?/2_|-|_Л?1/2+Ч

2 а

дг1'2^ _1л?1/2 +1

а < -

N

—-л^2+р -1

2

Оценим вероятность отклонения случайной величины X от ЕХ на а ЕХ с помощью леммы 2.

Р [х > (и - 1} = Р {х > (1 + а)ЕХ}

< ехр

N

-^--Лг1,2+Д -1 ]

Для достаточно больших N

( л

Р{Х>(1+а)ЕХ}<ехр --'-^7

По условию

у> 1/2-2/? +

1п

Следовательно для достаточно больших N

/ ^ 1п(МШУ) \ ^

р{х > (и — 1)ГЛг?'^ < ехр\ lnJV -~-

Оценим теперь вероятность того, что хотя бы в одну последовательность Гл^1 подряд идущих контейнеров будет назначено множество прямоугольников с суммарной высотой превосходящей (£/-1)Гл^~| (обозначим это событие за В ). Последовательность подряд идущих контейнеров с номерами с /-го по (/ + Г-А^г1 — 1) -й назовем /-ой

группой контейнеров (всего имеется с1— \ Ыг~\ + \ групп). За обозначим событие назначения прямоугольников с суммарной высотой, превосходящей (II -1)Гл^~| в контейнеры / -ой группы,

а-\ыг 1+1

в= и вг

2=1

-Глг^1+1

онл" |-м , .1

Р(5)< 2 Р(г,)<(</-Г^>1 + 1Ь

< •

1

г=! \ЛГ N

Покажем теперь, что если событие В не произошло, то в процессе упаковки прямоугольников в пирамиду по предложенному алгоритму

хотя бы в одном из нижних Г1 контейнеров достаточно места для

упаковки прямоугольника высоты 1 (одновременно нижние Г~\ контейнеров не могут быть заполнены на II — 1).

Пусть это не так и каждый из ГЫг 1 нижних контейнеров заполнен более, чем на и — 1. Вспомним, что 7 -й контейнер имеет ширину 7 а .

Найдем минимальный номер контейнера І такой, что І < СІ — ГШ7 ~\ и все контейнеры с І -го по <1 -й заполнены более, чем на £/ —1. Тогда утверждается, что в І -ую группу контейнеров (с номерами от І до

і + Г И71 — 1) были назначены прямоугольники с суммарной высотой превосходящей (II -1)Гл^~|. Действительно, в І -ую группу контейнеров по определению индекса І упаковано множество прямоугольников с суммарной высотой превосходящей (II — 1)Г~|, а так как либо І = 1, либо в (/ — 1) -й контейнер можно упаковать прямоугольник высоты 1,

то все контейнеры упакованные в І -ую группу были в нее и назначены. Получено противоречие.

Лемма 5.

М{£0 +1,^} = О^2(1оёЛ03' Доказательство. Разделим отрезок [ОД/4] на

lnN

6\п

одинаковых частей. Введем обозначение Мг

М = МI 1ы / 2І - їм" _|, 1м/ 2]- ] !>.

М {к0 +1,кг} = £м, = ]^М ||_ЛГ / 2] - ІЛ^4"1 ],!_# / 2] - _11

Оценим М . для 2 < / < п . Применим лемму 4 для параметров

Ап _ 1 г-1

7 2 Зп '

Очевидно, что

1 1п(51пЛ0

у >--2в+—±---------

2 1пЛГ

и алгоритмом было упаковано |_—_|-|_Л?1/2*' ] прямоугольников (условия

2

леммы 4 выполняются). Следовательно нижние Гл^І контейнеров

пирамиды к моменту упаковки |_—і - І7У1/2+д ] прямоугольников не могут

быть все заняты более чем на С/ — 1 и следовательно прямоугольник может выпасть только если будет назначен в один из нижних Гл^~1 контейнеров пирамиды. Всего в пирамиде <1 контейнеров, то есть вероятность того, что каждый прямоугольник из рассматриваемого диапазона может выпасть не превосходит

1>'1

Всего прямоугольников в диапазоне

ґ 11 11 !2\- 1к~2*~" ],ЦУ / 2] - ]

не более Ы2 4п . Следовательно

( 11 11 М = М Цу / 2] - _|, Цу / 2 _| - і [ =

= о

( І.ІІ ^г\п .д,2 з.

1 -1 + 4

= о\

Для/>5 М_ =0(Л^Гі2“).

£м, =о\пЫ

1 1

!2 12"~ I = О

1 л

1с^ ІУ-

Ы2

-0(М2 \ogNy

1 1п 51п N

72 1п N

Іс^іс^ N

V

Кроме того

XX =0(3-М2) = 0^Г~^ = 0^2 ыя | = 0\ М2 к^іУ |.

Для / = 1 количество прямоугольников в отрезке

Ґ I — 1

І.ІУ / 2 _| - |>+“], |_ЛГ / 2_| - |_ЛГ2 ]

есть

1 1 0\

0\ ЛГ2(1оеЛ03'

Итого

М{£0 + 1Д} = Xм, = 0^2(logA^)3/2 Лемма 5 доказана а вместе с ней и теорема.

Список литературы

[1] Baker В. S., Coffman Е. J., Rivest R. L. Orthogonal packings in two dimensions. SIAM J. Computing. 1980. V. 9. 4. P. 846-855.

[2] Baker B. S., Schwartz J. S. Shelf algorithms for two dimensional packing problems. SIAM J. Computing. 1983. V. 6. 2. P. 508-525.

[3] Shor P. W. The average-case analysis of some on-line algorithms for bin packing. Combinatorica. 1986. V. 6. 2. P. 179-200.

[4] Coffman E. G., Jr, Shor P. W. Packing in two dimensions: Asymptotic average-case analysis of algorithms. Algorithmica. 1993. V. 9. 3. P. 253-277.

[5] Кузюрин H. H., Поспелов А. И. Вероятностный анализ нового класса алгоритмов упаковки прямоугольников в полосу. ЖВМиМФ. 2011. Т. 51, N 10, с. 1931-1936.

[6] Кузюрин Н. Н., Поспелов А. И. Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу. Дискретная математика. 2006. Т. 18. 1. С. 76-90.

[7] Csirik J., Woegenger G.J. Shelf algorithm for on-line strip packing, Inf. Process. Letters, 1997, v. 63, N 4, P. 171-175.

[8] Трутников M.A., Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу, Труды ИСП РАН, 2012 г., т. 22, с. 456-462.