Eötvös Loránd Tudományegyetem Természettudományi Kar
Lomoschitz Lilla Anna Közelít® algoritmusok a 2 dimenziós online ládapakolási feladatra forgatással BSc Szakdolgozat
Témavezet®:
Király Tamás
Operációkutatási Tanszék
Budapest, 2013
Köszönetnyilvánítás
Szeretném megköszönni témavezet®mnek, Király Tamásnak a téma ötletét, és a szakirodalom megkeresését, valamint azt, hogy sok és rendszeres konzultációs alkalmat biztosított számomra. Szakmai és formai észrevételeivel sok segítséget nyújtott. Külön köszönöm a dolgozat szerkesztéséhez alkalmazott programok használatában nyújtott segítséget. Köszönettel tartozom még családomnak és barátaimnak, hogy felhívták gyelmemet a dolgozat korábbi verzióiban lév® formai hibákra, és általában a támogatásukért.
2
Tartalomjegyzék
1. Bevezetés
4
1.1.
A problémakör ismertetése . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2.
Tartalmi áttekintés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3.
Egyéb eredmények, alkalmazások
6
. . . . . . . . . . . . . . . . . . . . . . .
2. Négyzet alakú ládák 2.1.
2.2.
8
Egy algoritmus nem korlátos ládaszám esetén
. . . . . . . . . . . . . . . .
8
2.1.1.
A tárgyak csoportosítása . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1.2.
Sávok
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.1.3.
A tárgyak pakolása . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.1.4.
Fels® korlát
14
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Alsó korlát a feladatra
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Algoritmus téglalap alakú ládák esetén
15
20
3.1.
Csoportosítás
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.2.
Tárgyak elhelyezése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.3.
Általános alsó korlát a feladatra . . . . . . . . . . . . . . . . . . . . . . . .
28
3.4.
Fels® korlát az algoritmusra
. . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.5.
Javítási lehet®ségek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
4. Irodalomjegyzék
34
3
1. fejezet
Bevezetés
1.1.
A problémakör ismertetése
A ládapakolási feladat egy NP-nehéz kombinatorikus optimalizálási feladat. Számos területen alkalmazható, különböz® speciális esetei gyakran fordulnak el® gyakorlati problémák megoldásakor. A legegyszer¶bb alaptípusa az egydimenziós ládapakolási feladat. Ebben az esetben van
n darab kis szakaszunk, melyek hosszait aj -vel jelölve teljesül, hogy 0 < aj ≤ 1. A cél
az, hogy ezeket a szakaszokat minél kevesebb
1
egység hosszú nagy szakaszon helyezzük
el, úgy hogy a kis szakaszok ne fedjék egymást, és ne lógjanak le az egységhosszú nagy szakaszokról. A klasszikus két dimenziós ládapakolási feladat esetén téglalap alakú tárgyakat kell elhelyezni minél kevesebb
1
egység oldalú ládában. (Mostantól a tárgy és a kis téglalap
szavakat, valamint a láda és a nagy téglalap szavakat szinonímaként használom.) A kis téglalapok magassága és szélessége sem nagyobb, mint 1 egység. A tárgyakat úgy kell elhelyezni, hogy azok oldalai a láda falaival párhuzamosan helyezkedjenek el, a ládából ne lógjanak ki és egymást ne fedjék. Két dimenzióban már felmerül a kérdés, hogy lehessene forgatni a téglalapokat, vagy az eredeti helyzetben kelljen-e ®ket elhelyezni. Ha nem lehet ®ket forgatni, akkor könnyen látható, hogy a téglalap alakú ládába pakolás feladata is modellezhet® a négyzetbe pakolással. Amennyiben a forgatás megengedett, akkor a téglalap alakú ládába pakolás már nem vezethet® vissza ilyen egyszer¶en a négyzet alakú ládába pakolásra.
4
Fontos szerepe van annak, hogy el®zetesen ismerjük-e az összes elpakolandó tárgy méretét, ez alapján megkülönböztethetünk online és o ine feladatokat. O ine feladat esetén az összes tárgy paramétereit ismerjük, miel®tt elkezdenénk a pakolást. Online esetben csak a pakolás során tudjuk meg, hogy milyen tárgyakat kell elpakolnunk; azaz kezdetben egy láda paramétereit ismerjük, és mindig csak akkor ismerünk meg egy új tárgyat, ha az ismertekb®l egyet elpakolunk. Olyan feladat is elképzelhet®, hogy egyszerre több, de korlátos sok olyan tárgy lehet, aminek ismerjük a méreteit, de még nem pakoltuk el. Online esetben az alapján is lehet osztályozni a feladatokat, hogy mennyi ládát használ egyszerre. Ha nem használunk ilyen megkötést, akkor a feladat megoldására kitalált algoritmus futási ideje nagyon megn®het. Ugyanis, ahányszor új ládát nyitunk meg, azaz olyanba pakolunk, amibe addig még nem, akkor eggyel növeljük a megnyitott ládák számát. Ha az összes nyitott ládát megvizsgálja az algoritmus, miel®tt egy tárgyat elhelyezne, akkor egy-egy tárgy elhelyezése
O(n)
nagyságrend¶ id®be is telhet, ahol
n
az összes el-
pakolni való tárgy számát jelöli. Ezt az id®t úgy lehet csökkenteni, hogy maximalizáljuk azoknak a ládáknak a számát, amit az algoritmus megvizsgál az elemek elhelyezésekor. Ehhez de niáljuk a lezárt és aktív ládákat. Azokat a ládák nevezzük aktívnak, amiben már van legalább egy tárgy, és az algoritmus még pakolhat bele tárgyakat. Azt mondjuk, hogy egy algoritmus egy aktív ládát lezár, ha utána már soha többé nem nézi meg, hogy rakjon-e bele tárgyat; az ilyen ládát lezártnak nevezzük. Ha az aktív ládák maximális számára van megkötés, akkor a feladatot korlátos ládaszámúnak nevezzük. Az o ine ládapakolási feladat (azaz amikor a minimális ládaszám, és egy hozzá tartozó pakolás megadása a cél) NP-nehéz. Ezért a probléma megoldására kitalált polinomiális id®ben futó algoritmusok csak közelít® megoldásokat adnak. Ezeknek az algoritmusoknak a teljesítményét lehet úgy mérni, hogy megvizsgáljuk, hányszor annyi ládát használnak, mint amennyit egy optimális o ine pakolás használna. Mindezt nagyon sok tárgy esetén nézzük, és a legrosszabb esetekben, azaz olyan ládasorozatok esetén, ahol ez az arányszám maximális. A pontos de nícióhoz jelölje
L
az elpakolni való tárgyak sorozatát,
azt, hogy ehhez minimum mennyi láda kell, és az
A
A(L) azt, hogy az L sorozat elpakolásához
algoritmus mennyi ládát használ. Legyen továbbá
n RA
:= max
A(L) |OP T (L) = n OP T (L)
5
OP T (L)
Ekkor az
A
algoritmus aszimptotikus hatékonysági arányát (angolul asymptotic worst
case ratio) a következ®képpen de niáljuk:
n R∞ := lim sup RA n→∞
Az egyszer¶ség kedvéért ezt a továbbiakban hatékonysági aránynak nevezzük.
1.2.
Tartalmi áttekintés
A szakdolgozatnak a bevezet®n kívül két f® része van. A második fejezet a négyzet alakú ládába történ® online pakolással foglalkozik. Itt szerepel egy nem korlátos ládaszámú algoritmus, valamint egy fels® korlát annak a hatékonyságára. Az algoritmus S. Fujita, és T. Hada által írt [1] cikkb®l származik, a fels® korlátot pedig az ott lév® számolás mintájára becsültem felülr®l, a becslés
R∞ < 2.723.
L. Epstein [2] cikke szerint
a S. Fujita és T. Hada által adott bizonyítás hibás. Ezért a szakdolgozatban az eredeti fels® korlátnál nagyobb szám szerepel. Ebben a fejezetben szerepel még egy alsó korlát a hatékonysági arányra, amennyiben az algoritmus korlátos sok nyitott ládát használ. Ennek az értéke megközelít®leg
R∞ > 2.535,
az erre vonatkozó bizonyítás L. Epstein [2]
cikkéb®l származik. Annak az oka, hogy az alsó becslés korlátos ládaszámú algoritmusra vonatkozik, míg a fels® becslés egy nem korlátos ládaszámúra, az, hogy ez az algoritmus és ezek a bizonyítások szolgálnak a harmadik fejezet alapjául. Ebben saját eredmények vannak téglalap alakú ládába történ® online pakolásról. Szerepel egy korlátos ládaszámú algoritmus, ami maximum ritmusra:
10
ládát használ egyszerre, valamint két fels® korlát az algo-
2.75 és 2.55, ami a láda oldalainak arányától függ. Itt található még három alsó
korlát a feladatra, szintén a láda oldalainak aránya függvényében:
1.3.
2.05, 1.77, 1.47.
Egyéb eredmények, alkalmazások
Bizonyos ütemezési feladatok modellezésére a 2 dimenziós online pakolás forgatást nem megenged® változata alkalmas. A feladat korlátos ládaszámú változatára L. Epstein és R. van Stee adott [4]-ben egy olyan algoritmust, aminek a hatékonysági aránya a lehet® legkisebb, körülbelül 2.86. A nem korlátos ládaszámú feladat hatékonysági arányára X. Han, F.Y.L. Chin, H.-F. Ting, G. Zhang és Y. Zhang [5]-ben adtak egy fels® becslést, ez megközelít®leg 2.66.
6
A forgatást is megenged® változat nagyméret¶ papír-, furnér-, vagy fémalapokból különböz® kisebb méret¶ lapok kivágását modellezheti, ha a kivágások elvégzésénél az a cél, hogy minél kevesebb felhasználatlan anyag maradjon ki, illetve, hogy minél kevesebb nagy lapot használjanak fel. Itt a maximálisan nyitva lev® ládák száma azt jelenti, hogy mennyi nagy lapot kell kezelni egyszerre, azaz mennyit kell a kivágás helyén tárolni, és mennyi közül kell kiválasztani azt, amib®l a megrendelt kisebb lapot ki fogjuk vágni. Erre a problémára nem korlátos ládaszámmal az L. Epstein és R. van Stee által [6]-ban adott alsó korlát megközelít®leg 1.64. L. Epstein fels® korlátot is adott [2]-ben, ami
≈ 2.45.
Szintén ebben a cikkben szerepel korlátos ládaszámra egy-egy alsó és fels® korlát. Az alsó korlát, a már említett 2.535, ennek bizonyítása a szakdolgozatban is szerepel. A fels® korlát
≈ 2.547. Ennek az algoritmusnak a hatékonysági aránya azért annyira jó (azaz alacsony), mert ugyan korlátos ládaszámú, de
104
nagyságrend¶ nyitott ládát is használhat. Ezért
alkalmazásokra nem is érdemes felhasználni, mert ha nincs
105
nagyságrend¶ elpakolni
való tárgy, akkor el®fordulhat, hogy alig lesz lezárt ládánk, viszont sok megnyitott láda lesz, melyeknek csak kis részét foglalja el tárgy, azaz a szükségesnél jóval több ládát használ fel. Téglalap alakú ládába pakolásról írt M. M. Mehdi és S. P. Willems [3]-ban. k egy konkrét problémával foglalkoztak: rögzített méret¶ nagy acéllapokból kellett kivágni kisebbeket, úgy hogy a kisebbek méretei nem ismertek el®re, de az eloszlásuk igen. Az algoritmusuk egyszerre maximum három nagy lapot használ. Az ötletük az, hogy mindig úgy vágják ki az aktuális téglalapot, hogy annak a sarka a még felhasználható terület egy sarkához érintkezzen, és hogy a 3 nagy lapból megmaradó részbe beleírható 3 téglalap összmérete a lehet® legnagyobb legyen. Hatékonysági arányt nem számoltak, a saját maguk által adott példa-téglalapsorozatok állításuk szerint átlagosan a nagy lapok 80% -át felhasználták.
7
2. fejezet
Négyzet alakú ládák
2.1.
Egy algoritmus nem korlátos ládaszám esetén
Ebben a részben egy S. Fujita és T. Hada által [1]-ben leírt algoritmust mutatok be. El®ször a különböz® tárgyak csoportosítását írom le, majd a ládák felosztását különböz® sávokra, és a tárgyak elhelyezését a nekik megfelel® sávokban. Az alfejezet végén egy fels® korlát található az algoritmus hatékonysági arányára.
2.1.1.
A tárgyak csoportosítása
Legyen meg, ahol
T
az összes téglalap alakú elem halmaza, amelyeket egy-egy
x
és
0 < x ≤ y ≤ 1. szerint. Legyen
y
(x, y) pár határoz
a téglalapok szélességét, illetve magasságát jelentik; és teljesül, hogy
El®ször négy részhalmazra osztjuk a
T0 = {(x, y) | 2/3 < x ≤ 1}
{(x, y) | 1/3 < x ≤ 1/2},
és
,
T -beli
elemeket az
x
koordinátáik
T1 = {(x, y) | 1/2 < x ≤ 2/3}, T2 =
T3 = {(x, y) | 0 < x ≤ 1/3}.
A
T2
és
T3
részhalmazokat a
bennük lev® tárgyak y koordinátái szerint további részhalmazokra osztjuk.
T3 -at
így négy részhalmazra osztjuk. Legyen
T30 = {(x, y) ∈ T3 | 2/3 < y ≤ 1},
T31 = {(x, y) ∈ T3 | 1/2 < y ≤ 2/3}, T32 = {(x, y) ∈ T3 | 1/3 < y ≤ 1/2}, és T33 = {(x, y) ∈ T3 | 0 < y ≤ 1/3}. A
ai :=
T2 -beli 1 3
+
észre, hogy
elemek csoportosításához de niáljuk az
1 3(2i +1)
∀i ∈ N
esetén. Például:
1/3 < ai ≤ 1/2
Φ : R+ → Z
valós számokból álló sorozatot:
a1 = 4/9, a2 = 2/5, a3 = 10/27.
∀i ∈ N esetén. 2 ) . Φ(t) := log2 ( 9t−1
teljesül
függvény, melyre
{ai }
8
Legyen
>0
Vegyük
egy kicsi konstans, és
T 30 2/3
T 20
T 31
1/2
T 21 T 22
T 32
1/3
hosszú-sávba
T 33
y
T0
T1
közepes-sávba rövid-sávba 1/3
1/2
2/3
x 2.1. ábra. Csoportosítás
T2 -t
ezek segítségével a következ® három részhalmazra osztjuk:
Φ()−1
T20
:=
[
{(x, y) | aj+1 < x ≤ aj , 1 − aj < y ≤ 1}
j=0
∪ {(x, y) | 1/3 < x ≤ aΦ() , 1 − aΦ() < y ≤ 1} Φ()−1
T21
:=
[
{(x, y) | aj+1 < x ≤ aj , 1/2 < y ≤ 1 − aj }
j=0
∪ {(x, y) | 1/3 < x ≤ aΦ() , 1/2 < y ≤ 1 − aΦ() } T22 :={(x, y) | 1/3 < y ≤ 1/2} A csoportosítást a 2.1 ábra is szemlélteti. Egy-egy részhalmazba tartozó elemek méretére vonatkozik a következ® két állítás:
2.1.1. Állítás. Bizonyítás. 2/9 −
1 9(2i +1)
Legyen
Ha
i > log2 ( 92 − 1),
> 2/9 −
2.1.2. Állítás. elemek mérete
i > log2 ( 92 − 1),
A
1 9(2/9)
T0 -beli
akkor
ekkor
2i >
1/3 · (1 − ai ) > 2/9 − /2.
2 9
− 1.
Így
1/3 · (1 − ai ) = 2/9 − 3(3(21i +1)) =
= 2/9 − /2.
elemek mérete
> 4/9.
> 2/9 − (/2). 9
A
T1 -beli
elemek mérete
> 1/4.
A
T20 -beli
Bizonyítás.
Az els® két megállapítás triviális. A harmadik bizonyításához el®ször meg-
mutatjuk, hogy
(1 − ai ) · ai+1 = 2/9
a0 ) · a1 = 1/2 · 4/9 = 2/9. 1 ) 3(2i+1 +1) legalább
2.1.2.
=
2 9
+
2 9(2i+1 +1)
Ha
1 9(2i +1)
−
teljesül
i ≥ 1, −
min{2/9, 1/3 · (1 − aΦ() )},
∀i ∈ N
akkor
esetén. Ha
i = 0,
(1 − ai ) · ai+1 = ( 32 −
1 . Ezért 9(2i +1)(2i+1 +1)
T20
akkor
1 ) 3(2i +1)
(1 −
· ( 31 +
legkisebb elemének mérete
így 2.1.1 segítségével az állítás következik.
Sávok
A ládák sávokra bontásához de niálunk néhány halmazt:
X :=
1 | i ∈ {3, 4, 5}, j ∈ N i · 2j
Xh := X ∪ {1/2} Xk := X ∪ {a1 , a2 , . . . , aΦ() }, A továbbiakban
∀x ∈ (0, 1]
ahol
ai =
1 1 + ∀i ∈ N i 3 3(2 + 1)
esetén legyen
x e := min{a ∈ Xh | a ≥ x} x b := min{a ∈ Xk | a ≥ x}. Vegyük észre, hogy
x < 1/3
esetén
x/e x(= x/b x) > 3/4.
Az algoritmus a következ® háromféle sávot használja:
2.1.3. De níció.
Egy ládának egy részét hosszú-sávnak nevezzük, ha a szélessége
ség, és a magassága egy vezzük, ha a szélessége
Xh -beli
1/2
szám. Egy ládának egy részhalmazát rövid-sávnak ne-
egység, és a magassága egy
Xh -beli
részhalmazát közepes-sávnak nevezzük, ha vagy a szélessége egy
1 egy-
X -beli szám; vagy az egyik oldala 1−ai , a másik pedig ai
2/3
szám. Egy ládának egy egység, és a magassága
hosszú, valamely
1 ≤ i ≤ Φ()
esetén.
2.1.4. Megjegyzés. 2.1.3.
A közepes-sávok rövidebb oldalának hossza mindig egy
Xk -beli szám.
A tárgyak pakolása
Ebben a részben található az algoritmus leírása; el®ször az, hogy milyen sávba rak egy bizonyos elemet az algoritmus, majd az, hogy a sávokat hogyan helyezi el, és hogy ehhez mikor kezd el egy új ládába pakolni, illetve mikor zár le egy ládát.
10
Ha
• (x, y) ∈ T0 ∪T1 , akkor az algoritmus egy új ládát nyit meg, abba belerakja az elemet, majd lezárja a ládát.
• (x, y) ∈ T20 ∪ T30
x e magas,
esetén aktiváljunk egy
üres hosszú-sávot, helyezzük el az
elemet a sávban, és zárjuk le a sávot. A sávot a kés®bb leírt
hosszú_sáv nyitása(x)
szubrutin szerint tudjuk megnyitni.
• (x, y) ∈ T21 ∪ T31
esetén aktiváljunk egy
x b magas, üres közepes-sávot, helyezzük el az
elemet a sávban, és zárjuk le a sávot. A sávot a kés®bb leírt
közepes_sáv_nyitása(x)
szubrutin szerint tudjuk megnyitni.
• (x, y) ∈ T22 ∪ T32
esetén aktiváljunk egy
x e
magas, üres rövid-sávot, helyezzük el az
elemet a sávban, és zárjuk le a sávot. A sávot a kés®bb leírt
rövid_sáv_nyitása(x))
szubrutin szerint tudjuk megnyitni.
• (x, y) ∈ T33
esetén rakjuk a tárgyat egy aktív
x e
magasságú hosszú-sávba, ha ezek
között van olyan, amiben elfér a tárgy. Ha nincs ilyen sáv, akkor zárjuk le az összes aktív
x e
magas hosszú-sávot; és aktiváljunk egy
x e
magas, üres hosszú-sávot, és he-
lyezzük el az elemet az új sávban. Ekkor az eddigiekt®l eltér®en még nem zárjuk le a sávot. Az 2.1 ábra azt is szemlélteti, hogy a különböz® típusú elemeket milyen sávokba pakolja az algoritmus.
2.1.5. Állítás.
Minden lezárt
van tárgy, ha a sáv
Bizonyítás.
1/2
S
terület¶ hosszú-sávnak legalább
magas; és legalább
2.1.1 szerint egy lezárt
S/2
(4/9−)S
terület¶ részén
terület¶ részén, ha a magassága
< 1/2.
1/2 magas hosszú-sáv legalább 2/9 − /2 területen ki
van töltve elemekkel, így a kitöltöttségi aránya egy csak ilyet tartalmazó ládának legalább
4/9 − .
Másrészt ugyanezen állítás szerint egy
több, mint
1/i
( ahol
i ≥ 3)
magas lezárt hosszú-sáv
2/3 · 1/(i + 1) terület¶ részén van tárgy, így ennek a kitöltöttségi aránya ≥ 1/2.
2.1.6. Állítás. tárgy, ha a sáv
Minden lezárt
1/2
S
terület¶ rövid-sávnak legalább
magas; és legalább
S/2
4/5 · S
terület¶ részén van
terület¶ részén, ha a magassága 11
< 1/2.
Bizonyítás.
Az el®z®höz hasonlóan következik.
2.1.7. Állítás.
Minden lezárt
magas rövid-sávnak (ahol
ai
1 ≤ i ≤ Φ())
több, mint
1/2·1/3 = 1/6 terület¶ részén van tárgy; ha pedig a lezárt sáv magassága < 1/i (valamilyen i ≥ 3 esetén), akkor egy olyan elem van benne, aminek a területe több, mint 1/(i+1)·1/2 = 1/(2(i + 1)).
Bizonyítás.
De nícióból következik.
A következ®kben leírom, hogy az algoritmus hogyan oszt fel sávokra egy ládát. Ezt a
hosszú_sáv_nyitása(x), közepes_sáv_nyitása(x), rövid_sáv_nyitása(x) szubrutinok is-
mertetésével tesszük. Az utasítások pontos leírásai a következ®k:
hosszú_sáv_nyitása(x) :
•
Ha nincs hogy
j0
2j x e magas
hosszú-sáv semmilyen
2 x e ∈ {1/2, 1/3, 1/5}.
hogy van
2j x e magas
1
2j 0 x e
Ha
i∈N
i0 = 0,
esetén. Jelöljük ezt a sávot akkor aktiváljuk a
Q
Q-val.
Legyen
i0
2 x baQ
sávot. Egyébként osszuk fel
2i−1 x e, 2i−2 x e, . . . , x e, x e magasságokkal,
és aktiváljuk az egyik
olyan,
darab
0
2j x e
hosszú-sáv.
Válasszuk ki az egyik legvékonyabb hosszú-sávot, aminek a magassága lyen
•
j ∈ N,
j0 ∈ N
esetén, akkor legyen
Nyissunk egy új ládát, és bontsuk fel
magas hosszú-sávra. Így van olyan
•
j∈N
2i x e,
valami-
sáv magassága.
Q-t i0 + 1
sávra rendre
x e sávot.
rövid_sáv_nyitása(x) :
•
Ha van üres
x e magas rövid-sáv, akkor ezt aktiváljuk. Egyébként vegyünk egy üres x e
magas hosszú-sávot, a
x e magas
hosszú_sáv_nyitása(x) -szel, bontsuk a hosszú-sávot két üres
rövid-sávra, és az egyiket aktiváljuk.
közepes_sáv_nyitása(x) :
•
Ha van üres
x b
magas fekv® közepes-sáv (vagy ilyen széles álló közepes-sáv), akkor
azt aktiváljuk.
•
Egyébként, ha
x b > 1/3, akkor nyissunk egy új ládát, és jelöljünk ki benne 4 egyforma
sávot (2 fekv®t és 2 állót) középpontosan szimmetrikusan. A fekv® sávok magassága legyen
x e,
szélességük
1−x e,
az álló sávoknál pedig pont fordítva.
12
2.2. ábra. Közepes-sávok elhelyezése
•
Ha
x e ≤ 1/3,
2j x b
magas üres közepes-sáv semmilyen
új ládát, jelöljünk ki benne
x ≤ 1/3
esetén
0
1
2j 0 x b
darab
j0
b 2 x
j ∈ N-re,
akkor nyissunk egy
magas fekv® sávot, és
0
0 1/3 · 2j x b
2j x b széles sávot, ahol j 0 ∈ N és 2j x b ∈ {1/2, 1/3, 1/5}. Így már van olyan
j ∈ N,
és
és
nincsen
darab
x > 1/3,
hogy van
2j x b magas
közepes-sáv.
Válasszuk ki az egyik legkeskenyebb olyan közepes-sávot, aminek a magassága 0
2i x b valamilyen i ∈ N esetén, és nevezzük el a sávot Q-nak. Legyen 2i x b a Q sáv magassága.
Ha
i0 = 0,
rendre
akkor
i0 −1
2
Q
i0 −2
x e, 2
legyen egy aktív sáv. Egyébként osszuk fel
x e, . . . , x e, x e magasságokkal,
Q-t i0 + 1
és aktiváljuk az egyik
sávvá
x e sávot.
A közepes-sávok elhelyezkedését egy-egy ládában a 2.2 ábra is illusztrálja.
2.1.8. Állítás.
Minden
1/3-nál
gyak összterülete legalább
Bizonyítás.
szélesebb közepes-sávokra bontott lezárt ládában lev® tár-
2/3.
2.1.7 állítás szerint egy ilyen sávban lév® tárgyak összterülete legalább
és a közepes-sávok kijelölési módszere alapján ládában lev® tárgyak összterülete legalább
2.1.9. Állítás.
Minden
tárgyak területe legalább
Bizonyítás.
ilyen sáv van egy lezárt ládában. Így a
2/3.
1/3-nál nem szélesebb közepes-sávokra bontott lezárt ládában lev® 1/2.
Ha a sávok magassága
darab több, mint
4
1/6,
1/(2(i + 1))
1/i,
ahol
i ≥ 3,
akkor mindegyikben pontosan egy
terület¶ tárgy van. Ez igaz a sávok f®sávokká egyesítésére
is, csak itt a terület több tárgyból is összejöhet. Itt a f®sáv azt az eredeti sávot jelenti, amit kés®bb felbontott az algoritmus, és amire
i ∈ {3, 4, 5}.
fér el, így a ládában lev® tárgyak összterülete több, mint
13
Minden ládában
i+1
f®sáv
(i + 1) · 1/(2(i + 1)) = 1/2.
2.1.4.
Fels® korlát
2.1.10. Tétel. Bizonyítás.
Minden
L
Legyen
elemek számát
n0 ,
a
1/2
esetén
∞ RA ≤ 2.723 + .
tárgyaknak egy
T1 -beliekét
elemek pakolására, és használ, amit
>0
pedig
n
n1 .
elem¶ sorozata. Jelölje a benne lév®
Az algoritmus
b0 (= n0 )
ládát használ a
b1 = (n1 ) ládát a T1 -beliek számára. Tegyük fel, hogy b2
magas hosszú-sávokra oszt az algoritmus; és
szélesebb közepes-sávok vannak. Legyen
S
az
L-ben
b3
olyat, amiben 1/3-nál
S4
pedig
b0 + b1 + b2 + b3
darab
ládában, azaz azoknak a tárgyaknak az összterülete, melyek magassága legfeljebb Ha
konstans, akkor az algoritmus legfeljebb
használ. Az optimális o ine pakolás legalább
T0 -beli
olyan ládát
lev® tárgyak összterülete,
azon tárgyak összterülete, melyek nincsenek benne a fent említett
T0 -beli
1/3.
b0 + b1 + b2 + b3 + 2S4 + O(1)
max{n0 + max{n1 , b2 /2}, S}
ládát
ládát használ.
Ezekb®l következik, hogy
∞ RA ≤
b0 + b1 + b2 + b3 + 2S4 . max{n0 + max{n1 , b2 /2}, S}
A 2.1.5, 2.1.6, 2.1.8 és 2.1.9 állításokból következik, hogy
2/3b3 − n1 /4. Ezt S4
S4 ≤ S − 4/9n0 − (4/9 − )b2 −
helyére behelyettesítve még mindig egy fels® becslést kapunk
∞ RA -ra:
n0 + n1 + b2 + b3 + 2(S − 4/9n0 − (4/9 − )b2 − 2/3b3 − n1 /4) max{n0 + max{n1 , b2 /2}, S} 2S + n0 /9 + n1 /2 + (1/9 + 0 )b2 − b3 /3 ≤ max{n0 + max{n1 , b2 /2}, S}
∞ RA ≤
1. eset Ha S > max{n1 , b2 /2}, akkor ∞ RA ≤ 2 + 1/S · (n0 /9 + n1 /2 + (1/9 + 0 )b2 ).
•
Ha még
n1 ≤ b2 /2,
akkor
∞ ≤ 2 + 1/S · (n0 /9 + (11/36 + 0 )b2 ) ≤ 2 + 1/S · (11/18n0 + (11/18 + 0 )b2 /2) RA
=2+ •
ha pedig
n0 + b2 /2 11/18 + 00 ≤ 2 + 11/18 + 00 , S
n1 > b2 /2,
akkor
∞ RA ≤ 2 + 1/S · (n0 /9 + (13/18 + 0 )n1 ) ≤ 2 + 1/S · (13/18n0 + (13/18 + 0 )n1 ) n0 + n1 =2+ 13/18 + 00 ≤ 2 + 13/18 + 00 S
14
2. eset Ha S ≤ max{n1 , b2 /2}, akkor ∞ RA ≤2+
•
Ha még
n1 ≤ b2 /2,
n0 /9 + n1 /2 + (1/9 + 0 )b2 . n0 + max{n1 , b2 /2}
akkor
n0 /9 + b2 /4 + (1/9 + 00 )b2 n0 /9 + (13/18 + 00 )b2 /2 =2+ n0 + b2 /2 n0 + b2 /2 00 (13/18 + )(n0 + b2 /2) = 2 + 13/18 + 00 , ≤2+ n0 + b2 /2
∞ RA ≤2+
•
ha pedig
n1 > b2 /2,
akkor
n0 /9 + n1 /2 + (2/9 + 00 )n1 (n0 /9 + (13/18 + 00 )n1 =2+ n0 + n1 n0 + n1 00 (13/18 + )(n0 + n1 ) ≤2+ = 2 + 13/18 + 00 . n0 + n1
∞ RA ≤2+
Mivel
∞ ≤ 2 + 13/18 + 00 < 2.723 + 00 RA
minden lehetséges esetben, így a tétel teljesül.
2.2.
Alsó korlát a feladatra
Az alsó korlát bizonyítása L. Epstein [2] cikkéb®l származik. El®ször egy téglalapsorozatot fogunk megadni. Ehhez 7 viszonylag nagy téglalapot fogunk de niálni, amelyek együtt elférnek egy ládában. Mind a 7 téglalapról tudnunk kell, hogy ha csak egyformákat rakunk egy ládába, abból maximum mennyi fér el. Ehhez szükségünk lesz három állításra.
2.2.1. Állítás. 2 ≤ k ∈ N,
Olyan téglalapokból, melyek oldala szigorúan nagyobb, mint
legfeljebb
Bizonyítás.
(k − 1)2
1/k ,
ahol
darab fér el egy ládában.
Tekintsük a láda és a benne lev® téglalapok vetületét a láda egyik falával
párhuzamos tengelyre. Így a láda egy 1 egység hosszú f®intervallum lesz, a tárgyak pedig ennek az intervallumnak lesznek
1/k -nál szigorúan hosszabb részintervallumai. Mivel bár-
mely vízszintes, vagy függ®leges vonal maximum f®intervallum minden pontjában legfeljebb
k−1
tárgyat metszhet a ládában, így a
k−1 téglalap vetülete lehet. Tekintsük a részin-
tervallumok által meghatározott intervallumgráfot. A legnagyobb klikk mérete legfeljebb
k −1. Mivel minden intervallumgráf perfekt, így ennek a pontjait (azaz az intervallumokat 15
illetve tárgyakat) így legfeljebb
k − 1 színnel tudjuk színezni. Mivel minden téglalap nagyobb, mint 1/k ,
k−1
fér el fedés nélkül az intervallumban, így
minden színb®l. Így összesen
gassága
intervallum lehet a f®intervallumban, azaz ennyi
Vegyünk egyforma téglalapokat, melyek szélessége
1/3 < x < 1/2,
intervallum lehet csak
téglalap lehet a ládában.
2.2.2. Állítás.
(k − 1)2
k−1
és amelyekre teljesül, hogy
x + y > 1.
1/2 < y < 2/3
Ezekb®l legfeljebb
és ma-
2
fér el
egy ládában.
Bizonyítás.
Vegyünk egy ládát, amiben ilyen tárgyak vannak. Egy, a ládát metsz® víz-
szintes, vagy függ®leges vonal legfeljebb 2 tárgyat metszhet. Az, hogy két tárgyat messen, csak úgy fordulhat el®, ha mindkét tárgy ugyanarra az oldalára van forgatva; ekkor a vonal egy
y
hosszú intervallumot metsz ki mindkét téglalapból. Bármely egyéb esetben a
téglalapok nem férnének el egymás mellett, vagy egymás felett. Tekintsük a téglalapoknak és a ládának a láda egyik falára való vetületét. A tárgyaknak kétféle vetülete lehet: rövid (x méret¶) intervallum, vagy hosszú (y méret¶) intervallum. Minden pontot legfeljebb egy rövid intervallum, vagy legfeljebb két hosszú intervallum tartalmazhat. Mivel egy hosszú intervallum mellett nem fér el egy rövid, és egymást pedig nem fedhetik, így vagy csak rövid, vagy csak hosszú intervallumok lehetnek egy vetületen. Ha hosszú intervallumok vannak, akkor azoknak mindenképpen fedniük kell egymást, legalábbis a f®intervallum közepén, így ebben az esetben maximum 2 tárgy lehet a ládában. Ha az összes intervallum rövid, akkor azok nem fedhetik egymást, így szintén legfeljebb 2 lehet bel®lük egy ládában. Így összesen maximum 2 ilyen téglalap fér el egy ládában.
2.2.3. Állítás. gassága
Vegyünk egyforma téglalapokat, melyek szélessége
1/7 < x < 1/6,
és amelyekre teljesül, hogy
3x + y > 1.
1/2 < y < 4/7
Ezekb®l legfeljebb
és ma-
8
fér el
egy ládában.
Bizonyítás.
Elforgatás nélkül legfeljebb 6 téglalap rakható egy ládába, mivel 7 ilyen tég-
lalap már nem fér el egymás felett. Ha még megmutatjuk, hogy elforgatott téglalapokból a
6
eredeti irányban lev® mellett legfeljebb kett® fér el, és azt; hogy ha
forgatott téglalap van a ládában, amellett maximum
4
3
egyik irányba
másik irányba forgatott téglalap
fér el, akkor készen vagyunk.
l≥3
téglalap
van benne. Vegyünk egy függ®leges vonalat, ami a láda közepén is áthalad. Mivel
y > 1/2,
Vegyünk egy ládát például csak fekv® téglalapokkal. Tegyük fel, hogy
így ez a vonal mind az
l
tárgyat metszeni fogja. A vonal álló téglalapot nem metszhet,
16
ugyanis az már nem férne el a 3 fekv® téglalaptól, mivel függ®leges vonalat, és toljuk el ®ket jobbra illetve balra
l
darab téglalap
y
y + 3x > 1.
Kett®zzük meg a
y − 1/2 távolságra. Mivel mind az
széles, így mindkét vonal metszi az összes téglalapot a mozgatás során
végig, és a mozgatás végén is. Ezért az
l
téglalapon felül további téglalapok csak a két
vonal által meghatározott sávon kívül lehetnek. A vonalak, és a hozzájuk közelebb lév®
1−y
mindkét esetben. Álló téglalapok csak egymás
mellett lehetnek, mert a hosszabb oldaluk
> 1/2, így egymás fölött nem férne el 2 bel®lük.
függ®leges ládafal közötti távolság
Mivel a széls® sávok szélessége
1 − y < 3x,
így ezekbe a sávokba csak 2-2 téglalapot lehet
pakolni. Így a 3 fekv® téglalap mellé maximum 4 álló fér el. Ugyanez igaz fordítva is.
2.2.4. Tétel.
A hatékonysági arány korlátos ládaszám, forgatható elemek és négyzet alakú
ládák esetén a két dimenziós ládapakolási feladatra legalább
Bizonyítás.
Legyen
δ > 0
60377/23814 ≈ 2.535356.
egy kicsi konstans. A bizonyításhoz a következ® téglalap-
típusokat használjuk:
• A: 1/2 + δ
oldalú négyzetek. Ezekb®l 2.2.1 szerint csak egy darab fér el egy ládában.
• B : 1/3 + δ
oldalú négyzetek. Ezekb®l 2.2.1 szerint legfeljebb 4 darab fér el egy
ládában.
• C1 : 2/3 − δ
széles, és
1/3 + 2δ
magas téglalapok. 2.2.2 alapján ilyenekb®l legfeljebb
2 darab fér el egy ládában.
• C2 : 2/3 − 2δ
széles, és
1/3 + 3δ
magas téglalapok. 2.2.2 alapján ilyenekb®l legfeljebb
2 darab fér el egy ládában.
• D1 : 11/21 − 4δ
széles, és
10/63 + 2δ
magas téglalapok. 2.2.3 alapján ilyenekb®l
legfeljebb 8 darab fér el egy ládában.
• D2 : 32/63 − 4δ
széles, és
31/189 + 2δ
magas téglalapok. 2.2.3 alapján ilyenekb®l
legfeljebb 8 darab fér el egy ládában.
• E : 1/7 + δ
oldalú négyzetek. Ezekb®l 2.2.1 szerint legfeljebb 36 darab fér el egy
ládában. Ezenkívül még apró téglalapokat is fogunk használni, melyek oldalai nagyon kicsik. A bet¶kkel jelölt nagyobb téglalapok úgy vannak de niálva, hogy egy optimális o ine algoritmus által pakolt ládában pontosan egy darab fér el mindegyikb®l. A pakolás során
17
B
C1 D1
E C2
A
D2
2.3. ábra. Optimális o ine elrendezés
maradnak kitöltetlen részek a ládában, az apró téglalapokat úgy kell megadni, hogy ezt a maradék területet az így megadott ládában pont kitöltsék. Mivel az o ine algoritmus által pakolt összes láda területe 1 egység, így az apró tárgyak területe egy ládában (bet¶kkel jelölt tárgyak területe) gyak összterülete
= 361/47628 + Θ(δ)
(361/47628 + Θ(δ))·(az
Így az összes ládában az apró tár-
o ine ládák száma). A tárgyak elrendezését az
optimális o ine algoritmus szerint a 2.3 ábra szemlélteti. A négyzet tetejéb®l egy magas sávot levágunk, ebbe kerül egy oldalából egy egy
2/3 − 2δ
1/3 + 3δ
magas és
bal fels® sarkába egy
B
és egy
C1
D1 ,
a jobb fels®be egy
n
C2
típusú tárgy tölti ki. Így
széles téglalap marad. Ennek a bal alsó sarkába egy
helyezünk el. Így a kimaradó terület Egy téglalap-sorozat
E,
a jobb alsóba pedig egy
n
darab
B
D2
A,
a
típusú elemet
V = 361/47628 − Θ(δ) ≈ 0.007579575 − Θ(δ).
téglalapot tartalmaz minden típusból, úgy, hogy az egyfélék
egymás után jönnek, és utána az apró téglalapokat. Azaz el®ször jön majd
1/3 + 2δ
típusú tárgy. A megmaradó rész jobb
széles sávot vágunk le, ezt pont egy
2/3 − 3δ
1−
n
darab
A
típusú,
típusú, és így tovább, azaz az egyformák mindig együtt jönnek, a külön-
böz®k nem keverednek. Mivel az online algoritmus korlátos ládaszámú, így csak konstans sok ládát tarthat nyitva egyszerre, így ha
n → ∞,
akkor csak konstans sok ládába kerülhet többféle elem,
így konstans sok láda kivételével csak egyféle tárgy van az egyes ládákban. Az
A
típusú elem
külön-külön
n − O(1)
n/2 − O(1)
n/36 + O(1)-et.
ládát foglal el, a ládát, a
D1
és
B
D2
típusúak
n/4 + O(1)-et,
külön-külön
Az apró téglalapok pakolása legalább
18
n/8 + O(1), V n − O(1)
a
C1
és
C2
n
darab
típusúak
az E-típusúak pedig ládát használ fel. Ez
összesen
n
(91/36 + V )n − O(1)
ládát jelent. Mivel az o ine algoritmus ezeket az elemeket
ládába pakolja, így a hatékonysági arány
91/36 + V ≈ 2.53536.
19
3. fejezet
Algoritmus téglalap alakú ládák esetén
A következ® algoritmus során a feladat abban változik, hogy az elpakolni való kis téglalapokat (tárgyakat) nem négyzetekben, hanem téglalapokban kell elhelyezni. A téglalap (láda) rövidebb oldala 1 egység hosszú, a másik oldal hossza
a, ahol a > 4/3. A tárgyakat
◦ szintén a láda falával párhuzamosan kell elhelyezni, és lehet®ség van azok 90 -kal való elforgatására. A tárgyak mérete itt is maximum 1 egység lehet mindkét irányban. A rövidebb oldalukat
x,
a hosszabat
egyszerre, de ez az
a
y
jelöli. Az algoritmus maximum 10 nyitott ládát használ
szám növekedésével monoton csökken 7-ig. Az algoritmus minden
érkez® tárgyat el®ször osztályoz, majd megkeresi, hogy a csoportjának megfelel® ládában van-e hely neki; ha van, akkor (a kés®bb leírtak szerint) elhelyezi ott, ha nincs, akkor bezárja a ládát és új ládát nyit, majd ebben helyezi el a tárgyat. A fejezetben el®ször leírom a tárgyak csoportosítását, majd azt, hogy az egyes csoportokba tartózókat hogyan helyezi el az algoritmus, azzal együtt, hogy minimum mekkora részét foglalja el tárgy egy-egy lezárt ládának. Majd alsó és fels® korlátokat adok az algoritmus hatékonysági arányára különböz®
a
paraméterek esetén. Végül leírok két javítási
lehet®séget: az egyik nem módosítja a hatékonysági arányt, de általában csökkenti az összesen felhasznált ládák számát, a másik a hatékonysági arányt csökkenti, de a valóban felhasznált ládák számát akár növelheti is.
3.1.
Csoportosítás
A tárgyakat a csoportosításhoz úgy forgatjuk, hogy a rövidebb, (x-szel jelölt) oldalukon álljanak. Így ha
2/3 < y ;
0<x≤y≤1
teljesül. A ládákat
közepesre, ha
1/2 < y ≤ 2/3; 20
y
szerint 4 f®csoportra osztjuk: hosszúra,
rövidre, ha
1/3 < y ≤ 1/2;
és minire, ha
2/3 1/2 1/3 y
H1
H2
K1
K2b K3
H1
H3
2/3 1/2
R1
1/3
M1,M2 M3
y
1/3 1/2
2/3
H2
K2a K3
K1 R1 M1,M2 M3
3/4=a/2
1/3
x
1/2
2/3=a/3
x 3.1. ábra. Csoportosítás a=3/2 és a=2 esetén
1/3 M1 1/4 M2 1/6 1/8
M1
1/12 M2 M3 1/16 M3 1/24
y
M1,M2
x 3.2. ábra. M1, M2, M3, csoportosítása
y ≤ 1/3.
A további osztályozás alcsoportokra (x és néha
A hosszú f®csoportot felosztjuk H1-re, ha
a/2 < x. ha
A közepeset K1-re, ha
1/3 < x ≤ 1/2
a/3 < y ;
a/3 < x ≤ a/2.
és R2-re, ha az, amire
és
1/24 < y ≤ 1/12; k
y ≤ 1/3 · 1/2 szemlélteti
és
a
H2-re,
a/3 < x ≤ a/2;
és H3-ra, ha
K2a-ra, ha
1/3 < x ≤ 1/2
1/2 < x ≤ 2/3.
és
függvénye.
y ≤ a/3;
A rövideket R1-re, ha
a többi közül M1-be kerülnek azok, amikhez
k
és
K3-ra, ha
szerint) gyakran
K2b-re,
x ≤ a/3;
A minibe tartozók csoportosítása bonyolultabb: M3-ba kerül
y > 1/4 · 1/2
a = 3/2,
x ≤ 1/3;
x ≤ a/3;
y
a=2
∃ k ∈ N,
amire
. A maradék pedig M2-be kerül. A csoportosítást a 3.1 ábra
esetén. Az M1, M2, M3-ba tartozó tárgyak csoportosítása a
3.2 ábrán látható.
21
3.2.
Tárgyak elhelyezése
A más-más típusba tartozó tárgyak általában különböz® módon, és külön-külön ládákban kerülnek elhelyezésre. Mindenhol leírom a legrosszabb kitöltöttségi arányt
4/3 ≤ a < 2
2 ≤ a esetén. Ez a szám azt mutatja meg, hogy egy-egy lezárt láda területének mekkora
és
részén van tárgy. Ezt az alfejezet végén található 3.2 táblázat foglalja össze. A ládák hosszabb oldalukon fekszenek. A tárgyak állítása mindig azt jelenti, hogy a rövidebb oldaluk van alul és felül, a fektetése pedig azt, hogy a hosszabb. A
hosszú
f®csoportba tartozók közül a H1-es tárgyakat a nekik megnyitott ládában
balról folytonosan egymás mellé állítjuk. Ha a soron lev® tárgy nem fér már el, új ládát nyitunk, és ugyanígy folytatjuk a pakolást. Mivel
y > 2/3
minden tárgy esetén, így ha
valamelyik vízszintes tengely szerinti helyen van tárgy a ládában, ott a láda
2/3 magassá-
gig tele lesz. Ez az elrendezés a láda egyik hosszabb oldalára vetítve tulajdonképpen egy egydimenziós ládapakolási feladat, ahol az így maximum az
1/3-a.
a/3
x
oldalak a szakaszok hosszai. Mivel
x ≤ a/3,
hosszú kitöltetlen rész lehet a láda jobb szélén, ami a láda hosszának
Így a H1-típusú láda
2/3 · 2/3 = 4/9
részét biztosan tárgy fedi.
A H2 típusú tárgyakat szintén így állítjuk a ládába, minden H2-es ládában pontosan
2
tárgy fér el. Ezek együttes mérete
2xy > 2 · a/3 · 2/3 = (4/9)a,
annak 4/9 része biztosan ki lesz töltve. H2 típusú elemek csak
a láda mérete
a,
így
a ≤ 3 esetén vannak, a > 3
esetén nincs szükség ilyen ládára. A H3 típusú tárgyakból összesen egy fér egy ládába. Ezért ebb®l nincs is fenntartott nyitott láda, hanem csak az új H3 tárgy érkezésénél nyitunk egyet, és azután rögtön be is zárjuk. Egy ilyen téglalap területe
xy > a/2 · 2/3 = a/3,
van kitöltve. H3 típusú elemek csak
így az
a
méret¶ láda
1/3
részig
a ≤ 2 esetén vannak; a > 2 esetén nincs szükség ilyen
ládára. A
közepes tárgyak közül a K1-be tartozók pakolásához a ládát fel kell osztani: balról
folytonosan felbontjuk
2/3 széles, 1 egység magas sávokra, ameddig lehet. Az ilyen sávokba
fogjuk fektetni lentr®l felfelé folytonosan a tárgyakat; ha az aktuális sávba már nem fér bele az elhelyezend® tárgy, akkor a következ®be kezdünk pakolni. Ha az aktuális tárgyat már egyetlen sávban sem tudjuk elhelyezni, akkor a sávokból kimaradt jobb oldali rész bal szélébe állítjuk. Ett®l fogva ide is pakolunk balról folytonosan. Ha az aktuális tárgyat se sávban, se pedig a kimaradó jobb oldali részben nem tudjuk elhelyezni, akkor az eddig használt ládát lezárjuk, új ládát nyitunk és ebben helyezzük el a tárgyat. Ezt a pakolást a 3.3 ábra is illusztrálja.
22
3.3. ábra. K1-beli elemek elhelyezése egy ládában
3.2.1. Állítás. a≤2
Az aszimptotikus kitöltöttségi arány
esetén minimum
Bizonyítás.
4/3 ≤ a < 2
esetén minimum
2/5,
3/7.
Az els® esetben pont kett® darab
2/3 széles sáv fér el. Ezekben minimum 1/2
hosszú tárgyak fekszenek, így szélességében 3/4-ig vannak kitöltve az ilyen sávok. A tárgyak magassága külön-külön maximum
1/3,
így egy maximum
üresen a sáv tetején, így az magasság szerint
1/2
ilyen sáv minimum
2/3-ig
1/3
magas rész maradhat
ki lesz töltve. Összességében egy-egy
részében lesz tárgy. A kimaradó
a − 4/3
széles részb®l maximum
1/3 szélesség¶ rész marad üresen, és a többi szélessége 1/2 magasságig lesz kitöltve. Így a (2 · 2/3 · 1/2)/a,
kitöltöttségi arány: ha
a ≥ 5/3;
ez az
a = 5/3-ban
ha
a < 5/3
és
(2 · 2/3 · 1/2 + (a − 4/3 − 1/3) · 1/2)/a,
veszi fel a minimumát, ahol
2/5
értéket vesz fel.
A második esetben nem egyértelm¶, hogy mennyi sáv lesz, így a sávok száma (n) és a láda mérete (a) szerint is minimalizálni kell. A sávok száma z®vel megegyez®en minden esetben minimum pedig minimum ha
n = b(3/2)ac. A sávok az el®-
1/2 részig lesznek kitöltve. A kimaradó rész
d ∈ [0, 1/4) arányban, ahol d = 0, ha a − 32 n ≤ 1/3, és d =
a − 32 n > 1/3.
Így a teljes láda kitöltöttsége
minimalizálni szeretnénk, akkor egyrészt az
1/2
1/2
és
d
1 2
·
a−(2/3)n−1/3 , a−(2/3)n
konvex kombinációja lesz. Ha ezt
súlyát kell csökkentenünk, másrészt
0-t
b3a/2c2/3·1/2 2 , ha a − n ≤ 1/3, és választani 0 és 1/4 közül. A minimalizálandó függvény: a 3 b3a/2c2/3·1/2+(a−1/3−2/3·b3a/2c)·1/2 2 , ha a − n > 1/3. Ez a = 7/3 esetén veszi fel a minimumot, a 3 akkor a kitöltöttség
3/7
lesz.
A K2a-ba és K2b-be tartozó tartozó tárgyakhoz két-két egyforma vízszintes sávra osztjuk a ládát. A K2a és K2b típusúak külön ládába kerülnek. Mindkét esetben balról folytonosan fektetjük a tárgyakat a sávokba, amíg valamelyik sávban még van hely. (Amíg mindkét sávban van hely, addig mindegy, hogy melyikben helyezzük el a tárgyat.) K2a esetén minden sáv
1/3
magaságig ki lesz töltve, hosszra pedig maximum
marad a jobb oldalukon, így a teljes elfoglalt terület minimum kitöltöttség minimum
a/3
2 · 1/3 · 2/3 · a
üres rész
lesz, így a
4/9. K2b csak a > 2 esetén fordul el®. Egy sávba pontosan két ilyen 23
3.4. ábra. K2a-beli és R1-beli tárgyak elhelyezése, valamint K2b és R2-beli tárgyak elhelyezése
elem kerülhet, így a ládába összesen kitöltöttségi arány
4/9.
4.
Az elfoglalt terület
4xy ≥ 4 · 1/3 · a/3 = 4/9 · a,
a
Ezt az elhelyezést a 3.4 ábra szemlélteti.
A K3-ba tartozó tárgyakat balról folytonosan, állítva pakoljuk egy ládába, majd ha nem fér bele az aktuális tárgy, akkor a ládát lezárjuk, és újat nyitunk. A kitöltöttségi arány megmutatására nem elég egy ládát nézni, néhány ládához a kövekez® K3-as láda kitöltött részéb®l hozzászámolunk egy darabot, természetesen azt a következ® láda kitöltöttségébe már nem számoljuk bele.
3.2.2. Állítás. a < 2;
és legalább
Bizonyítás. mivel
Minden K3 típusú láda aszimptotikus kitöltöttsége legalább
Ha
3/8,
ha
1/3,
ha
4/3 <
2 ≤ a.
a ≤ 3/2,
akkor pont két tárgy fér el; ezek összmérete több, mint
2 · x · y < 2 · 1/2 · 1/2 = 1/2.
1/2 kitöltöttség több, mint 3/2
= 1/3.
A láda mérete maximum
3/2,
1/2,
így a minimális
A többi esetben azt mutatom meg, hogy egy láda
magasságig minden esetben ki lesz töltve, és általában szélességében csak
1/2
1/2
rész marad
üresen. Ha mégsem, akkor a következ® láda ennél nagyobb mértékben van kitöltve, ami a hiányt kompenzálja. Mivel láda szélességében Ha
u > 1/2,
y > 1/2,
u ∈ [0, 2/3)
akkor bontsuk fel
már nem fért bele a ládába,
így magasságban
1/2-ig
széles rész maradhat ki. Ha
u = 1/2 + v
ki lesz töltve a láda. A
u < 1/2,
akkor rendben van.
alakban. Ez esetben a soron lev® tárgy, ami
x > u = 1/2 + v
széles, és
y ≥ x > 1/2 + v
magas. Ha az
elhelyezett tárgy tetejér®l képzeletben levágunk egy
v magas sávot (továbbiakban pótsáv),
1/2
magasságú marad. Ha ezt a pótsávot
akkor a megmaradt rész még mindig legalább
elfordítjuk, és a régi láda végébe állítjuk, akkor annak már csak
1/2
rész fog hiányozni
a szélességéb®l. A pótsáv mérete miatt a magassága is el fogja érni az
1/2-et.
A pótsáv
áthelyezését a 3.5 ábra illusztrálja. A láda kitöltöttsége így minimum
2≤a
esetén pedig
1/2·(a−1/2) , ez a
3/8. 24
3/2 ≤ a < 2
esetén minimum
1/3,
3.5. ábra. Két egymást követ® K3-as láda pakolása, az áthelyezett pótsávot a két pöttyözött rész jelöli
A
rövid f®csoportból az R1-beliek pakolásához két egyforma vízszintes sávra osztjuk a
ládát, és a tárgyakat balról folyamatosan állítva pakoljuk a sávokba. Ezt addig folytatjuk, amíg olyan elem nem jön, ami már az egyik sávba sem fér bele, ekkor az eddig használ ládát lezárjuk, és új ládát nyitunk. Mindkét sáv van benne valami), és maximum legalább
4/9
1/3
magasságig ki lesz töltve (ahol egyáltalán
a/3 üres részek lesznek a jobb szélükön. Így a kitöltöttsége
lesz.
Az R2-be tartozókat szintén így pakoljuk két sávba. Mindkét sávban pont két tárgy fér el, a ládában minimum
4 tárgy van, melyek összmérete 4xy ≥ 4·a/3·1/3 = (4/9)a, így a kitöltöttség
4/9.
R2-beli elemek csak
3.2.3. Megjegyzés.
a < 3/2
esetén vannak.
A K2a és R1; valamint a K2b és R2 típusú elemek pakolása meg-
egyezik. Így a K2a és R1 számára elég egy ládát fenntartani, míg a K2b és R2-belieknek is elég összesen egy nyitott láda. A
minik pakolásához az egy típusba tartozókat még tovább kell csoportosítani.
Az M1-beli tárgyak további felosztásához de niáljuk a következ® függvényt:
min{1/3 · 2k | 1/3 · 2k ≥ y, k ∈ N}.
Minden
y
magasságú ládát egy
g(y)
g(y) :=
magasságú (szé-
lesség¶) sávba fogunk állítani (fektetni). A fekv® sávok hossza nincs el®re rögzítve, hanem az érkez® tárgyak függvénye. Ezek közül az egyiket két oldalról fogjuk pakolni különböz® méret¶ elemekkel, a sáv akkor telik be, amikor középen már majdnem összeérnek a különböz® típusú tárgyak. A ládát alsót még két vízszintes bal végének egy (k
∈ N)
1/6
3
darab
1/3
magasságú f®sávra osztjuk. Ezek közül az
magas sávra osztjuk, de csak a jobb oldalán. A fels® f®sáv
1/12 széles részét további függ®leges sávokra osztjuk fel, ezek rendre
szélesek. Azokat a tárgyakat, melyekre
g(y) = 1/3,
1 12·2k
balról folytonosan pakoljuk a
f®sávokba, el®ször a fels®be, majd a középs®be,aztán az alsóba, egészen addig, amíg ezekben van hely. Az
1/6
magas sávba való tárgyakat jobbról pakoljuk folytonosan, mindig
abba a kicsi sávba, amelyikben az utoljára elhelyezett tárgy bal széle jobbrább van. Ha
25
3.6. ábra. M1, és M3-beli tárgyak pakolása
az alsó f®sávban már nem fér el az aktuális
1/6-os
tárgy, akkor a középs® sávot ugyanúgy
felosztjuk, mint kezdetben az alsót, és ide pakolunk tovább. Az ezeknél kisebb tárgyakat a nekik megfelel® fels® f®sávban álló kicsi sávba fektetjük folytonosan. Ha egy ilyen kicsi sávban már nem fér el a soron lev® tárgy, akkor nyitunk egy vele megegyez® méret¶ ki-
1/3-os
csi sávot, amit úgy helyezünk el az
f®sávban, mintha egy
1/3
magas tárgy lenne;
innent®l fogva ide pakoljuk az ennek megfelel® méret¶ elemeket. Egy láda akkor telik be, ha az éppen elhelyezend®
1/3-os
vagy
1/6-os
tudunk új kicsi sávot nyitni egy elhelyezend®
tárgyat nem tudjuk elhelyezni, vagy nem
1/24-es,
vagy annál kisebb tárgynak. Az
M1-beliek pakolását a 3.6 ábra illusztrálja.
3.2.4. Megjegyzés.
Az
1/24-es, és annál kisebb tárgyaknak nem feltétlenül kellene el®re
kis sávokat lefoglalni, mert lehet, hogy nem lesz rájuk szükség; viszont ekkor bonyolultabb lenne mindig megkeresni az aktuális tárgyhoz tartozó kicsi sáv helyét.
Az M2-be tartozó tárgyak pakolása hasonlóan történik. A tárgyak besorolását a
h(y) :=
min{1/4·2k | 1/4·2k ≤ y} függvény adja meg. A ládát 4 darab 1/4 magas f®sávra bontjuk, az alsó f®sáv jobb oldalán két darab
1/8
széles kisebb sáv indul.
le a fels® f®sáv bal végéb®l a kicsi sávoknak, amik rendre
1/16 k
1/16 · 2
pakolás ugyanúgy történik, és itt is igaz marad a megjegyzés, csak Az M3-ba tartozók pakolásához sávot bal oldalról
1/16
3
kisebb
1/12
széles részt vágunk
(k
∈ N)
szélesek. A
1/32-del.
4 darab 1/4 magas f®sávra osztjuk fel a ládát. A fels®
magas sávra bontjuk, az alsót pedig jobbról
szélesre. Az el®bbiekbe pakoljuk állítva azokat a tárgyakat, melyekre
4
darab
y > 1/16;
az
utóbbiakba pedig a többit. Ha egy f®sávba már nem fér bele az aktuális tárgy, akkor közvetlenül alatta vagy fölötte nyitunk egy ugyanolyat, mint ami éppen betelt. Új ládát akkor nyitunk, ha valamelyik sávban összeérnek a tárgyak (az aktuálisan elhelyezend® vagy egy
1/12-esbe,
vagy egy
1/16-osba
belelógna), vagy mind a
elemek pakolását is a 3.6 ábra illusztrálja.
26
4
sáv betelt. Az M3-beli
3.2.5. Állítás. 0.48, 2 ≤ a 2
esetén
Az M1-be tartozó ládák kitöltöttségi aránya
esetén
319/576 > 0.55.
Az M2-be tartozó ládák kitöltöttségi aránya
1111/2304 > 0.48, 2 ≤ a
kitöltöttségi aránya
Bizonyítás.
4/3 ≤ a < 2
esetén
esetén
605/1152 > 0.52.
79/128 > 0.61, 2 ≤ a
M1 esetén a sávok a rövidebb oldaluk
1/3
ami már nem fért ide, kevesebb, mint
1/3
1/3-os
Az M3-be tartozó ládák
esetén
365/576 > 0.63.
tárgyakat tartalmazó sávban
x ≤ y < 1/3,
széles rész marad üresen, mivel
így az új sávot nyitó elem,
széles lehet. Ez összesen
területegység. A csak 1/6-os tárgyakat tartalmazóban pedig maximum
1/6 = 1/18
4/3 ≤ a <
3/4-éig mindig ki vannak töltve, mert
az ennél kisebb tárgyak már M2-be kerülnek. A csak maximum
4/3 ≤ a < 2 esetén 187/384 >
1/3 · 1/3 = 1/9
1/6 széles, ez 1/3 ·
területegység. Amelyik sávban mindkét féle tárgy van, abban a maximális
kimaradó terület
1/3 · 1/3 + 1/6 · 1/6 = 5/36.
Az utóbbi tulajdonságú sávból csak egy
lehet minden ládában, így a legtöbb üresen maradó rész akkor fordulhat el®, ha kett®
1/3-os,
és egy vegyes sávunk van. Ez összesen
2 · 1/9 + 5/36 = 13/36
területegység. Az
üresen maradó részhez még hozzá kell vennünk a kicsi sávokban kimaradó helyeket, ennek fels® becsléseként tekinthetjük az összes megnyitott, de még nem lezárt kicsi sávot. Mivel minden sávméretb®l összesen egy van, így ezek összterülete
1/3 · 1/12 = 1/36.
Így már
csak a lezárt kicsi sávok végén maradó kihasználatlan területet nem vettük gyelembe. Ez minden esetben maximum akkora lehet, mint a kicsi sáv szélessége, ez a legnagyobb, azaz
1/24
széles kicsi sávnál veszi fel a maximumát, ami a kicsi sáv területének az
szám a 3.2.2 állítás bizonyításához hasonló módon lecsökkenthet® kicsi sáv végén
Ez a
1/12-re. Ha egy 1/24-es
2/3 · 1/24 + u = 1/36 + u rész marad üresen, akkor a következ® kicsi sávban
az els® tárgy minimum u-val szélesebb lesz, mint az eddig kitöltöttnek számolt
1/36
1/8-a.
2/3·1/24 =
széles rész, így ezt a kilógó részt képzeletben az el®z® lezárt sávba helyezve, annak
a kitöltetlen része minimum lesz. Ha ilyen
11/12 · 3/4 ·
1/24
csökken, így a hosszanti kitöltöttsége
Másrészt
4/3 ≤ a < 2
2≤a
esetén
esetén
vegyesben
1/4 · 1/4
ahol
2/3-ig
rész marad maximum üresen, az
1/4 · 1/4 + 1/8 · 1/8,
a
veszi fel a minimumát, ami
319/576 > 0.55. ki lesznek töltve a sávok. Az
1/8-osban
4 sávban összesen (három 1/4-es,
3 · 1/4 · 1/4 + 1/4 · 1/4 + 1/8 · 1/8 = 17/64. 1/4 · 1/16 = 1/64
a = 4/3-nál
a = 2-ben,
M2 esetén a rövidebb oldal szerint minimum es sávokban
11/12
széles kicsi sávokkal lesz tele a láda, a kitöltöttség akkor is minimum
a−13/36−1/36 . Ez a
187/384 > 0.48.
u · 1/36-dal
maximum
1/4-
1/4 · 1/8,
a
egy vegyes) maximum
A kitöltetlen kicsi sávok miatt legfeljebb
rész maradhat üresen. A lezárt kicsi sávok végén lev® üres rész miatti
kitöltési arány az el®z®höz hasonlóan
1/12-el csökkenhet. Így az összkitöltöttség minimum 27
a−17/64−1/64 . Ez a
11/12 · 2/3 ·
1111/2304 > 0.48
Másrészt
4/3 ≤ a < 2
2≤a
esetén
esetén
a = 2-ben,
M3 pakolása esetén a sávok minimum Így
2/3-dal
2/3
ahol
605/1152 > 0.52.
3/4
vagy
veszi fel a minimumát, ami
magasságig lesznek kitöltve.
számolva alsó becslést kapunk a kitöltöttségre. Egy csak
tartalmazó befejezett f®sávban maximum csak
a = 4/3-nál
1/16-os
1/4 · 1/12
tárgyakat tartalmazóban legfeljebb
1/12-es
tárgyakat
terület¶ rész marad üresen. Egy
1/4 · 1/16.
A vegyesben kevesebb mint
1/4 · 1/12 + 1/4 · 1/16. Négy ilyen összege maximum 3 · 1/4 · 1/12 + 1/4 · 1/12 + 1/4 · 1/16 = 19/192.
Így a teljes láda kitöltöttsége több, mint
a = 4/3-nál ahol
veszi fel a minimumát, ami
2/3 ·
79/128 > 0.61.
a−19/192 . Ez a Másrészt
4/3 ≤ a < 2
2≤a
esetén
esetén
a = 2-ben,
365/576 > 0.63.
Ládatípus
4/3 ≤ a < 2
2≤a
H1
4/9
4/9
H2
4/9
4/9
H3
1/3
-
K1
2/5
3/7
K2a és R1
4/9
4/9
K2b és R2
4/9
-
K3
1/3
3/8
M1
>0.48
>0.55
M2
>0.48
>0.52
M3
>0.61
>0.63
3.1. táblázat. Kitöltöttségi arányok legrosszabb esetekben
3.3.
Általános alsó korlát a feladatra
A négyzetbe pakoló algoritmusokhoz hasonlóan itt arra adok alsó becslést, hogy egy algoritmus a legrosszabb esetben hányszor annyi ládát használhat, mint az optimális o ine pakolás. Mivel a hatékonysági arány az
a szám függvénye, így az a értékét®l függ®en több
becslést adok. Az el®z®ekhez hasonlóan olyan ládasorozatokat fogok konstruálni, amiknek az optimális o ine elhelyezése
n darab egyformán kitöltött ládában történik. Mindhárom
esetben el®ször egy darab ilyen o ine ládában szerepl® tárgyakat fogom megadni. Majd az
28
D
D
D
B A
D C D
3.7. ábra. O ine pakolás az alsó korláthoz
4/3 < a ≤ 3/2
esetén
o ine ládában szerepl® összes tárgyra megadom, hogy csak olyanból maximum mennyi fér el egy ládában. Ez alapján meg lehet mondani, hogy az egyes tárgyakból mennyi ládában fér el. Ebb®l pedig kiszámítható, hogy az
n
n
darab
darab o ine láda tárgyait
minimum mennyi ládába pakolja akármelyik online algoritmus. Ha
4/3 < a < 3/2,
a/3 +
és öt darab
akkor minden o ine ládában lesz egy
a/7 +
oldalú négyzet. Ezeket rendre
a/2 + ,
A, B, C, D
egy
1/2 +
egy
bet¶kkel jelölve
az elrendezés leolvasható a 3.7 ábráról. A maradék részt is teljesen kitöltjük akármilyen méret¶ kicsi téglalapokkal, a továbbiakban ezeknek a neve apró téglalapok lesz. Jelöljük
r-rel, r≈
azt, hogy az apró téglalapok a láda területének hányadrészét foglalják el. Ekkor
a−a2 /4−1/4−a2 /9−5·a2 /49 . Az a
oldalúból kett®,
a/3 +
a/2 + oldalú négyzetekb®l 1 fér bele egy ládába, az 1/2 +
oldalúból négy. Az
lasztást kell csinálni aszerint, hogy felett, így a ládában összesen összesen
oldalú négyzetek esetén esetszétvá-
vagy nem. Els® esetben
4
láda fér el egymás
24, második esetben 5 láda fér el egymás fölött, így a ládában
30 darab pakolható. Így n darab o ine láda tartalmának elpakolásához legalább
n + n/2 + n/4 + 5 · n/24 + n · r ládát, ha
a ≥ 5/7.
Ez a minimumát Ha
a > 5/7,
a/7 +
ládát használ, ha
a > 5/7, és n + n/2 + n/4 + 5 · n/30 + n · r
Ha ezek közül a másodikat tekintjük, akkor egy alsó becslést kapunk.
∞ a = 3/2-ben veszi fel, ahol 2417/1176·n > 2.05·n. Így R4/3
2.05.
3/2 < a < 2,
akkor az o ine ládákban van egy
négyzet, és egy oszlopban annyi
a/7 +
a/2 + ,
és egy
a/3 +
oldalú
oldalú négyzet, amennyi elfér egymás felett. Ezt
a 3.8 ábra is illusztrálja, a négyzeteket rendre
A, B, C
szintén kitöltjük apró téglalapokkal. Ez esetben
r≈
bet¶kkel jelölve. A maradék részt
a−a2 /4−a2 /9−a/6 . Mivel a
a/3 + > 1/2,
így az ilyen oldalú négyzetekb®l csak kett® fér el egy ládában, a többi tárgyra ez a szám megegyezik az eddigivel. Most
n darab o ine láda tartalmát legalább n + n/2 + n/6 + n · r
ládába pakolja minden online algoritmus. Ez a minimumát
16/9 · n >
∞ 1.77n. Így R3/2
> 1.77.
29
a= 2
esetén veszi fel, ahol
C C A
C
B
C
3.8. ábra. O ine pakolás az alsó korláthoz
Ha és egy Az
3/2 < a ≤ 2
2 < a < 3, akkor az o ine láda tartalmazzon kett® darab a/3 + oldalú négyzetet, a/4 +
a/3 +
oldalú négyzetet. A kimaradó részt szintén apró téglalapokkal töltjük ki.
oldalú négyzetekb®l most kett® fér el egy ládában, az
Az apró téglalapoknak kimaradó hely ebben az esetben ilyen o ine láda tartalmát minimum algoritmus. Ennek minimuma
3.4.
esetén
2 · n/2 + n/3 + n · r
r =
a/4 +
oldalúakból 3.
a−2·a2 /9−a2 /16 . Így a
n
darab
ládába pakolja bármelyik online
∞ > 1.47. a = 3-ban van, ahol 71/48·n > 1.47n. Ezért R2
Fels® korlát az algoritmusra
El®ször a
4/3 < a < 2
sorozata. Jelölje
h3
esetet nézzük. Legyen
L
elpakolni való kis téglalapok
n
elem¶
azoknak a ládáknak a számát, amennyibe az algoritmus H3 típusú
tárgyakat pakolna az
L
sorozatból;
pakolására használna. Jelölje
k3
pedig azoknak a számát, amennyit K3 típusúak
S az L sorozatban lév® tárgyak összterületét, S−h3 −k3
pedig a
H3-on és K3-on kívüli tárgyak összterületét. Mivel az algoritmus a H3 és K3 típusú tárgyak kivételével a ládákat minimum
2/5 arányban kitölti, így az ezen kívüli elemeket maximum
2, 5 · S−h3 −k3 + O(1) ládába pakolja. Így összesen maximum k3 + h3 + 2, 5 · S−h3 ,−k3 + O(1) ládát használ. Az optimális online pakolásra igazak az alábbiak:
•
minimum annyi ládát használ, amennyi a tárgyak összterülete
•
minimum annyi ládát használ, amennyi H3-beli tárgy van a sorozatban, mivel ezekb®l mindig 1 darab kerülhet az online algoritmus szerint is egy ládába, ezért ezek darabszáma legalább
•
minimum
h3
h3 + 2/3 · (k3 − 1/2 · h3 )
ládát használ. Mivel, ha K3 és H3 beli tárgyak
is vannak, akkor ha az o ine el®ször a H3-beli elemeket rakodja egyesével ládákba, akkor minden H3-at már tartalmazó ládába még maximum egy darab K3-beli elemet még el lehet helyezni. Mivel az online minimum 2 darab K3-beli elemet rakott egy
30
ládába, így az ilyen módon elpakolható K3-beli ládák száma maximum minimum
k3 − 1/2 · h3
h3 /2.
Ezért
ládányi K3-as elemet kell még elpakolni. Mivel ezekb®l 2
vagy 3 tárgy lehet egy ládában, így ha az online ládákba mindig ügyetlenül 2 került, az o ine pedig ügyesen 3-at rak egy ládába, az o ine akkor is minimum 2/3-szor annyi ládába pakolja ®ket, mint az online, azaz minimum
2/3 · (k3 − 1/2 · h3 )
ládát
használ a kimaradt K3-ak pakolására. Így az optimális online pakolás legalább
h3 + 2/3 · k3 }
ládát használ. Így a hatékonysági arányra teljesül, hogy:
∞ R3/4
Mivel
max{S, h3 , k3 +2/3·(k3 −1/2·h3 )} = max{S, h3 , 2/3·
k3 + h3 + 2, 5 · S−h3 −k3 . max{S, h3 , 2/3 · h3 + 2/3 · k3 }
S ≥ S−h3 −k3 + 1/3 · h3 + 1/3 · k3 ,
így
S−h3 −k3
ezen egyenl®tlenség szerinti fels®
becslését írva az egyenl®tlenségbe, még mindig egy fels® becslést kapunk
∞ R3/4
Ha
∞ -re. Így: R3/4
1/6 · h3 + 1/6 · k3 + 2, 5 · S h3 + k3 + 2, 5 · (S − 1/3 · h3 − 1/3 · k3 ) ≤ . max{S, h3 , 2/3 · h3 + 2/3 · k3 } max{S, h3 , 2/3 · h3 + 2/3 · k3 }
max{S, h3 , 2/3·h3 +2/3·k3 } = S , akkor 2/3·h3 +2/3·k3 ≤ S azaz 1/6·h3 +1/6·k3 ≤ S/4
szerint a jobb oldal nevez®ben
2.75.
Ha
S
és
1/4·S+2,5·S S
≤
= 2.75.
2/3 · h3 + 2/3 · k3
helyett
Ha
max{S, h3 , 2/3 · h3 + 2/3 · k3 } = h3
h3 -at
helyettesítve a jobb oldal
max{S, h3 , 2/3 · h3 + 2/3 · k3 } = 2/3 · h3 + 2/3 · k3 .
2/3·h3 +2/3·k3 -at helyettesítve a jobb oldal ≤
≤
Akkor a nevez®ben
1/6·h3 +1/6·k3 +2,5·(2/3·h3 +2/3·k3 ) 2/3·h3 +2/3·k3
esetén a
1/4·h3 +2,5·h3 h3
S
=
helyére
= 2.75. Ezekb®l
következik, hogy
∞ ≤ 2.75 3.4.1. Állítás. R4/3
a > 2
Tekintsük most az téglalapok sorozata;
k3
pakolására használna,
esetet. Ugyanúgy, mint eddig, legyen
L
elpakolni való kis
azoknak a ládáknak a száma, amennyit az algoritmus
S
az L-beli tárgyak összterülete.
S−k3
K3 típusúak
pedig a K3-on kívüli tárgyak
összterülete. Mivel az algoritmus a K3 típusú tárgyak kivételével a ládákat minimum arányban kitölti, így az ezen kívüli elemeket maximum Így összesen maximum egyrészt minimum egyrészt
S
k3 + 7/3 · S−k3 + O(1) esetén minimum
3
ládába pakolja.
ládát használ. Az optimális o ine pakolás
ládát használ, másrészt minimum
2 < a < 8/3
7/3 · S−k3 + O(1)
3/7
3/5 · k3 -at.
és maximum
5
Azért
3/5 · k3 -at,
mert
K3 típusú elem kerülhet egy
ládába. Így ha az online algoritmus csak hármat helyezne el minden ládában, míg az
31
o ine ötöt, akkor az online által felhasznált ládák számának a az o ine. Másrészt maximum
2/3
a > 8/3
3/5-szeresét
esetén, a csak K3-at tartalmazó ládák végén a kimaradó
széles rész a láda hosszának kevesebb, mint egynegyede; így ha az összes
o ine szélességében teljesen ki van töltve, míg az online-ok csak
3/4-szer
használná fel
3/4-ig,
annyi ládát használ, mint az online, ez pedig alulról becsülhet®
Így az optimális o ine pakolás legalább arányra teljesül, hogy:
∞ R2
akkor az o ine
3/5-del.
max{S, 3/5·k3 } ládát használ. Így a hatékonysági
k3 +7/3·S−k3 . Mivel max{S,3/5·k3 }
S ≥ S−k3 + 3/8 · k3 ,
így ha
S−k3
ezen
∞ egyenletlenség szerint becsüljük felülr®l, még mindig egy fels® becslést kapunk R2
∞ ≤ R2
k3 + 7/3 · S − 3/8 · k3 1/8 · k3 + 7/3 · S ≤ . max{S, 3/5 · k3 } max{S, 3/5 · k3 }
Ha
max{S, 3/5 · k3 } = S ,
Ha
max{S, 3/5 · k3 } = 3/5 ·
1/8·5/3·S+7/3·S = 2.5416˙ . S +7/3·3/5·k3 ∞ k3 , akkor R2
akkor
∞ ≤ R2
= 2.5416˙ .
Így teljesül az
alábbi
∞ 3.4.2. Állítás. R2
3.5.
Javítási lehet®ségek
Az eddig leírt algoritmus arra volt kihegyezve, hogy a legrosszabb esetben teljesítsen jól. Ezért egy ládába általában csak egy típusba tartozó tárgyakat helyezett el, mivel így elkerülhet®, hogy több egyforma nyitott ládánk legyen, amibe még beleférne egy tárgy, de olyan típusú tárgy éppen nem jön. Az átlagos esetben sokat javíthat az algoritmuson, ha egy-egy ládába többféle tárgy is kerülhet. Az algoritmusban van olyan típusú elem, aminek a pakolása során a legjobb esetben is marad kitöltetlen rész a ládában. Például az R3-beli tárgyak pakolásakor egy
1/3
magas sáv a ládák tetején mindenképpen üresen
marad. Az éppen nyitott ilyen típusú láda fels®, üresen maradó részébe pakolhatnánk M1beli elemeket, olyan módon, mintha az egy M1-láda f®sávja lenne. Ennek a módosításnak a haszna az M1 és R3-beli elemek arányától, és ezeknek a tárgyaknak a sorrendjét®l függ. El®fordulhat olyan eset is, hogy nem lesz kevesebb a felhasznált ládák száma. Erre példa, ha egyáltalán nincsenek M1-beli elemek, vagy ha a ládasorozatban az összes M1-beli tárgy megel®zi az R3-belieket. Ezért ez a javítás a hatékonysági arányra kiszámolt fels® korláton nem feltétlenül javítana, de azt biztos nem rontaná.
32
A megnyitott ládák megengedett számának növelése esetén a csoportosításon lehetne nomítani, és ez is növelheti a hatékonysági arányt. Természetesen itt a megnyitott ládák számának növelésével az algoritmus egyre nehézkesebbé válik. Ha pedig csak kevés tárgyat kell elpakolni, akkor lehet, hogy összességében több ládába pakol egy több nyitott ládával dolgozó és jobb hatékonysági arányú algoritmus, mint egy kevesebb nyitott ládát használó, de kisebb hatékonysági arányú. Ennek az az oka, hogy a hatékonysági arány egy aszimptotikus mér®szám, ezért kis ládaszámnál nem feltétlenül m¶ködik jól.
33
4. fejezet
Irodalomjegyzék
[1] S. FUJITA, T. HADA.
Two-dimensional on-line bin packing problem with rotatable
items. Theoretical Computer Science 209 (2002) 939-952 [2] L. EPSTEIN.
Two-dimensional online bin packing with rotation. Theoretical Com-
puter Science 411 (2010) 2809-2911 [3] M. M. MEHDI, S. P. WILLEMS.
Online Algorithm Used to Improve US Steel Dis-
tributors Yield Performance. 2012, beküldve: Manufacturing & Service Operations Management [4] L. EPSTEIN, R. VAN STEE.
Optimal online algorithms for multidimensional packing
problems. SIAM Journal on Computing 35 (2) (2005) 431-448 [5] X. HAN, F.Y.L. CHIN, H.-F. TING, G. ZHANG, Y. ZHANG.
A new upper bound
on 2D online bin packing. CoRR, abs/0906.0409, 2009 [6] L. EPSTEIN, R. VAN STEE.
Online square and cube packing. Acta Informatica 41
(9) (2005) 595-606.
34
