Eötvös Loránd University Faculty of Science
Györgyi Péter
Hálózati optimalizálási modellek BSc szakdolgozat
Témavezet®:
Frank András, egyetemi tanár Operációkutatási Tanszék
Budapest, 2010
El®szó
Szeretném megköszönni a témavezet®mnek, Frank Andrásnak, hogy a rendszeres konzultációink során irányította munkámat, szakmai és formai észrevételei sokat segítettek a szakdolgozatom elkészítésében.
i
Tartalomjegyzék
Bevezet®
1
Jelölések
3
1. Három példa
4
1.1. Van-e még esély a bajnoki címre? . . . . . . . . . . . . . . . . . . . .
4
1.2. Repül®jegyek szétosztása . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3. Optimális energiapolitika meghatározása . . . . . . . . . . . . . . . .
6
2. A probléma felvázolása
8
2.1. A feladat meghatározása . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2. A matematikai modell . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.3. A célfüggvény . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3. A standard eset
12
3.1. Az eset áttekintése . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2. Egy egyszer¶sítési lehet®ség . . . . . . . . . . . . . . . . . . . . . . . 13 3.3. Az egy sor esete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4. A hálózati modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4. Az ütközésmentes eset
20
4.1. Egy technikai akadály . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2. Az els® modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3. A második modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
ii
TARTALOMJEGYZÉK
iii
5. Egy újabb feltétel
27
5.1. A nyúlvány-és-horony kialakítás . . . . . . . . . . . . . . . . . . . . . 27 5.2. A minimális TG-hiba modellezése . . . . . . . . . . . . . . . . . . . . 29
6. A minimális felbontásszám
31
6.1. Burkard tétele kétsoros mátrixra . . . . . . . . . . . . . . . . . . . . . 31 6.2. Baatar tétele egysoros mátrixra . . . . . . . . . . . . . . . . . . . . . 31
7. Az egészérték¶ség problémája
34
7.1. A kanonikus felbontás . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7.2. Kanonikus felbontás minimális TG-hiba esetén . . . . . . . . . . . . . 36 7.3. Az optimális felbontás meghatározása . . . . . . . . . . . . . . . . . . 37
Irodalomjegyzék
41
Bevezet®
Számos gyakorlatban felmerül® probléma jól kezelhet® gráfok segítségével, majd a gráfalgoritmusok gyakran vezetnek a feladat megoldásához. Az optimalizálási feladatok esetén különféle mennyiségek optimumát (minimumát, maximumát) kívánjuk meghatározni. A gráfokon jó néhány optimalizáló algoritmus ismert, ilyen például Dijkstra-algoritmus a legrövidebb út keresésére pozitív élköltségek esetén, vagy a Ford-Fulkerson-algoritmus a maximális folyam meghatározására. Bizonyos esetekben a gráf segítségével jutunk egy lineáris programozási feladathoz, felhasználva a gráf valamilyen nevezetes mátrixát. A szakdolgozatom célja, hogy különféle gyakorlati problémákat visszavezessünk egy már ismert hálózati optimalizálási feladatra. Néhány esetben teljesen természetesen adódik ez a visszavezetés. Vannak azonban olyan feladatok, ahol el®ször nem is gondolnánk az ilyen jelleg¶ megoldásra, pedig sok esetben gyorsabb algoritmust kapunk az eredeti problémára, mint más, közvetlenebb módszerrel. Szakdolgozatom elején bemutatom három egyszer¶ feladat leírását a gráfok segítségével úgy, hogy a kapott gráfon, egy jól ismert algoritmus segítségével, meg tudjuk oldani az eredeti feladatot. A szakdolgozat nagyobbik része egy bonyolultabb problémát ír körül. A rákos betegek sugárkezelésénél merül fel egy optimalizálási feladat: egy ismert kiterjedés¶ daganatot akarunk sugárzásnak alávetni, hogy a daganat megsemmisüljön, de az ép sejtek a lehet® legkevésbé károsodjanak. A sugárzás szabályozásában fontos szerepe van egy eszköznek, a Multileaf Collimator-nak. Ezen gép beállításai próbáljuk meghatározni úgy, hogy különböz® feltételeknek eleget tegyünk. A 2. fejezetben felvázoljuk a problémát, majd megadjuk egy matematikai modelljét (mátrixok segítségével). A következ® fejezet a standard esetr®l szól, ezt átírjuk egy minimális költség¶ folyam meghatározásának problémájára. A 4. fejezet 1
BEVEZET
2
egy, a gyakorlatban fontos, feltételt szab meg nekünk. Ez lényegesen bonyolultabbá teszi a feladatot, azonban a megoldást továbbra is kereshetjük egy minimális folyam képében, igaz most már lényegesen bonyolultabb a gráfunk és mellékfeltételeket is kénytelenek leszünk tenni. Az ezt követ® fejezet Bárász Mihály [5] eredményeit, amelyben egy újabb megkötést tesz számunkra, írja át a folyamproblémára. Az utolsó el®tti fejezet bemutat egy az ugyanebben a környezetben felmerül® feladatot, amelyr®l belátjuk, hogy módszereinkkel kezelhetetlen, hiszen NP-nehéz. Legvégül vázlatosan ismertetünk egy másik módszert, amely egy elméletben fontos eredményt, az egészérték¶séget biztosítja számunkra.
Jelölések
Ha külön nem jelezzük, akkor egy G = (V, E) gráf csúcsszáma n, élszáma m. Irányított gráf esetén gyakran A-val jelöljük az élek halmazát. A v csúcsba befutó élek halmazát A− (v)-vel, az onnan indulókat A+ (v)-vel jelöljük. Az éleken lév® esetleges költségfüggvény c (a nem jelölt éleken az értéke 0), a fels® és alsó korlátokat u(e)-vel és l(e)-vel jelölöm az e élen. Ezek a korlátok alapesetben +∞ illetve −∞ értékeket vesznek fel (természetesen sok esetben az l ≡ 0-t is nyilvánvaló-
nak vesszük). A csúcsokon lehetnek feleslegeink illetve igényeink, ezeket az i. csúcs esetén bi -vel jelöljük, felesleg esetén bi > 0, igény esetén bi < 0. Egy folyam értékét az e élen x(e)-vel jelöljük, nyilván minden e esetén l(e) ≤ x(e) ≤ u(e). A folyamunknak ki kell elégítenie az igényeinket a feleslegeinkb®l, azaz minden v ∈ V -re bv +
P
e∈A− (v)
x(e) −
P
e∈A+ (v)
x(e) = 0.
3
1. fejezet
Három példa
Ebben a fejezetben néhány gyakorlati példán keresztül bemutatjuk a hálózati modellezés hasznosságát, széles alkalmazhatóságát. A fejezet alapvet®en válogatás [3]-ból. Ezen könyvben számos gráfalgoritmusokra találhatóak alkalmazások, most azonban a teljesség igénye nélkül válogatunk közülük.
1.1.
Van-e még esély a bajnoki címre?
A feladatunk az, hogy baseball bajnokság egy adott pillanatában eldöntsük, hogy van-e még esélye a csapatunknak a végs® gy®zelemre. A bajnokság gy®ztese a legtöbb gy®zelemmel rendelkez® csapat (döntetlen nincs, a holtversenyes gy®zelmünket is elfogadjuk). Jelöljük a csapatokat az 0, 1, 2, ..., n számokkal, a mi csapatunk legyen a 0. Tegyük fel, hogy az i. csapat eddig w(i) darab gy®zelemmel rendelkezik, továbbá azt, hogy az i. és a j. capat még g(ij) mérk®zést játszik egymással. Nekünk az a legjobb eset, ha a csapatunk minden hátralév® mérk®zését megnyeri, tegyük fel, hogy ekkor w(max) gy®zelme lesz. A feladatunk egyenérték¶ az alábbi gráfon lév® megengedett folyamproblémával (1. ábra), hiszen, ha van megengedett folyam, akkor van egészérték¶ megengedett folyam is, ennek a jobb oldali része pedig pont egy nekünk jó kimenetelt mutat (az i-b®l (i, j)-be mutató él azt jelenti, hogy az i. csapat hány mérk®zést nyer meg a j . ellen). A másik irány hasonlóan nyilvánvaló.
4
1.2. Repül®jegyek szétosztása
5
1. ábra. Van-e még gy®zelmi esély?
1.2.
Repül®jegyek szétosztása
Van egy p kapacitású kis helyi repül®járatunk, amelyik sorban meglátogatja az 1, 2, ..., n városokat. Tegyük fel, hogy az i. városból b(ij) utas akar a j . városba
menni. A jegyek árát központilag meghatározták: i-b®l j -be f (ij)/f®. Feladatunk meghatározni, hogy a különféle jegyekb®l mennyit árusítsunk, hogy a bevételünk maximális legyen, de mindenhol betartsuk a kapacitáskorlátunkat. A probléma megfeleltethet® egy minimális költség¶ folyamfeladatnak (n = 4 esetén lásd 2. ábrát, más n-re hasonlóan). Minden (i, j) csúcsban vannak az i − j útra váró utasok, akik utaz-
nak közülük, azok a baloldali élen "mennek el" (és zetnek nekünk f (ij)-t a jegyért), a többiek a jobboldalin. A repül® az alsó vízszintes éleken halad (az itteni értékek kapacitások, míg a többi költség). Innent®l kezdve az ekvivalencia nyilvánvaló (az egészérték¶ség most is adódik).
1.3. Optimális energiapolitika meghatározása
6
2. ábra. Repül®jegyek kiosztása n = 4 esetén.
1.3.
Optimális energiapolitika meghatározása
Tegyük fel, hogy az országunk négyféle módon tud energiához jutni: k®olajból, szénb®l, uránból és vízer®m¶b®l. Az ország energiaigénye is négy részre osztható: szükség van elektromos áramra, háztartási olajra, benzinre és gázra. Minden alapanyagból képesek vagyunk bizonyos energiák el®állítására, például szénb®l tudunk elektromos áramot csinálni, azonban ez az átalakítás veszteséggel jár, amely arányos az átalakítandó mennyiséggel. Célunk, hogy mindenb®l kielégítsük az ország igényét és a lehet® legkevesebbet költsük. Jelöljük az alapanyagainkat 1, 2, 3, 4-gyel, az el®állított energia fajtákat 10 , 20 , 30 , 40 -vel. Az i. energiahordozóból a(i)-t tudunk vásárolni c(i) áron. Az i-b®l j 0 -be történ® átalakítás költsége c(ij 0 ), az átalakítandó mennyiség m(ij 0 ) része marad meg (a többi veszteség). j 0 -b®l b(j 0 ) igény van. A feladatot az
általánosított folyamproblémára vezethetjük vissza, amely azt is megengedi, hogy bizonyos (uv) éleken a folyam m(uv)-szeresére változik. A megfelel® gráf most is egyszer¶en adódik (lásd 3. ábra), c-t és b-t az ábrán jelöltük (most csak az igényeinket kell kielégíteni, felesleg maradhat!), az (S, i) éleken a(i) fels®, a (j 0 , T ) éleken b(j 0 ) alsó kapacitás van. Az (i, j 0 ) "átalakító" éleken m(ij 0 )-szeresére módosítjuk
a folyamunkat. A gráfunkon lév® minimális költség¶ folyam mutatja az optimális stratégiánkat.
1.3. Optimális energiapolitika meghatározása
3. ábra. Energiapolitika meghatározása.
7
2. fejezet
A probléma felvázolása
2.1.
A feladat meghatározása
A rákos betegek kezelésének egyik leggyakoribb módszere a sugárkezelés, különösen akkor, ha a tumor jól lokalizálható. Ebben az esetben az a célunk, hogy a sugarak elpusztítsák a rákos sejteket, de közben a létfontosságú ép sejtek ne károsodjanak. A kezelés úgy történik, hogy a betegre több (leggyakrabban 3-7) irányból párhuzamos sugárnyalábot bocsájtunk egy lineáris gyorsító nev¶ géppel (linear accelerator). Annak érdekében, hogy mindenhova a megfelel® mennyiség¶ sugárzás jusson a célterületet minden irányból kis cellákra osztjuk, majd meghatározzuk, hogy az egyes cellákra mekkora intenzitású sugárzást kívánunk bocsájtani. A megadott intenzitáseloszlás (intenzitástérkép) el®állításához egy sokleveles kollimátor (Multileaf Collimator, továbbiakban MLC) nev¶ eszköz áll rendelkezésünkre. Ez a szerkezet lényegében egy állítható sz¶r®, amely az érkez® sugarat csak bizonyos pozíciókban engedi át. A sz¶r® több (napjainkban általában 20-100) függetlenül mozgó fémnyelvpárból áll, a sugárzás csak az egymással szemben elhelyezked® nyelvek közti területen tud áthaladni (lásd 4. ábra). Az intenzitástérkép el®állításának gyakori módja az úgynevezett step-and-shoot módszer, amely statikus módon m¶ködik: el®ször beállítjuk a nyelveket, majd bekapcsoljuk a sugarat egy megadott ideig, ezután átállítjuk a nyelveket és újra sugározunk, stb. A másik el®állítási módszerrel, miszerint állandó sugárzás mellett folyamatosan mozgatjuk a nyelveket, nem foglalkozunk. Ebben a fejezetben megadjuk a problémai matemetikai leírását, 8
9
2.2. A matematikai modell
bevezetünk néhány kés®bb felhasználra kerül® de níciót, továbbá meghatározzuk, hogy milyen célfüggvényekre kívánunk optimalizálni.
4. ábra. Egy MLC. ([8])
2.2.
A matematikai modell
A feladat matematikai modellje a következ®: adott egy nemnegatív mátrixunk (általában feltehet®, hogy az értékek egészek, jelöljük I -vel és legyen M ∗ N -es, ez az intenzitás mátrix), ezt akarjuk felbontani speciális bináris mátrixok, úgynevezett sorintervallum mátrixok (szegmensek), nemnegatív lineáris kombinációjára (I =
PK
i=1 (xi
∗ Si )). Ezen Si mátrixok felelnek meg az egyes fémnyelv beállítá-
soknak (ott van 1-es, ahova eljut a sugárzás), a együtthatóik pedig azt mutatják, hogy mennyi ideig sugárzunk az adott beállítás mellett. Ez úgy is megfogalmazható, hogy minden i ∈ {1, 2, ..M }-re egy S szegmens i. sorához hozzárendelünk egy ([li , ri )) számpárt, ahol li ∈ {1, 2, 3, ..., N + 1}; ri ∈ {1, 2, 3, .., N + 1}; li ≤ ri és S(i, j) = 1 ⇔ li ≤ j < ri , különben 0. Vagyis li mutatja az i. sorban lév® baloldali
fémnyelv által az els®, még pont nem lefedett mez®t, míg ri a jobboldali fémnyelv által lefedett els® mez®t mutatja.
10
2.2. A matematikai modell
5. ábra. Az l=3, r=N-1 eset.
Példa. Egy példa a felbontásra:
4 4 3 1 6 3 3 4 1 4 4 3 3 6 4
0
1 1 0 0 1 1 0 0 = 3∗ 0 1 0 1 1 1 0 3 0 1 1
0
1 1 1 1 1 0 0 0 +1∗ 1 1 1 1 1 0 0 1 1 1 1
0
0 0 1 0 1 0 0 0 +2∗ 1 0 0 0 0 0 0 0 1 1 0
0
0 0 0 0
A nyelvek állása ezen szegmensek esetén a következ®:
6. ábra. A nyelvek elhelyezkedése a példában A másik megfogalmazás szerint, az els® szegmens esetén l1 = 1, r1 = 3, l2 = 2, r2 = 4, l3 = 2, r3 = 3, l4 = 1, r4 = 4, l5 = 2, r5 = 5.
Megjegyzés. A szegmensek és a nyelvbeállítások között nincs bijekció, hiszen a csupa nulla sort több beállítással is elérhetjük. Ez azonban nem jelent gondot a kés®bbiekben, így gyakran használjuk felcserélhet® módon ezen fogalmakat.
11
2.3. A célfüggvény
2.3.
A célfüggvény
Nyilván minden egész elemekb®l álló mátrix el®állítható legfeljebb M ∗ N darab sorintervallum mátrix lineáris kombinációjaként, hiszen az egyetlen egyesb®l és különben csupa nullákból álló mátrixok sorintervallum mátrixok, míg ezen mátrixokat megfelel® együtthatókkal beszorozva az intenzitás mátrix minden egyes eleme tetsz®legesen beállítható. Ezt nevezik triviális felbontásnak, de ez a gyakorlatban használhatatlan. Több célt is ki szoktak t¶zni annak megfelel®en, hogy milyen felbontást kívánunk elérni. A leggyakoribb cél az összsugárzási id® (
PK
i=1
xi ) minimalizálása, hiszen ekkor
kevesebb sugárzás éri az ép sejteket. A modellünkben az összsugárzási id®t a felbontásban szerepl® együtthatók összege adja, gyakran felbontási id®ként hivatkozunk majd rá (decomposition time, DT). Fontos cél lehet még a kezelés idejének minimalizálása, hiszen ekkor több beteg kezelésére kerülhet sor. A kezelési id® jól jellemezhet® a nyelvek beállításához szükséges id® és az összsugárzási id® összegével, azaz a
PK
i=1 (xi + c(Si , Si−1 ))
számmal, ahol c(Si , Si−1 ) az i. elrendezés beállításának
az ideje az i − 1-b®l (S0 a kezdeti elrendezés). Ebben az esetben gyakran fel szokták tenni, hogy a nyelvek újrakon gurálása konstans id®t vesz igénybe, így jelent®sen egyszer¶sítve a problémát. Bizonyos esetekben a felbontásszám (K , decomposition cardinality, DC) minimalizálása a cél. Mi alapvet®en a felbontási id® minimumát fogjuk vizsgálni, majd belátjuk, hogy a felbontásszám minimumának meghatározása már nagyon speciális esetben is NP-nehéz (bár vannak jól közelít® heurisztikus algoritmusok).
Példa. Az el®bbi példa esetén a felbontásszám 3, míg a felbontási id® 3+1+2 = 6. Triviális felbontásnál a felbontásszám 16 (a nulla elemekhez nem kell külön szegmens), a felbontási id® 4 + 4 + 3 + 1 + 6 + 3 + 3 + 4 + 1 + 4 + 4 + 3 + 3 + 6 + 4 + 3 = 56. Látható már ebben az esetben is, hogy a triviális felbontás lényegesen rosszabb eredményt ad, akármelyik mennyiség szerint vizsgálódunk.
3. fejezet
A standard eset
3.1.
Az eset áttekintése
Standard esetnek azt nevezzük, ha az eddigi feltételek mellett nem vezetünk be újabbakat. A legtöbb esetben sajnos kénytelenek vagyunk további feltételeket szabni, azonban a mostani modellünk is hasznos a gyakorlatban. Léteznek olyan MLC-k, amelyek beállításaiban felhasználják a standard eset eredményeit. Ez lényegesen gyorsabban kapható meg, mint például a következ® fejezetben tárgyalásra kerül® ütközésmentes eset. Ebben a fejezetben bemutatjuk, hogy létezik egy O(M N )-es algoritmus, amely megadja nekünk a minimális összsugárzási id®t. Az algoritmus visszavezeti a feladatot egy adott gráfon való minimális költség¶ folyamproblémára. Ez a fejezet els®sorban Ahuja és Hamacher [1] munkájának eredményeit mutatja be: leegyszer¶sítjük a problémát az M = 1 esetre, majd ennek megoldására megadunk egy hálózati modellt. A feladatunk a minimális összsugárzási id® meghatározása, azaz a következ® feladat megoldása: min z ∗ :=
PL
k=1
xk (1)
feltéve, hogy: I=
PL
k=1
xk Sk (1a)
Sk szegmens ∀k ∈ {1, 2, ..., L}-re (1b) xk ≥ 0 ∀k ∈ {1, 2, ..., L}-re (1c)
12
13
3.2. Egy egyszer¶sítési lehet®ség
Megjegyzés. 1) Itt feltehetjük, hogy L az összes szegmens száma, hiszen a 0 együtthatóval rendelkez® szegmensek nem változtatják meg a minimumot. 2) z ∗ -gal a feladat megoldását, vagyis a legkisebb összsugárzási id®t jelöljük a továbbiakban. 3.2.
Egy egyszer¶sítési lehet®ség
A probléma nem tartalmaz semmiféle megkötést a sorok között, ezért célszer¶ a feladatot soronként vizsgálni, majd a sorokra kapott eredményekb®l megpróbálni megkonstruálni az (egyik) optimális felbontást. Ezzel a módszerrel M egymástól független feladatot kaptunk. Egy sor esetén a feladatunk a egy adott N dimenziós vektor felbontása olyan N dimenziós 0-1 vektorok nemnegatív lineáris kombinációjára, amelyekben az egyesek egy tömbben szerepelnek. A feladatot minden sor esetén átírjuk egy irányított hálózatban lév® minimális költség¶ folyam problémává. Az így kapott hálózat meglehet®sen speciális lesz: nem lesz benne kör, de amúgy teljes lesz (ha a csúcsokat 1,2,...-tal jelöljük, akkor minden olyan (i, j) élt behúzunk, ahol i < j ); a költség függvényünk azonosan 1 lesz, míg kapacitás korlátunk semelyik élen se lesz. Be fogjuk bizonyítani, hogy ebben a speciális esetben a minimális költség¶ folyamproblémának a megoldására létezik O(N )-es algoritmus, továbbá, ha ezt mind az M sor esetében megcsináljuk, akkor ezek segítségével az eredeti feladatra adunk egy O(M N )-es algoritmust. Könnyen belátható, hogy nem létezik ennél gyorsabb algoritmus a standard eset megoldására. Az i. sor esetén a feladatunk a következ®: min zi :=
PL
k=1
xk (2)
feltéve, hogy: Ii,. =
PL
k=1
xk rk (2a)
rk egysoros szegmens vektor (továbbiakban szegmenssor) ∀k ∈ {1, 2, ..., L}-re (2b) xi ≥ 0 ∀i ∈ {1, 2, ..., L}-re (2c)
Az el®z® megjegyzés 2) pontjához hasonlóan itt is zi -vel jelöljük a kés®bbiekben a minimumot. A következ® állítás bizonyítása megmutatja, hogy hogyan kaphatjuk meg (1) megoldását úgy, hogy ismerjük minden sor esetén (2) megoldását.
14
3.2. Egy egyszer¶sítési lehet®ség
Jelölés. zmax :=max {zi : 1 ≤ i ≤ M }. Azaz zmax a sorok minimális összsugárzási idejei közül a legnagyobb.
Állítás. zmax = z ∗ . Vagyis az el®bb de niált mennyiség az I mátrix esetén a legkisebb összsugárzási id®, tehát (1) megoldása megkapható, ha minden sorára megoldjuk (2)-t, majd megkeressük ezek közül a legnagyobbat.
Bizonyítás. Nyilvánvaló, hogy (1) megoldása legalább akkora, mint bármely sor esetén (2) megoldása, hiszen ellenkez® esetben I felbontásának megfelel® sora jobb felbontást adna, mint (2), ami viszont ellentmondás, hiszen (2) a legjobb felbontást keresi. Tehát zmax ≤ z ∗ . Az egyenl®séget úgy fogjuk bizonyítani, hogy megadjuk I -nek egy olyan felbontását, ahol az összsugárzási id® éppen zmax . Legyenek ri1 , ri2 , ..., rip az i. sorhoz tartozó szegmenssorok az optimális felbontásban (p i-t®l függ). Ezekhez tartozzanak az xi1 , xi2 , ..., xip együtthatók (ekkor nyilván zi =
Pp
k=1
xk ). I egy optimális felbon-
tását egy egyszer¶ algoritmus segítségével kaphatjuk meg. Az els® lépésben minden 1 ≤ i ≤ M esetén kiválasztunk egy tetsz®leges rik1 -t, majd ezeket a szegmenssorokat összerakva megkonstruáljuk S1 -et. Ennek együtthatója legyen x1 = minxik1 : 1 ≤ i ≤ M . Ezután lecsökkentjük a kiválasztott szegmenssorok együtthatóját x1 -gyel. Amennyiben egy szegmenssor együtthatója 0 lesz (legalább egy ilyen biztosan lesz), akkor azt a szegmenssort elfelejtjük a továbbiakban. Ezután újra kiválasztunk M darab szegmenssort, ezekb®l megkonstruáljuk S2 -t, majd az el®bbihez hasonlóan megadjuk x2 -t, végül újra redukálunk. Ha egy sor esetén már nem tudunk szegmenssort kiválasztani, akkor a csupa nulla sort választjuk. Ezt addig csináljuk, amíg el nem fogy az összes szegmenssor. A kapott felbontás összege nyilván I lesz, hiszen soronként vizsgálva a (2a) feltétel biztosítja ezt számunkra. Tehát (1a) teljesül. (1b) is igaz lesz, hiszen szegmenssorokat összerakva nyilván szegmenst kapunk, míg (1c) triviális. Tegyük fel, hogy zmax = zj . Ekkor nyilván az algoritmus segítségével kapott felbontás ideje zj , hiszen az i. sor esetén a hasznos (nem azonosan nulla) szegmenssorok együtthatójának összege zi lesz (ehhez azt használjuk ki, hogy ha egy szegmenssort sugárzunk x ideig, majd y ideig, akkor az összsugárzási id® ugyanakkora lesz, mintha x + y ideig sugároztuk volna). Tehát beláttuk, hogy I -nek
15
3.3. Az egy sor esete
létezik zmax idej¶ felbontása, viszont ennél jobb nincs, tehát ez a felbontás minimuma, vagyis z ∗ = zmax .
Megjegyzés. Az optimum meghatározása a most belátott állítás segítségével elérhet® O(M N ) id®ben. Ezzel szemben az ehhez tartozó felbontáshoz már több id®re lesz szükség, ugyanis a bizonyításban szerepl® algoritmus nem fut le ennyi id® alatt. Megjegyezzük továbbá, hogy ezt a méretet számos esetben már az output (a szegmenseink) is túllépheti. 3.3.
Az egy sor esete
Tehát (1) megoldása helyett elegend® megoldani I minden sorára (2)-t, innen az el®bbi algoritmus segítségével megkaphatunk egy optimális felbontást. Mostantól tehát (2)-t próbáljuk megoldani. Az egyszer¶ség kedvéért az i indexeket elhagyjuk, valamint Ii,. helyett egy adott b vektort kell "kikevernünk" a (2a) feltételben. A jobb áttekinthet®ség miatt transzponáljuk le az egész feladatunk, tehát rk és b legyenek oszlopvektorok. Feltehet®, hogy semely k-ra nem lesz rk ≡ 0, hiszen ezeket elhagyhatjuk. Ezután minden rk -ról el lehet mondani, hogy az els® néhány koordinátája nulla, majd a következ® néhány (legalább egy) egyes, majd a maradék néhány nulla. rk -t jelöljük ruv -val, ha az els® egyes koordinátája u és az utolsóé v − 1 (u és v
megfelel az el®z® fejezetben de niált, a nyelvek állását meghatározó li és ri számoknak). Legyen A = {(u, v) : 1 ≤ u ≤ N, u + 1 ≤ v ≤ N + 1}! Nyilvánvaló, hogy |A| = n + (n − 1) + ... + 1 = n(n + 1)/2. A feladatunk tehát a következ®:
min z :=
P
(u,v)∈A
xuv (3)
feltéve, hogy: b=
P
(u,v)∈A
xuv ruv (3a)
xuv ≥ 0 ∀(u, v) ∈ A (3b)
Példa. N = 3 esetén A = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}, tehát z = x12 + x13 + x14 + x23 + x24 + x34 . A (3a) feltételt mátrixos alakban írjuk fel és
már a hálózati modellt el®készítend® beszúrunk egy csupa nulla sort is a végére:
16
3.3. Az egy sor esete
1 1 0 1 0 0 0 0
1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0
x12 x13 x14 x23 x24 x34
=
b1
b2 b3 0
Természetesen a (3b) feltételnek megfelel®en x12 , x13 , x14 , x23 , x24 , x34 ≥ 0 Más N esetén is vegyünk fel egy csupa nulla sort, majd írjuk át a (3a) feltételt úgy, hogy a mátrix minden sorából (az els® sort kivéve) kivonjuk a felette lév® sort. Ha a b vektort is ennek megfelel®en módosítjuk, akkor nyilvánvalóan egy ekvivalens LP feladatot kapunk. Jelölje b0 a módosított b vektort. A konstrukciónak köszönhet®en (miszerint az egyesek minden oszlopban egy blokkban helyezkednek el) a módosított feladat egy ruv -nak megfelel® oszlopa egy darab egyest tartalmaz az u. sorban és egy darab (-1)-est a v . sorban, míg a többi érték nulla lesz. Tehát a következ® feladatot kaptuk: min z :=
P
(u,v)∈A
xuv (4)
feltéve, hogy: b0 =
P
(u,v)∈A
0 (4a) xuv ruv
xuv ≥ 0 ∀(u, v) ∈ A (4b)
Példa. Az el®bbi példát (N = 3) folytatva a következ®t kapjuk:
1 1 1 0 0 0 −1 0 0 1 1 0 0 −1 0 −1 0 1 0 0 −1 0 −1 −1
x12 x13 x14 x23 x24 x34
b1 b2 − b1 = b3 − b2 −b3
A b ≥ 0 feltételb®l (b vektor eredetileg az I mátrix egyik sora volt, tehát nemnegatív) triviálisan következnek az alábbi észrevételek:
17
3.4. A hálózati modell
1. Észrevétel.
PN +1
2. Észrevétel.
Pj
3.4.
i=1
b0i = 0
0 i=1 bi
≥ 0 minden j ∈ {1, 2, ..., N + 1}-re
A hálózati modell
A kapott lineáris programozási feladatunk egy jól ismert példa a hálózati folyam probléma alkalmazására, például Ahuja és társai is foglalkoznak vele [5] munkájukban. Vezessük be a következ® G = (V, A) irányított gráfot: legyen V = {1, 2, ..., N + 1} a csúcshalmazunk és, mint már korábban jeleztük legyen A = {(u, v) :≤ u ≤ N, u + 1 ≤ v ≤ N + 1} az élek halmaza. Minden él költsége legyen 1, míg vala-
mennyi él kapacitása legyen ∞ (az alsó kapacitás legyen minden élen 0). A j . csúcs feleslege vagy igénye legyen b0j .
Példa. N = 3 esetén a következ® gráfot kapjuk:
7. ábra. A standard eset gráfja Ha ezen a gráfon megoldunk egy minimális költség¶ folyam problémát, akkor a (4)-gyel egy ekvivalens feladatot oldunk meg, hiszen a (4a) feltétel épp az igények és a feleslegek kiegyenlítését jelenti, míg a (4b) az alsó kapacitásoknak felel meg. A folyam költsége
P
(u,v)∈A
xuv , amely mennyiség minimumát keressük (4)-ben, tehát
a folyam probléma és (4) ekvivalens feladatok. Most pedig belátjuk, hogy a mostani minimális költség¶ folyam problémánk megoldható O(N ) lépésben. Az algoritmus hatékonysága a következ® triviális meg gyeléseken múlik:
3.4. A hálózati modell
18
3. Észrevétel. 1) A hálózatunk körmentes, de amúgy teljes lesz (minden olyan (i, j) élt behúzunk, ahol i < j )
2) c ≡ 1; u ≡ ∞ Az algoritmusunk a következ® lesz: kiindulunk az üres folyamból, majd kiválasztjuk az els® olyan csúcsot (u), ahol felesleg van (b0u > 0) és az els® olyat (v ), ahol igény van (b0v < 0). A 2. Észrevétel miatt u < v , hiszen különben j = u estén ellentmondást kapnánk. Legyen ezt követ®en xuv = min{|b0u |, |b0v |} (itt kihasználtuk a 3. észrevétel 1) pontjának második felét). Végül b0u értékét lecsökkentjük xuv -val, míg b0v értékét megnöveljük xuv -val. Ugyanezeket a lépéseket csináljuk egészen addig, amíg minden b0i nulla nem lesz. A korábban tett két meg gyelésünk a módosított b0 értékek mellett is nyilván fennáll. Az els® észrevétel miatt amíg van valahol felesleg, addig lesz valahol igény is, míg a második észrevétel miatt az els® felesleggel rendelkez® csúcs mindig megel®zi az els® igénnyel rendelkez®t, tehát az algoritmusunk nem akad el. Minden lépés után valamelyik i csúcs esetén bi nulla lesz, tehát az algoritmusunk O(N )-es lesz, hiszen a lépések konstans idej¶ek (az els® felesleget tartalmazó csúcs és az els® igénnyel rendelkez® csúcs meghatározása folyamatosan történik, azaz mindig 1-el növeljük a megfelel® indexet, amíg megfelel® b-vel rendelkez® csúcsot nem találunk, így összesen tart O(N ) ideig). Azt, hogy az algoritmusunk jó úgy bizonyítjuk, hogy ez egy speciális esete az ismert legrövidebb út algoritmusnak. Ez az algoritmus szintén az üres folyamból indul és mindig az éppen aktuális x folyamhoz tartozó G(x) gráfon dolgozik. G(x) csúcsai megegyeznek G csúcsaival és minden A-beli (i, j) élt egy c((i, j)) költség¶ és rj,i = ui,j − xi,j kapacitású (i, j) és egy −c((i, j)) költség¶ rj,i = xi,j kapacitású (j, i)
éllel helyettesítünk. Ha egy él kapacitása nulla, akkor elhagyjuk. Az algoritmus minden lépésben G(x) egy felesleggel rendelkez® csúcs és egy igénnyel rendelkez® csúcs között megkeresi a legrövidebb utat, módosítja x-et és b-t, és ezt addig csinálja, amíg b ≡ 0 nem lesz. Nyilvánvaló, hogy a mi algoritmusunk ennek egy egyszer¶bb esete.
A jobb érthet®ség miatt nézzük csak az algoritmust:
3.4. A hálózati modell
u := min{w : bw > 0}; v := min{w : bw < 0};
amíg u és v értelmes, addig δ := min{bu , −bv }; xuv := δ ; bu := bu − δ ; bv := bv + δ ;
amíg bu ≤ 0, addig u := u + 1;
amíg bv ≥ 0, addig v := v + 1;
19
4. fejezet
Az ütközésmentes eset
4.1.
Egy technikai akadály
Bár vannak MLC-k, amelyeknél hasznos az el®z® fejezetben bemutatott módszer, leggyakrabban mégis kénytelenek vagyunk további mellékfeltételeket szabni. Az MLC-k többségénél, technikai okok miatt, a szomszédos sorokban lév®, egymással szemközt elhelyezked® nyelvek nem nyúlhatnak túl egymáson. Vagyis a korábbi jelölésekkel: ∀i ∈ {2, 3, ..., M }-re li ≤ ri−1 és ∀j ∈ {1, 2, ..., M − 1}-re li ≤ ri+1 . Az ilyen beállításoknak megfelel® szegmenseket ütközésmentes szegmenseknek fogjuk hívni. Mint látni fogjuk, ez a feltétel a feladat bonyolultságát jelent®sen megnöveli. Ebben a fejezetben bemutatjuk Bolandnak és társainak [6] cikkében tárgyalt eredményét, amely két hálózati modell segítségével is megmutatja, hogy a feladat polinomiális id®ben megoldható. Az els® modell egyegyszer¶ gráfot használ számos mellékfeltétellel, míg a második modell a mellékfeltételek egyszer¶sítését, a hálózatba való beépítését célozza meg. Ebben a modellben egy hálózati folyamproblémát kapunk azzal a mellékfeltétellel, hogy bizonyos éleken a folyamértékek megegyezését követeljük meg. Az így kapott lineáris program LP-megoldóval már hatékonyan (polinomiálisan) kezelhet®. Összefogalva a következ® feladatot szeretnénk megoldani (L-re most úgy gondolhatunk, mint az összes ütközésmentes szegmens száma): min z ∗ :=
PL
k=1
xk (5)
feltéve, hogy: 20
21
4.2. Az els® modell
I=
PL
k=1
xk Sk (5a)
Sk ütközésmentes szegmens ∀k ∈ {1, 2, ..., L}-re (5b) xk ≥ 0 ∀k ∈ {1, 2, ..., L}-re (5c)
De níció. Jelölje H egy adott sorban lév® nyelvpár pozícióinak a halmazát, azaz H = {(u, v) : u ∈ {1, 2, ..N + 1}, v ∈ {u, u + 1, ..., N + 1}}. Emlékeztetésül meg-
jegyezném, hogy az el®z® fejezetben de niált A halmaz nem engedte meg az u = v esetet, vagyis a csupa nulla sort.
4.2.
Az els® modell
Vezessük be a következ® G = (V, A) gráfot: legyen V = {(i, l, r) : i ∈ {1, 2, .., M }, (l, r) ∈ H} ∪ {S, T }
Egy rögzített (i0 , l0 , r0 ) csúcs annak felel majd meg, hogy az i0 . sorban a baloldali nyelv az l0 pozícióban van, míg a jobboldali az r0 -ban. A gráfot úgy képzeljük el, hogy M szintje van, minden szinten az adott sorhoz tartozó csúcsok helyezkednek el, míg a 0. szinten az S és az M +1. szinten a T mesterséges csúcs van. Két csúcs között akkor húzunk be élt, ha szomszédos szinten vannak és a nekik megfelel® beállítások nem ütköznek. Ezen kívül összekötjük még S -et az összes 1. szinten lév® csúccsal és az összes M . szinten lév® csúcsot összekötjük T -vel, valamint behúzzuk a (T, S) élt. Ez utóbbi kivételével minden élt lefele irányítunk, azaz a magasabb szint¶ csúcs fele mutatnak. Összefoglalva (lásd 8. ábra): A = {((i, j, r), (i + 1, l0 , r0 )) : i ∈ {1, 2, ..., M − 1}, l ≤ r0 , l0 ≤ r}∪ ∪{(S, (1, l, r)) : (l, r) ∈ H} ∪ {((M, l, r), T ) : (l, r) ∈ H} ∪ {(T, S)}
Vegyük észre a következ® két nyilvánvaló állítást:
1. Észrevétel. A G gráf a (T, S) élt elhagyva körmentes, vagyis minden kör átmegy a (T, S) élen.
22
4.2. Az els® modell
2. Észrevétel. Minden G-beli kör megfelel egy ütközésmentes szegmensnek és minden ütközésmentes szegmens megfelel egy G-beli körnek.
Példa. M = 4, N = 2 esetén a gráfunk a következ® (az éleknek csak egy része van berajzolva, színessel két adott szegmenshez tartozó kört láthatunk):
8. ábra. Az M = 4, N = 2 eset. A két színessel jelölt kör az alábbi szegmenseknek felel meg (az els® a piros, a második a kék):
1 0 1 1 , 0 1 0 0
0 0
1 1 1 0 1 0
Mivel minden ütközésmentes szegmens megfelel egy körnek, ezért egy adott felbontásban szerepl® minden ütközésmentes szegmensnek megfeleltethetünk egy
23
4.3. A második modell
folyamot oly módon, hogy a neki megfelel® kör éleinek a folyamértéke az ® együtthatója legyen. Ha egy felbontás esetén ezeket a folyamokat összeadjuk (élenként), akkor minden felbontásnak megfeleltettünk egy folyamot.
Példa. Tekintsük az alábbi felbontást:
1 0
0 0
2 0
1 1 5 5 1 1 2∗ = +3∗ 1 0 3 2 0 1 3 0 1 0 0 0
Ekkor a következ® folyamot kapjuk: a piros éleken xe = 2 , a kékeken xe = 3, xT S = 5, míg a többi élen x ≡ 0.
Az 1. Észrevétel miatt egy felbontásnak megfelel® folyamban a felbontás ideje épp a (T, S) él folyamértéke lesz. Ez adja nekünk a következ® ötletet: vezessünk be egy költségfüggvényt úgy, hogy cT S = 1, míg különben c ≡ 0. Ezáltal egy folyam költsége épp a (T, S) él költsége lesz, vagyis ahhoz, hogy a feladatunk egy minimális folyamprobléma legyen, már csak az (5a) feltételt kell garantálnunk. Ezt az els® modellben a következ® mellékfeltétellel biztosítjuk: Pj
l=1
PN +1 P r=j+1
e∈A− (i,l,r)
xe = Iij (6) ∀i ∈ {1, 2, ..., M }, ∀j ∈ {1, 2, ..., N }
Emlékeztetésül: A− (i, l, r) az (i, l, r) csúcsba befutó élek halmazát jelöli. A hálózati folyamproblémánk a (6) mellékfeltétellel egy lineáris programozási formulát adnak nekünk, amely segítségével már megkereshetjük az optimális felbontást. A formulában a változók és a feltételek száma polinomiális, így jó algoritmushoz jutottunk. Ezt követ®en érdemes a modellünket átalakítani úgy, hogy minél közelebb kerüljünk egy egyszer¶ folyamproblémához. 4.3.
A második modell
Célunk elérésének érdekében szükség lesz a mátrix mez®it jelképez® élekre, melyeken a folyamértéket pontosan meg kívánjuk szabni, vagyis ezen éleken az alsó és a fels®
24
4.3. A második modell
korlátot is Iij -re állítjuk be. Minden szegmensbeállítás egyértelm¶en meghatározza, hogy mely mez®k kapnak sugárzást, így az ezeken a csúcsokon áthaladó folyamértékekb®l állítjuk össze a megfelel® értékeket. Legyen G0 = (V 0 , A0 ) gráf az alábbi: V 0 := {(i, l, r)1 , (i, l, r)2 : (i, l, r) ∈ V }∪ ∪{(i, j) : i ∈ {1, 2, ..., M }, j ∈ {1, 2, ..., N + 1}} ∪ {S, T } A0 := Aeddigi ∪ Abe ∪ Aki ∪ Aint
Aeddigi := {((i, l, r)2 , (i + 1, l0 , r0 )) : i ∈ {1, 2, ..., M − 1}, l ≤ r0 , l0 ≤ r}∪ ∪{(T, S)} ∪ {(S, (1, l, r)1 ) : (l, r) ∈ H} ∪ {((M, l, r)2 , T ) : (l, r) ∈ H} ∪ {(T, S)} Abe := {((i, l, r)1 , (i, l)) : (i, l, r)1 ∈ V 0 )} Aki := {((i, r), (i, l, r)2 ) : (i, l, r)2 ∈ V 0 )} Aint := {((i, j), (i, j + 1) : i ∈ {1, 2, ...M }, j ∈ {1, 2, ..., N })}
Az intenzitás éleken (utolsó halmaz) fels® és az alsó kapacitás is bevezetünk: ∀e = ((i, j), (i, j + 1)) ∈ Aint : u(e) = l(e) = Ii,j . A többi élre l(e) = 0, u(e) = ∞. c továbbra is csak a (T, S) élen 1, különben 0. Nézzük meg, hogy változott meg a
korábbi modellünk! A korábbi csúcsokat kettévágtuk és a keletkezett két új csúcs között átvezetjük a rajtuk átmen® folyamot azokon az éleken, amelyek azoknak a mez®knek felelnek meg, melyeket sugárzás ér. Ezeken az éleken már beállíthatjuk a kívánt értékeket a kapacitásokkal. Azonban az intenzitás éleken több beállításhoz tartozó kör is keresztülmegy, így ezek összekeveredését csak mellékfeltétellel tudjuk elkerülni: x((i, l, r)1 , (i, l)) = x((i, r), (i, l, r)2 ) (7) ∀(i, l, r) ∈ V
A hálózaton a fenti mellékfeltétellel kell minimális költség¶ folyamot keresnünk. Nyilvánvaló, hogy |V 0 | = O(M N 2 ) és |A0 | = O(M N 4 ) (minden szinten O(N 2 ) csúcs van és két szint közötti O(N 2 ) él a domináns tag), tehát polinomiális algoritmussal megkereshet® a legolcsóbb folyam, vagyis polinomiális id®ben megkaphatjuk a minimális összsugárzási id®t és a hozzá tartozó felbontást.
4.3. A második modell
25
Megjegyzés. A mellékfeltétel miatt a modell nem biztosítja az egészérték¶séget. Erre valójában nincs is szükség, hiszen a sugárzási id®t nagy pontossággal be tudjuk állítani. Kombinatorikus algoritmusokkal ez az eredmény is elérhet®, vázlatosan bemutatjuk ezt is az utolsó fejezetben.
Példa. A korábbi példa a kiterjesztett gráfon (az éleknek csak egy része van behúzva; ahol a két kör megegyezik, azokat az éleket lilával jelöltük, továbbá a szemléletesség miatt a kettévágott csúcsokat színeztük az indexelés helyett):
26
4.3. A második modell
9. ábra. A kib®vített gráf.
5. fejezet
Egy újabb feltétel
5.1.
A nyúlvány-és-horony kialakítás
A szomszédos sorokban elhelyezked® nyelvek között mindig van egy kis rés, ezért az ilyen jelleg¶ hibák minimalizálása miatt a nyelvek oldala speciális, úgynevezett nyúlvány-és-horony (tongue-and-groove, továbbiakban TG) kialakítású. Ez a kialakítás segíti az érintkez® nyelvek közti sugárárnyékolást, azonban ha egy élnek csak az egyik oldalán van nyelv, akkor ezen a részen különféle hibák (alul- vagy túlsugárzás) lépnek fel. Ebben a fejezetben a korábbi feltétel (ütközésmentesség) megtartása mellett úgy keressük a minimális összsugárzási id®t, hogy a TG hiba minimális legyen. A problémával [5]-ben találkozhatunk, most azonban az el®z® fejezetben bemutatott modelleket fogjuk úgy módosítani, hogy az újabb feltételnek is megfeleljünk.
De níció. Egy A = (aij )i∈{1,2,...,M },j∈{1,2,...,N } (nemnegatív) mátrix TG-hibája a következ®: T G(A) =
M −1 X N X
|aij − ai+1,j |
i=1 j=1
De níció. Azt mondjuk, hogy két M ∗ N -es mátrix (A és B) kompatibilis pro lú, ha minden i ∈ {1, 2, ..., M − 1} és j ∈ {1, 2, ..., N } esetén teljesül a következ® két állítás: 1) aij ≤ ai+1,j esetén bij ≤ bi+1,j 27
28
5.1. A nyúlvány-és-horony kialakítás
2) aij ≥ ai+1,j esetén bij ≥ bi+1,j Az alábbi két észrevétel triviális módon adódik a de níciókból:
1. Észrevétel. T G(cA) = cT G(A) (c tetsz®leges valós) 2. Észrevétel. T G(A + B) ≤ T G(A) + T G(B) és egyenl®ség akkor és csak akkor van, ha A és B kompatibilis pro lú.
De níció. Egy I =
PL
k=1
xk Sk (nemnegatív) felbontás TG-hibája:
T G({xk }, {Sk }) =
L X
xk T G(Sk )
k=1
Állítás. Legyen I =
PL
k=1
xk Sk , ahol minden változó nemnegatív. Ekkor: T G(I) ≤ T G({xk }, {Sk })
és egyenl®ség akkor és csak akkor van, ha minden Sk azonos pro lú I -vel.
Bizonyítás. A két Észrevétel többszöri alkalmazásával az állítás nyilvánvaló. Meghatároztuk tehát, hogy milyen szegmensek szerepelhetnek a felbontásban, ha a TG-hibát minimális szinten kívánjuk tartani. Jelöljük az I -vel kompatibilis pro lú, ütközésmentes szegmensek halmazát U (I)-vel. A feladatunk tehát a következ®: min z ∗ :=
PL
k=1
xk (8)
feltéve, hogy: I=
PL
k=1
xk Sk (8a)
Sk ∈ U (I) ∀k ∈ {1, 2, ..., L}-re (8b) xk ≥ 0 ∀k ∈ {1, 2, ..., L}-re (8c)
Bárász Mihály cikkében ([5]) egyrészt átfogalmazza a feladatot egy lineáris programozási feladattá, amely biztosít egy hatékony algoritmust, másrészt mutat egy kombinatorikus algoritmust, amely lineáris id®ben megadja az optimális összsugárzási
5.2. A minimális TG-hiba modellezése
29
id®t (lásd az utolsó fejezetben), igaz felbontást nem mutat hozzá (mint a 3. fejezetben említettük, rossz esetben már az output mérete is túl nagy lehet, így nem is létezhet lineáris algoritmus). Ennek az eredménynek els®sorban elméleti jelent®sége van, hiszen különféle heurisztikus algoritmusok eredményességét lehet gyorsan meghatározni. A kombinatorikus algoritmus biztosítja az egészérték¶séget is, ellentétben az el®z® fejezet most bemutatásra kerül® modelljének módosított verziójával. Látható tehát, hogy nem mindig érdemes feltétlenül ezt a módszert követni, bizonyos esetekben más algoritmusok a célravezet®bbek.
5.2.
A minimális TG-hiba modellezése
Az el®z® fejezetben bemutatott modellek szinte teljesen megfelelnek a mostani feladat ábrázolásához, csupán néhány élt kell elhagynunk, hogy a nem I -kanonikus szegmensek ne fordulhassanak el® a felbontásban. Pontosabban fogalmazva az el®z® fejezet els® modelljében szerepl® A els® részében szerepl® feltétel a következ®kkel (9) egészítend® ki: 1) (l < l0 ) ⇒ ∀j ∈ [l, l0 ) : Iij ≥ Ii+1,j (9a) 2) (l > l0 ) ⇒ ∀j ∈ [l0 , l) : Iij ≤ Ii+1,j (9b) 3) (r < r0 ) ⇒ ∀j ∈ [r, r0 ) : Iij ≤ Ii+1,j (9c) 4) (r > r0 ) ⇒ ∀j ∈ [r0 , r) : Iij ≥ Ii+1,j (9d) Vagyis egy I intenzitásmátrix minimális TG-hibájú ütközésmentes felbontásai közül a minimális összsugárzási id®t adót meghatározásához a következ® G = (V, A) gráfon kell a minimális költség¶ folyamot keresni a (6) mellékfeltétel mellett: V = {(i, l, r) : i ∈ {1, 2, .., M }, (l, r) ∈ H} ∪ {S, T } A = {((i, j, r), (i + 1, l0 , r0 )) : i ∈ {1, 2, ..., M − 1}, l ≤ r0 , l0 ≤ r, (9)}∪ ∪{(S, (1, l, r)) : (l, r) ∈ H} ∪ {((M, l, r), T ) : (l, r) ∈ H} ∪ {(T, S)}
30
5.2. A minimális TG-hiba modellezése
Példa. M = 2, N = 3 esetén, ha I=
1 5 2 2 3 4
akkor:
10. ábra. A minimális TG-hiba esete. Természetesen ezt a modellt is átalakíthatjuk a korábbihoz hasonló módon. Ebben a modellben egyedül Aeddigi -t kell értelemszer¶en módosítani a (9) feltétel segítségével, az így kapott modellben már csak (7) lesz mellékfeltételként.
6. fejezet
A minimális felbontásszám
6.1.
Burkard tétele kétsoros mátrixra
Ebben a fejezetben nem a felbontási id®t fogjuk vizsgálni, hanem a felbontásszámot. A problémára 2002-ben adott választ Burkard [6] cikkében, mégpedig negatívat. Az alábbi tétel belátásával bizonyította, hogy a minimális szegmensszámú felbontás meghatározása NP-nehéz:
Tétel (Burkard). Legyen a1 , a2 , ..., an adott. Ekkor az alábbi A mátrixnak akkor és csak akkor van felbontása n szegmens nemnegatív kombinációjára, ha létezik az {1, 2, ..., n} számoknak olyan {i1 , i2 , ..., ik } részhalmaza, amelyre ai1 +ai2 +...+ain = M.
A=
a1
0
a2
0
a3
... an
M M M M M M M
Megjegyzés. Az utóbbi probléma ismert NP-nehéz feladat. 6.2.
Baatar tétele egysoros mátrixra
2005-ben Baatar és társai [4]-ben a következ® tétellel belátták, hogy már egysoros mátrixok esetén is NP-nehéz a feladat:
31
32
6.2. Baatar tétele egysoros mátrixra
Tétel. Tekintsük az alábbi két problémát: Felbontásszám probléma (DC) Adott: A = (a1 , a2 , ..., aN ), K pozitív egész szám. Kérdés: létezik-e I -nak felbontása legfeljebb K darab szegmensre.
Hármas particionálás (Three Partitioning, 3-PART) Adott: B, Q, b1 , b2 , ..., b3Q pozitív egész számok, melyekre
P3Q
j=1 bj
= QB és min-
den j -re B/4 < bj < B/2. Kérdés: létezik-e a {b1 , ..., b3Q } számoknak felosztása T1 , T2 , ..., TQ hármasokra, hogy
P
b∈Tq
b = B minden q ∈ {1, 2, ..., Q}-ra.
Legyen: 1) N := 4Q 2) ha n ≤ 3Q, akkor an :=
Pn
j=1 bj
, különben an := (4Q − n + 1)B
3) K := 3Q Állítás: A két problémára ugyanakkor lesz igen a válasz.
Megjegyzés. A hármas particionálás ismert NP-nehéz feladat. Bizonyítás. Ha a 3-PART-ra igen a válasz, akkor a következ® felbontása lesz Anak: ha bj ∈ Tq , akkor Sj esetén legyen l = j, r = 3Q + q + 1 (most csak egy sorunk van). xj pedig legyen bj . Nyilván K darab szegmensünk lesz és könnyen ellen®rizhet®, hogy el®állítottuk A-t, tehát az egyik iránnyal készen vagyunk. Mivel A els® 3Q eleme monoton növ®, ezért A felbontásában biztosan pontosan K darab szegmens van. Jelöljük a Sq -t intervallumként: Iq = [lq , rq ) (lq és rq l-
nek és r-nek felel meg az Sq szegmens esetén). Vegyünk A-nek azt a {Iq , xq }, q ∈ {1, 2, ..., 3Q} (K elem¶) felbontását, amelyre az intervallumok összhossza maximális.
Az általánosság rovása nélkül feltehetjük, hogy lq = q (az els® 3Q mez® mindegyikében kell kezd®dnie intervallumnak). Figyeljük meg az alábbiakat: 1) Ebben a felbontásban semely p, q ∈ {1, 2, .., 3Q}-ra nem lesz lq = rp , mert különben Ip és Iq helyett vehetnénk Ip ∪ Iq -t min{xp , xq } együtthatóval és Ip -t vagy Iq -t a maradék együtthatóval, így n®ne az intervallumok összhossza.
2) rq > 3Q∀q ∈ {1, 2, .., 3Q}, mivel az els® 3Q mez® mindegyikéb®l indul intervallum, de 1) miatt ezekben a mez®kben nem lehet vége intervallumnak.
6.2. Baatar tétele egysoros mátrixra
33
3) rq 6= 3Q + 1∀q ∈ {1, 2, .., 3Q}, mert a3Q = a3Q+1 , tehát valamelyik intervallumnak kéne kezd®dnie 3Q + 1-ben is, hogy kiegyenlítsük a két mez®t, de ez nem lehet. 4) Az eddigiek miatt minden intervallum vége (rq ) a {3Q + 2, 3Q + 3, ..., 4Q + 1} halmazban van. Legyen bj ∈ Tq ⇔ rj = 3Q+j +1. A de níciója mutatja, hogy jól particionáltunk (az elemek B -esével csökkennek az utolsó Q mez®n), tehát beláttuk a másik irányt is.
Megjegyzés. Bizonyos speciális alakú mátrixokra (például bináris mátrixokra és konstansszorosaikra) ismert polinomiális algoritmus. Ennek azonban csak elméleti jelent®sége van, a gyakorlatban jól közelít®, heurisztikus algoritmusokat használnak. Egy ilyen algoritmus megtalálható például [4]-ben.
7. fejezet
Az egészérték¶ség problémája
Az utolsó fejezetben felvázoljuk a kombinatorikus módszert, amely biztosítja számunkra az egészérték¶séget is. Mint már említettük erre a gyakorlatban nincs szükség, azonban számos esetben (például a minimális felbontásszám közelítésére) kombinatorikus módszert használnak, továbbá így hasonló problémák megoldásához is jól hasznosítható algoritmust kapunk. Ebben a részben [4] és [5] segítségével bemutatjuk, hogyan biztosítható az egészérték¶ség az ütközésmentes, illetve a minimális TG-hibájú esetben. Ez a fejezet csak egy vázlatot ad, részletes bizonyítások és a kombinatorikus módszer további felhasználásai a fenti forrásokban találhatóak.
7.1.
A kanonikus felbontás
De níció. Egy S szegmens esetén legyen L(S) egy olyan M ∗ (N + 1)-es mátrix, amelyben minden i ∈ {1, 2, ..., M } esetén, az i. sorban pontosan az li . mez®ben van egyes, különben minden eleme nulla. Egy {ck , Sk } felbontás esetén legyen L := P
ck ∗L(Sk ), amelyre baloldali végpontok mátrixaként fogunk hivatkozni. Hasonlóan
de niáljuk az R mátrixot is (jobboldali végpontok mátrixa).
Észrevétel. Könnyen látszik, hogy L és R minden sorösszege megfelel a felbontás idejének.
De níció. Tetsz®leges M ∗ N -es I mátrix esetén legyen I d azaz M ∗ (N + 1)-es mátrix, amire Iijd = Ii1 , ha j = 1; Iij − Ii,j−1 , ha j ∈ {2, 3, ..., N }; és −IiN , ha 34
35
7.1. A kanonikus felbontás
j = N + 1.
Észrevétel. Nyilvánvaló, hogy L − R = I d . A következ® tétel segítségével jól jellemezhetjük az L és R mátrixokat:
1. Tétel. L és R pontosan akkor tartoznak I egy ütközésmentes felbontásához, ha L − R = I d és minden i = 1, ..., M − 1-re és t = 1, ..., N -re (i) t X j=1
és (ii)
t X j=1
lij ≥
t X
ri+1,j
j=1
li+1,j ≥
t X
ri,j
j=1
Egy a fenti feltételekkel adott L és R mátrixpár több különböz® felbontáshoz is tartozhat (de ezek ideje ugyanakkora), mi azonban kiemelünk közülük egyet, így megfeleltetjük a speciális felbontásokat és a mátrixpárokat egymásnak. Mostantól tehát elég lesz L és R mátrixokat meghatározni.
De níció. Egy {[xk , yk ]} intervallumrendszer kanonikus, ha nincs két olyan intervalluma, hogy az egyik szigorúan tartalmazza a másikat. Egy szegmensrendszer kanonikus, ha minden sorára megszorítva kanonikus intervallumrendszert kapunk (egy szegmens sora alatt az [li , ri ) intervallumot értjük). Egy ({ck }, {Sk }) felbontás kanonikus, ha a szegmensei kanonikus rendszert alkotnak. L és R segítségével könnyedén megkaphatjuk azt a hozzátartozó kanonikus fel-
bontást, amelyben nincsenek nulla együtthatójú szegmensek és amelyben semely szegmens nem szerepel kétszer. Az algoritmusból könnyen látszik, hogy amennyiben L és R elemei egészek, abban az esetben minden részeredmény, így a ck együtt-
hatók is egészek lesznek, tehát a kés®bbiekben csak L és R egészérték¶ségével kell foglalkoznunk:
36
7.2. Kanonikus felbontás minimális TG-hiba esetén
k := 1
amíg L 6= 0 Minden i-re legyen αil az L i. sorának els® nem 0 eleme és li ennek az indexe. Hasonlóan de niáljuk R mátrix esetén az αir és az ri változókat. l r Sk := ([li , ri )), ck := min{α1l , ..., αM , α1r , ..., αM }
L i. sorának li . eleméb®l kivonunk ck -t, R-re hasonlóan. k := k + 1
7.2.
Kanonikus felbontás minimális TG-hiba esetén
Ha a TG-hibát is minimalizálni szeretnénk, akkor hasonlóan kell eljárnunk. Az alábbi tétel megmutatja, hogy ezt megtehetjük:
2. Tétel. A minimális felbontási idej¶ I -kompatibilis (minimális TG-hibájú) felbontások között van kanonikus.
Bizonyítás (vázlat). Megmutatjuk, hogy minden felbontáshoz létezik egy kanonikus felbontás is ugyanakkora felbontási id®vel. Ha a felbontásunkban van két szegmens (S és S 0 ) melyek nem kanonikusak (azaz van olyan soruk, ahol li < li0 ≤ ri0 < ri , vagy fordítva), akkor ezt a két szegmenst ki tudjuk úgy cserélni
(legfeljebb) három szegmensre, hogy a sorokat kicseréljük a [min(li , li0 ), min(ri , ri0 )), [max(li , li0 ), max(ri , ri0 )) sorokra (értsd: ezekben az intervallumukban lesznek egye-
sek) és a nagyobb együtthatóval rendelkez® szegmens i. sorára. Az így kapott három szegmens már I -kompatibilis lesz (ez egyszer¶ esetvizsgálattal adódik), továbbá az együtthatók könnyedén beállíthatóak úgy, hogy minden feltételt kielégítsünk. Amíg van a kanonikusságot sért® szegmenspár, addig folyamatosan cserélünk. Az eljárásunk során (feltéve, hogy I egész együtthatós) a
P
k ck
PM i
(rk,i −lk,i )2 kifejezés min-
den lépésben legalább eggyel csökken, így véges algoritmust kaptunk, tehát készen vagyunk (rk,i illetve lk,i az Sk szegmens esetén jelöli ri -t, illetve li -t). A fejezet els® tételéhez hasonló tételt kaphatunk a minimális TG-hibájú esetben
37
7.3. Az optimális felbontás meghatározása
is:
3. Tétel. L és R pontosan akkor tartoznak I egy minimális TG-hibájú ütközésmentes felbontásához, ha L − R = I d és minden i = 1, ..., M − 1-re és t = 1, ..., N -re (i)
t X
lij ≥
j=1
és (ii)
t X
t X
ri+1,j
j=1
li+1,j ≥
j=1
t X
ri,j
j=1
ha Ii,t ≤ Ii+1,t , akkor (iii) t X
és (iv)
lij ≤
t X
j=1
j=1
t X
t X
rij ≥
j=1
j=1
t X
t X
li+1,j
ri+1,j
ha pedig Ii,t ≥ Ii+1,t , akkor (v)
és (vi)
j=1
t X
t X
j=1
7.3.
lij ≥
j=1
rij ≤
li+1,j
ri+1,j
j=1
Az optimális felbontás meghatározása
A fejezet korábbi részein már beláttuk, hogy egy optimális megoldás el®állításához elegend® meghatározni az L és R mátrixokat. Ezek ismeretében a kanonikus felbontás algoritmusa már biztosít számunkra egy optimális felbontást. Azt is beláttuk, hogy az együtthatók egészérték¶ségét L és R egészérték¶sége biztosítja. Ebben a részben egy O(M N )-es algoritmussal el®állítjuk L-t és R-t, továbbá belátjuk, hogy mindkett® elemei egészek lesznek.
38
7.3. Az optimális felbontás meghatározása
Fogalmazzuk át a problémát: az, hogy L és R nemnegatív, továbbá L − R = I d pont annak felel meg, hogy egy nemnegatív W -re L = I+d + W és R = I−d + W (I+d és I−d I d pozitív és negatív része koordinátánként). Ez a meg gyelés koordinátánként
nézve triviális. Tehát elegend® W -t meghatározni. Könnyen belátható, hogy az L és R mátrixok jellemzésére használt 1. illetve 3. tétel feltételei mind átírhatóak W segítségével. Például (i) esetén a következ®t kapjuk:
t X
(wij − wi+1,j ) ≥
j=1
t X d ((Ii+1,j )− − (Iijd )+ ) j=1
A többi feltétel is átírható hasonló alakra, így a következ® feladatot kell megoldanunk (a felbontás ideje megegyezik L és R tetsz®leges sorának összegével, amely akkor minimális, ha W tetsz®leges sorösszege minimális):
min
PM +1 j=1
w1j (10)
feltéve, hogy: dit ≤
Pt
j=1 (wij
− wi+1,j ) ≤ eit
Minden i ∈ {1, 2, ...M − 1}-re t ∈ {1, 2, ..., N + 1}-re (10a) W ≥ 0 (10b)
A (10a) feltételben dit és eit rögzített I -t®l függ® számok (ütközésmentes esetben (i) és (ii) segítségével kaphatóak meg, míg minimális TG-hiba esetén (i)-(vi) segítségével). A következ® lemma azt mutatja meg, hogy az optimális W -t megkaphatjuk úgy, hogy oszloponként határozzuk meg:
1. Lemma. Ha W (10) egy megengedett megoldása, ennek k. oszlopa wk , és w' egy olyan nemnegatív M dimenziós oszlopvektor, amely koordinátánként kisebb wk -nál és dik ≤
k−1 X
0 (wij − wi+1,j ) + wi0 − wi+1 ≤ eik
j=1
akkor W k. oszlopát w'-re, k + 1-et wk+1 − w' + wk -ra cserélve szintén megengedett megoldást kapunk ugyanakkora célfüggvénnyel.
39
7.3. Az optimális felbontás meghatározása
Bizonyítás. Egyedül t = k feltétel esetén változnak (10a)-ban a feltételek, de ennek fennállását a lemma feltétele biztosítja. (10b) és a célfüggvény változatlansága triviális. A lemma miatt W -t meghatározhatjuk oszloponként, ha minden sorban a minimális értéket írjuk be (hamarosan látni fogjuk, hogy ezt megtehetjük). Tehát, ha az els® k − 1 oszlop ismert, akkor a következ® feladat megoldásával kapjuk wk -t: 0 ) (11) min (w10 , ...wM
feltéve, hogy: 0 wi+1 − wi0 ≤
Pk−1
− wi+1,j ) − dit (11a)
0 − wi0 ≥ wi+1
Pk−1
− wi+1,j ) − eit (11b)
j=1 (wij j=1 (wij
wi0 ≥ 0 (11c) ∀i ∈ {1, 2, ..., M − 1}
(11)-ben a minimumot úgy értjük, hogy minden koordinátájában kisebb egyenl®, mint bármely más megengedett megoldás megfelel® koordinátája. Ha találunk (11)nek megoldását és W k. oszlopának ezt véve minden k-ra jó megoldáshoz jutunk, hiszen semelyik koordinátáját nem tudjuk tovább csökkenteni, így a sorösszeg minimális lesz. A feladatunkat kicsit általánosabban fogalmazva a következ®t kell megoldanunk: min (x1 , ...xM ) (12) feltéve, hogy: xi+1 − xi ≤ fi (12a) xi+1 − xi ≥ gi (12b) xi ≥ 0 (12c) ∀i ∈ {1, 2, ..., M − 1}
A következ® lemma biztosítja, hogy lesz koordinátánként minimális megoldásunk:
2. Lemma. Ha x és x0 két megoldása (12)-nek, akkor a koordinátánként vett minimumuk is megoldása lesz (12)-nek.
7.3. Az optimális felbontás meghatározása
40
Bizonyítás. Tekintsük (12a)-t egy tetsz®leges i esetén. Feltehetjük, hogy xi ≤ x0i . Ekkor min{xi+1 , x0i+1 } ≤ xi+1 ≤ xi + fi = min{xi , x0i } + fi . (12b) hasonlóan kapható meg, míg (12c) triviális. A következ® vázlatos algoritmus el®állítja nekünk az optimális x vektort. Az algoritmus három részb®l fog állni. El®ször egy (12b)-t kielégít® megoldást adunk: x1 = 0, xi =
Pi−1 l=1
gl , ha i > 1. Ezután az egész sorozatot megemeljük úgy, hogy a
legkisebb eleme 0 legyen (így kielégítjük (12c)-t), az els® 0 el®tti elem indexe legyen k . Végül amíg k ≥ 1, addig az x1 , ..., xk kezd®szeletet eltoljuk lefele annyival, hogy
a feltételeink ((12a) és (12c)) ne sérüljenek. Ha (12a) miatt állunk meg, akkor k-t eggyel csökkentjük, különben a nullává vált elem elé állítjuk. A feltételek fennállása némi esetvizsgálat után könnyen adódik, míg az optimalitás valamivel bonyolultabban indukcióval jön ki. Nyilvánvaló, hogy ha az elején minden egész volt, akkor a végén is minden az maradt, így W egész együtthatós lesz, ezért L és R is, vagyis a felbontás együtthatói is. Érdemes megjegyezni továbbá, hogy a módszer O(M N ) id®ben adja meg az optimális felbontás idejét (vagyis például L egy sorának összegét), tehát a módszer ilyen téren is optimális.
Irodalomjegyzék
[1] R. K. Ahuja, H. W. Hamacher, A Network Flow Algorithm to Minimize Beam-
On Time for Unconstrained Multileaf Collimator Problems in Cancer Radiation Therapy, Networks (2005), 36-41. [2] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network ows: Theory, algorithms,
and applications, Prentice-Hall, Englewood Clis, NJ (1993) [3] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, M. R. Reddy: Applications of Network
Optimalization in: Network models (M. O. Ball, T. L. Magnanti, C. L. Monma, G. L. Nemhauser), Elsevier (1995) [4] D. Baatar, H. W. Hamacher, M. Ehrgott, G. J. Woeginger, Decomposition of in-
teger matrices and multileaf collimator sequencing, Research Report, Department of Mathematics, University of Kaiserslautern, Germany (2004) [5] Bárász M., Egy daganatos betegségek sugárkezelésénél felmerül® optimalizációs
probléma vizsgálata, Publikálatlan kézirat (2006) [6] N. Boland, H. W. Hamacher, F. Lenzen, Minimizing Beam-On Time in Cancer
Radiation Treatment Using Multileaf Collimator, Networks 43 (2004) 226-240. [7] R. E. Burkard, Open research question section of Oberwolfach conference, (2002) [8] http://varian.mediaroom.com
41
