Mathematics | Studies, essays, thesises » Szilárd András - A hozzárendelési feladat szemléltetése Java nyelven

A Hozzárendelési feladat szemléltetése Java programozási nyelven szakdolgozat Szilárd András III. programozó matematikus Dr. Csendes Tibor témavezet® Szegedi Tudományegyetem, Természettudományi Kar, Alkalmazott Informatikai Tanszék Szeged 2004 Feladatkiírás A Hozzárendelési feladat az operációkutatás egyik fontos alapfeladata, megoldására a többi között az ún. Magyar módszer is jól alkalmazható Jelenleg a szegedi programozó szakokon több kurzus anyagának is részét képezi a probléma. (Operációkutatás I, Kombinatorikus optimalizálás) Ezért hasznos lenne egy olyan program, amellyel ellen®rizni lehet a megoldandó feladatokat. Jelen szakdolgozat f® célkit¶zése, hogy a hallgató egy általa választott programozási nyelven, implementáljon egy olyan számítógépes programot, amely helyesen megoldja az ún. Hozzárendelési feladatot A megoldás menete támaszkodjon a Magyar módszer néven ismert eljárásra A program alapvet®

feladata az, hogy helyesen oldja meg a futási id®ben megadott, tetsz®leges hozzárendelési feladatokat. A további funkciók közé tartozik az, hogy legalább két üzemmódban legyen képes a feladatok megoldását végezni: egyikben részletes üzeneteket kell generálnia az eljárás során, míg a másikban elegend® a végeredményt bemutatnia. A részletes, magyarázó szöveges üzenetek megjelenítésével egyid®ben, vizuális szemléltetést is megkívánunk a programtól, oktatási szempontok gyelembe vételével i Tartalmi összefoglaló Szakdolgozatom kit¶zött témája a Hozzárendelési feladat, Magyar módszerrel történ® megoldásának szemléltetése volt, tetsz®legesen választott programozási nyelven. A feladatot sikerrel oldottam meg Java programozási nyelven, s®t a nyilvánvaló kívánalmakon túl további el®nyös szempontokat is gyelembe vettem már a tervezés során. Dolgozatomban el®ször ismertetem a Hozzárendelési feladatot egy

egyszer¶ példán keresztül, majd bemutatom az operációkutatásból ismert matematikai modelljét. Ezután részletesen tárgyalom a  probléma hatékony megoldására szolgáló  Magyar módszert. A dolgozat érdemi részét a számítógépes megoldáshoz felhasznált ötletek, technikák, módszerek alkotják. Ennek els® fejezetében röviden ismertetem a Java nyelvet, amelyet a megoldáshoz alkalmaztam. Majd röviden kitérek olyan részletekre, amelyek fontosak voltak a megvalósítás szempontjából Az ezt követ® fejezetek részleteiben elemzik a szoftver létrehozásának lépéseit Elmagyarázom, hogy mi indokolta egy-egy döntésem, azokban az esetekben, ahol esetleg több megoldási mód is kínálkozott volna. Végül példákon keresztül illusztrálom a kapott eredményeket A létrehozott szoftver  a Java-nak köszönhet®en  végrehajtható kód szintjén architektúra-független, képes önálló- és hálózati alkalmazásként is m¶ködni, három

különböz® üzemmódban képes a feladatok kezelésére (a feladatmegoldásokat kísér® üzenetek és a grakus szemléltetés részletességét tekintve), több nyelven (jelenleg magyarul és angolul) is tud. Kulcsszavak: Java, grakus szemléltetés, Hozzárendelési feladat, Magyar módszer ii Tartalomjegyzék Feladatkiírás i Tartalmi összefoglaló ii Bevezetés 1 A Hozzárendelési feladat . A Hozzárendelési feladat megoldása Magyar módszerrel . Meghatározások . A Magyar módszer leírása . A feladat megoldása Alkalmazott eszközök . A Java programozási nyelv . Java applikáció vs. Java applet AWT vs. Swing Szálak a Java-ban . Java csomagok (package) . JAR (Java ARchive) . Policytool . . . . . . . . . . . . . . . . . . . . . . Az alapvet® feladatok megvalósítása Az ap csomag . Az APBase

osztály . . A MyList2D osztály . Az ap csomag m¶ködése . További feladatok megvalósítása . A gaps csomag . A GAPSStarter osztály . A GAPS osztály . A GAPSPanel osztály . A GAPSThread osztály . Az APData osztály iii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . 1 2 2 2 4 4 4 5 6 6 6 7 7 8 9 9 10 11 11 15 15 15 17 18 18 Az AssignmentMatrixPanel osztály . 21 Az AboutDialog osztály . 23 A Verbosity osztály . 23 A table csomag . A MyTableDialog osztály . A MyTableEditor osztály . Az IntegerField osztály . . . . . Extra funkciók megvalósítása . A többnyelv¶ség megvalósítása . Ábra és szöveg mentése közvetlenül a programból A gyorsítóbillenty¶k alkalmazása . Beépített példa feladatok . Technikai részletek . A szoftver fájlokba szervezése . A szoftver fordítása . A HTML-oldal beállításai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 24 24 25 26 26 26 27 28 29 29 29 30 A szoftver m¶ködés közben, tesztelés 31 Összefoglalás 40 Irodalomjegyzék 42 Nyilatkozat 43 Köszönetnyilvánítás 44 Függelék 45 Els® példa . 32 Második példa . 38 Források a WWW-n . 45 A Java programozási nyelvvel kapcsolatos oldalak . 45 Algoritmusok szemléltetésével kapcsolatos oldalak . 45 Operációkutatással kapcsolatos oldalak . 45 iv Bevezetés A Hozzárendelési feladat A Hozzárendelési feladat lényege jól szemléltethet® a következ® példával: adott bizonyos számú dolgozó és ugyanennyi, egymástól független munka; mindegyik dolgozó képes elvégezni bármelyik munkát, továbbá az egyes dolgozók adott munkákra vonatkozó költségei ismertek. A feladat az,

hogy minden egyes dolgozóhoz rendeljünk pontosan egy munkát, méghozzá olyan módon, hogy az összes feladat legyen elvégezve, az összköltség minimális értéke mellett. A feladat több módon is kiterjeszthet® illetve sz¶kíthet®, ám mi csak a fentieknek megfelel® modellt tárgyaljuk.1 Jelöljük n-nel a dolgozók számát, cij -vel pedig a j edik munka költségét, amennyiben azt az i-edik dolgozó végzi el (i = 1, , n; j = 1, . , n)! Tetsz®leges 1 ≤ i, j ≤ n indexpárra legyen ( xij = 1, ha az i-edik dolgozó végzi el a j -edik munkát, 0 különben. A probléma a következ® optimumszámítási modellel írható le: n X xit = 1 (i = 1, . , n) t=1 n X xtj = 1 (j = 1, . , n) t=1 xij ∈ {0, 1} (i = 1, . , n; j = 1, , n) n X n X (1) cij xij = z min i=1 j=1 A Hozzárendelési feladat az operációkutatás egyik régóta ismert, napjainkra lényegében megoldott problémája. Kezdetben a nyers er® módszerével próbálták meg1 A

Hozzárendelési feladatnál általánosabb a tiltott hozzárendelések kezelése és az ún. Szállítási feladat, speciálisabb pl. a Házasságkötési játék néven ismert probléma 1 közelíteni a feladatot, de ez az út  az akkori id®k legfejlettebb számítógépes teljesítménye mellett  már 10 × 10-es feladatok esetén is járhatatlannak bizonyult. Kés®bb Kuhn sikerrel dolgozott ki egy valóban használható eljárást, amely König maximum-párosítási algoritmusán és Egerváry redukciós eljárásán alapult[1]. Kuhn az 1955-ben közölt eljárásának a Magyar módszer nevet adta, utalva arra, hogy munkáját a két nagy magyar matematikus ihlette. A továbbiakban Imreh Balázs Operációkutatás c. könyvére[2] építve ismertetjük a módszer lényegét A Hozzárendelési feladat megoldása Magyar módszerrel Meghatározások Független 0-rendszer Adott mátrix 0 elemeinek egy rendszerét független 0rendszernek nevezzük, ha a mátrix minden sora és

minden oszlopa legfeljebb egy elemét tartalmazza a rendszernek. Valamely mátrixban esetleg több független 0rendszer is kijelölhet®, és maximális számú független 0-rendszerb®l is több lehet 0∗ A független 0-rendszer elemeit a továbbiakban 0∗ -gal fogjuk jelölni. Kötött sor (oszlop) Egy mátrix valamely sorát (oszlopát) kötöttnek nevezzük, ha mellette (felette) egy + jel áll. Szabad elem Egy mátrix valamely elemét szabad elemnek nevezzük, ha nem kötött sem a sora, sem az oszlopa. Szabad nulla Az a 0, amely szabad elem is egyben. A Magyar módszer leírása El®készít® rész. A C költségmátrix i-edik sorából rendre vonjuk ki az i-edik sor elemeinek minimumát (i = 1, . , n), és az el®álló mátrixot jelölje C ! A C mátrix j -edik oszlopának elemeib®l rendre vonjuk ki az illet® oszlop elemeinek minimumát (j = 1, . , n), és jelölje a kapott mátrixot C (0) ! C (0) -ban oszlopfolytonosan alakítsunk ki független 0-rendszert, azaz

oszlopról oszlopra haladva (j = 1, , n) a tekintett oszlopból választható 0-k közül mindig a legkisebb sorindex¶t vegyük fel a független 0-rendszerbe! Ezek után r értéke legyen 0, majd folytassuk az eljárást az Iterációs résszel ! Iterációs rész (r. iteráció) 1. lépés Ha a C (r) -ben kijelölt független 0-rendszer elemeinek száma n, akkor vége 2 az eljárásnak. Ellenkez® esetben kössük le C (r) -ben a 0∗ -okat tartalmazó oszlopokat, és folytassuk az eljárást a 2. lépéssel! 2. lépés Keressünk sorfolytonosan szabad 0-t! Amennyiben nincs szabad 0, akkor az 5. lépéssel folytatjuk, különben meg kell vizsgálnunk az illet® szabad 0 sorát Ha ez a sor 0∗ -ot tartalmaz, akkor a 3. lépés, ellenkez® esetben a 4 lépés következik 3. lépés A tekintett szabad 0-t lássuk el vessz®vel (00 ), kössük le a sorát és oldjuk fel a sorában lév® 0∗ oszlopának lekötését! Az eljárás a 2. lépéssel folytatódik 4. lépés A

tekintett szabad 0-t lássuk el vessz®vel (00 ), és ebb®l a 00 -b®l kiindulva képezzünk láncot! A láncképzés a következ®k szerint megy: minden láncbeli 00 -t az oszlopában lev® 0∗ követ a láncban, és minden 0∗ -ra, a sorában található 00 -vel folytatódik a lánc  feltéve, hogy vannak ilyen elemek, különben a láncképzés véget ér. Ezek után legyen C (r+1) a jelölések nélküli, aktuális C (r) mátrix, és lássuk el ∗ -gal (r+1) a cij (r) (r) (r) (r) elemet, ha cij ≡ 0∗ és cij nem szerepel a láncban, vagy cij ≡ 00 és cij eleme volt a láncnak! Végül növeljük meg r értékét 1-gyel, és folytassuk az eljárást az 1. lépéssel! 5. lépés Képezzük a szabad elemek minimumát, majd ezt az értéket vonjuk ki az összes szabad elemb®l és adjuk hozzá a kétszeresen kötött (soruk és oszlopuk is le van kötve) elemekhez! Ezt követ®en, az átalakított mátrixot tekintve aktuális C (r) mátrixnak, folytassuk az

eljárást a 2. lépéssel! Megjegyzések A láncképzés során el®fordulhat, hogy a lánc egyetlen (00 ) elemb®l áll, ilyenkor elfajuló láncról beszélünk. Ennek értelmezése az, hogy ezzel az elemmel közvetlenül b®víthet® az el®z®ekben el®állított független 0-rendszer. Belátható, hogy a szükséges iterációk száma legfeljebb n − 1. A módszer további el®nyös tulajdonsága, hogy kisebb módosításokkal alkalmazható az általánosabb, ún. Szállítási feladat megoldására (ld pl [2]-t!) 3 A feladat megoldása Alkalmazott eszközök A kit¶zött feladatot Java programozási nyelven oldottam meg, bár a probléma megoldásához szükséges alapvet® szempontoknak több olyan programozási nyelv is megfelelt volna, amelyet kell® mértékben ismerek (c/opengl, tcl/tk), úgy érzem a Java további el®nyökkel is rendelkezik, melyek motiválták választásom. A Java egy  a c++-hoz meglehet®sen hasonló szintaktikájú  általános célú,

objektum orientált nyelv. E  produktivitását tekintve mindenképpen  hatékony nyelv segítségével könnyedén kialakítható pl. több nyelv¶ felhasználói felület, a weben keresztül történ® futtatásra alkalmas program (ún applet) Választásom tehát a Java-ra esett, ebben a nyelvben kívántam tovább mélyíteni tudásom. Ennek megfelel®en magáról a Java programozási nyelvr®l szólok pár szót A Java programozási nyelv A Java viszonylag atal nyelv, alig több mint tíz éve, 1991-ben kezdték el tervezni, fejleszteni. 1994-ben a Java fejleszt®i megcélozták az Internet-et (Ne feledjük, az els® grakus böngész®, a Mosaic alig egy éve létezett akkor!) A nyelv er®södését jelzi, hogy 1994 ®szére megszületett az els® Java-ban írt Java-fordító. 1995-ben megjelenik a Java kereskedelmi forgalomban, majd 1996-ban kiadják az 1.0-ás Java Development Kit-et. A Java azóta is igen dinamikusan fejl®dik  az 12-es változat 1998-as jelent®s

újratervezéseit követ®en (Java Foundation Classes, Swing, Java2) , jelenleg az 1.4-es f® verziószámnál tart Éppen ezen dolgozat írása közben jelent meg az 1.50Beta1-es változat (45 oldal) A Java platform Java Application Programming Interface-b®l és Java Virtual Machine-ból áll (ld. az 1 ábrát!) A Java api-k az egyéb nyelvekb®l ismert könyvtáraknak felelnek meg, amiket a programozó kényelmesen felhasználhat programjaiban2 A Java forráskódot el®ször le kell fordítani egy köztes, ún bájt-kódra, majd 2 Az Java iránt érdekl®d®k ugye tudják, hogy érdemes minél többet olvasni az api dokumentációját? Megtekinthet® pl. itt: http://javasuncom/j2se/142/docs/api/ 4 ezt a hordozható bájt-kódot a jvm interpretálja. Ennek a hordozhatóságnak persze ára van, ami legjobban talán a futásid®kben érhet® tetten. Ma már azonban, sokak számára elérhet® az a számítási sebesség, amely mellett inkább a Java által nyújtott el®nyök

kerülhetnek el®térbe. Java nyelvû program Java API-k Java Virtual Machine Számítógépes operációs rendszer 1. ábra A Java platform kapcsolódása az operációs rendszerekhez és a Java nyelv¶ progra- mokhoz. Ez az igen egyszer¶ sematikus ábra azt szemlélteti, hogy miként ékel®dik a Java platform (jvm, Java api) rétege az operációs rendszer és a Java bájt-kód közé. Java applikáció vs. Java applet Java applikációknak a Java nyelv¶, önállóan m¶köd® alkalmazásokat hívjuk, szemben az applet-tel, amely  a Java api dokumentáció meghatározása szerint  egy olyan kis program, amely egy másik alkalmazásba van ágyazva.3 Azokat az applet-eket, amelyeket web-oldalakba ágyazott m¶ködésre tervezünk az Applet (vagy újabban inkább a JApplet) osztályból kell származtatnunk. Ezek az osztályok biztosítják a standard felületet az applet és környezete között. A JApplet osztály némileg inkompatíbilis a korábbi Applet osztállyal, ui a

contentPane kell hogy legyen a JApplet minden gyermekének (komponensének) szül®je (tulajdonosa). Azaz a korábbi applet.add(child); helyett, az applet.getContentPane()add(child); módszerre van szükség a komponensek applet-re helyezésekor. Ugyanez igaz az elrendezés menedzserekre, a komponensek eldobására stb Fontos megjegyezni, hogy a web-böngész®kb®l indított Java applet-ek  biztonsági okokból  igen korlátozott jogosultsággal rendelkeznek rendszerünk felett, ellentétben az önállóan futtatható változataikkal, amelyek  az adott operációs rendszernek megfelel®  szokásos jogokkal bírnak. Azaz, egy böngész®b®l futtatott Java applet, az alapértelmezett beállításoknak köszönhet®en, nem képes a lokális fájlrendszert olvasni, írni stb. 3 Valójában a határok könnyen elmosódnak, hiszen általában megoldható, hogy egy Java program képes legyen applet-ként és önálló alkalmazásként is m¶ködni (egyetlen forráskódról van szó).

5 A szakdolgozatomban tárgyalt szoftver önálló alkalmazás és applet is egyben. Ehhez a kódnak csak a töredékét kellett felkészítenem erre a kett®s szerepre. Az applet el®nye, hogy hálózaton keresztül is elérhet®vé teszi az alkalmazást, az esetleges verzió frissítésekr®l nem a felhasználónak kell gondoskodnia, biztonságosabb. Az applikáció el®nye, hogy mindig elérhet® rendszerünkön, nem kell megvárni a letöltési id®t. AWT vs. Swing A Java 1.0 gui (Graphical User Interface  Grakus Felhasználói Felület) könyvtárának eredeti célja az volt, hogy a programozók számára olyan felületet kínáljon, amely jól mutat mindegyik platformon. Az Abstract Window Toolkit (awt) nem érte el célját, köszönhet®en az elkapkodott tervezésnek, kivitelezésnek[3].4 Gyengécske megjelenése és a benne lev® sok megszorítás újabb megoldásokért kiáltott A helyzet némiképp javult a Java 1.1-ben bevezetett eseménykezeléssel, valamint a

JavaBeans-szel. A pontot az  -re a Java 2 (jdk 12) tette fel, a Java Foundation Classes bevezetésével, amelynek gui részét Swing-nek hívják. A dolgozatomban részletezett szoftver az újabb, jobb Swing gui-t használja, csak a szükséges minimális mértékben tartalmaz awt elemeket. Szálak a Java-ban Az objektumok lehet®vé teszik, hogy a programot önálló részekre bontsuk. El®fordul azonban, hogy arra is szükségünk van, bizonyos részek önállóan futó alfeladatokat lássanak el  ezeket a független alfeladatokat szálaknak nevezzük A többszálúságnak sok lehetséges felhasználási módja létezik, de általában arra szolgál, hogy egy bizonyos eseményre, eszközre való várakozás ne tartsa fel az egész programot. Gyakorlatban ez azt jelenti, hogy a processzen belül létrehozunk egy szálat, amelyet az eseményhez, eszközhöz rendelünk, és a program többi részét®l függetlenül futtatjuk. A megvalósított szoftverben alkalmazom a szálakat, a

felhasználói interakciók jobb kezelése érdekében. Java csomagok (package) Nagyobb feladatok esetén feltétlenül hasznos a meglév® osztályokat valamilyen módon elkülöníteni, pl. a névütközések elkerülése végett Erre szolgálnak a csomagok 4 Aki nem tudott annak idején megküzdeni az awt-vel, az lépjen újra szorítóba és próbáljon egy Swing -et! 6 A Java osztályokat könnyen csomagokba szervezhetjük, ehhez mindössze arra van szükség, hogy az összetartozó osztályokat közös könyvtárba helyezzük (melynek neve lehet®leg utal a csomag rendeltetésére). Eztán az osztályokat tartalmazó fájlok els® sorában feltüntetjük a csomag nevét, amely megegyezik annak a könyvtárnak a nevével, amelyben található. A szakdolgozatomban ismertetend® szoftver alkalmazza a csomagokat, a jobb áttekinthet®ség és az esetleges újra felhasználhatóság érdekében. JAR (Java ARchive) Az elkészített Java alkalmazások terjesztéséhez,

telepítéséhez célszer¶ a Java, jar elnevezés¶ tömörít® és csomagoló eszközét használnunk. A jar fájlok formátuma lényegében kompatíbilis az igen elterjedt zip fájl formátummal. A jar fájlok alkalmazása igen el®nyös a web-es applet-ek esetében. Ahhoz ugyanis, hogy egy applet betölt®djön a böngész®be, minden egyes alkotórészének le kell tölt®dnie a kliens gépére. Ez több fájl esetén több kommunikációt igényel a kliens és a szerver között, nem is beszélve a tömörítéssel elérhet® méretcsökkenésr®l. A dolgozatomban tárgyalt csomagokat és a futásukhoz szükséges állományokat egy tömörített Java archívumba foglaltam, a könnyebb hordozhatóság és az applet letöltési idejének csökkentése érdekében. Policytool A Java Futtató Környezet (jre) részét képezi a Policytool nev¶ eszköz, amelynek akkor vesszük hasznát, ha szeretnénk egy applet-et több jogosultsággal felruházni, mint az alapértelmezésben

szerepl®, igen szigorú biztonsági beállítások. Az eszköz részletes ismertetésére nem áll módomban kitérni, ajánlom a 45. oldalon szerepl® hivatkozást. A szoftver applet-ként való futtatásakor, a Policytool nev¶ standard Java eszközt kell alkalmaznunk ahhoz, hogy a programban jelenlév® minden lehet®séget kiaknázhassunk.5 Természetesen, ha önálló alkalmazásként indítjuk a programot, a teljes fegyvertár rendelkezésünkre áll. További részletekhez ajánlom a 45. oldalon található- és [3] irodalmakat 5 A Policytool-t érint® részeket ld. a 26 oldalon! 7 Az alapvet® feladatok megvalósítása Az implementált szoftver alapvet® feladatának nyilvánvalóan a Hozzárendelési feladatok, Magyar módszerrel történ® helyes megoldását kell tekintenünk. A forráskód6 teljes egészében angol nyelv¶ (a megjegyzések, elnevezések is), hiszen gyakorlatilag ez a programozás nyelve napjainkban, továbbá azért is, mert nem tartom helyesnek

az ékezet nélküli magyar szavak használatát, legkevésbé a vegyes nyelv¶ kifejezéseket.7 A f® célkit¶zésnek megfelel®en, els® lépésként egy olyan csomagot (package) hoztam létre, amely a fenti feladat számítógépes ábrázolásához szükséges adatszerkezeteket és ezen adatszerkezeteken végzend® m¶veleteket tartalmazza. Mivel a kés®bbiekben erre a csomagra olyan felszínt szerettem volna húzni, amely kell® részletességgel tudja, hogy egy adott eljárás éppen mit csinál, ezért ennek lehet®ségét már most meg kellett valósítanom. Erre a feladatra absztrakt metódusokat használtam, hiszen pontosan még nem ismert, hogy a magasabb szinten lév® felszín hogyan kívánja szemléltetni az aktuális lépést. GAPS Starter GAPS table package ap package APBase GAPS Panel GAPS Thread APData MyList2D Assignment Matrix Panel My My TableDialog TableEditor gaps package Integer Field 2. ábra A létrehozott legfontosabb osztályok viszonya Az

ábrán a fejlesztés során létre- hozott legfontosabb osztályok viszonya látható, továbbá az egyes osztályokat tartalmazó csomagokat is feltüntettem. Talán ezekb®l is érezhet® már, hogy a problémát lehet®leg sok szintre próbáltam tagolni, a magukban is életképes csomagok, önálló osztályok és metódusok elkülönítésével. Ez a megközelítés általában igen hasznos, hiszen pl a (tovább)fejlesztést, hibajavítást nagy mértékben megkönnyíti. Jelen probléma esetén azonban, ezt a szemléletet id®nként nehezen kivitelezhet®nek találtam, de az alábbi csomag és az ebben szerepl® metódusok  úgy hiszem  jól körülhatároltak, funkciójuk elég világosan deniált. 6 7 Helytakarékosság céljából, tömörebben közlöm a forráskód megfelel® részeit. A szárnyaló gondolatok többé nem szárnyalnak. Amúgy értjük, hogy mi az elszével ? 8 Az ap csomag Az ap csomag (Assignment Problem package) a Hozzárendelési feladatot

leíró osztályokat tartalmazza, ez a szoftver motorja. A következ® három osztályt foglalja magába: • az APBase osztály a Hozzárendelési feladatot  Magyar módszerrel megoldó  absztrakt alaposztály, • az APData elnevezés¶ osztály a feladatot leíró adatszerkezeteket és a rajtuk végezhet® m¶veleteket tartalmazza, • a MyList2D a csomag legegyszer¶bb osztálya, a feladatmegoldás láncképzéshez szükséges egysége. A fenti három osztály forráskódja nagyjából 900 sort tesz ki, ezért a teljes feladat megoldásának ez volt a kisebb és valójában könnyebb része. Az APBase osztály Az APBase (alap)osztályra szöveges- és grakus felhasználói felületet is építhetünk. Az elképzelésem az volt, hogy a feladatmegoldó algoritmus, futása során üzeneteket küld: az eljárás megfelel® pontjain sendMsgXXX() elnevezés¶ metódushívásokat helyeztem el, ám ezek a metódusok mind absztrakt eljárások. A célom az volt, hogy ez az osztály

egyfajta alaposztályként szolgáljon, amelyre építkezve ezeket az absztrakt eljárásokat tartalommal töltjük meg. Az APBase osztály tehát maga is absztrakt, hiszen absztrakt metódusokat tartalmaz. (Java-ban egy adott osztályban lev® egyetlen absztrakt metódus is kikényszeríti azt, hogy maga az osztály is absztrakt legyen) Absztrakt osztályokból  érthet® okokból  nem hozható létre objektum, viszont a leszármazási láncban szerepelhetnek. Itt jegyzem meg, hogy Java-ban (az interface-ekt®l eltekintve) a leszármazottaknak, csak egyetlen szül® osztályuk lehet Ez id®nként igen kényelmetlen, de így a többszörös öröklésnél esetenként felmerül® problémák nem léteznek, és talán nagyobb hangsúlyt kap a gondos tervezés is. Az APBase osztály publikus (public) és védett (protected) adatokat nem tartalmaz, két privát (private) elérés¶ adata egy APData típusú objektumból és a lehetséges maximális költséget meghatározó,

véglegesített statikus (nal static) egész érték¶ adatból áll. Publikus eljárásai a konstruktora és a getAssignment elnevezés¶ metódusa. Ez utóbbi egy egészeket tartalmazó tömb referenciáját adja vissza Ez a visszaadott tömb azt írja le sorról sorra, hogy egy adott sor hányadik oszlopában található a 0∗ elem, vagyis ez a tömb reprezentálja a független 0-rendszert. A 9 getAssignment() metódus a Magyar módszer egyes lépéseit a bevezet®ben ismertetett leírásnak megfelel®en tartalmazza (11. oldal) Az absztrakt sendMsgXXX() metódusok azért védett elérés¶ek, mert ezeket a metódusokat közvetlenül csak az APBase osztály kívánja meghívni. A Magyar módszert, mint eljárást csak ez az osztály kell, hogy részleteiben ismerje Privát eljárásai a Magyar módszernek megfelel® lépésekb®l (stepX()) és az azokat még elemibb lépésekre bontó metódusokból állnak (pl. makeChain(), amely a lánckészítésért felel®s) Az APData

osztály Az APData osztály a megoldáshoz szükséges alacsonyabb szint¶ algoritmusokat és adatszerkezeteket tartalmazza  a lánc kivételével, amelyet a MyList2D osztály valósít meg. Ez el®bbi osztály csak privát elérés¶ adatokkal dolgozik, ellenben minden metódusa publikus Az osztály eljárásai között olyan elemi m¶veleteket találunk, mint pl. egy oszlop (sor) lekötése vagy felszabadítása, a nullák megjelölése vagy éppen a jelölések megszüntetése A fenti osztály egyik privát elérés¶ adata a MyList2D osztály egyik példánya, amelyet kés®bb részletesen bemutatok. Az APData osztály tartalmazza a Hozzárendelési feladat költségmátrixát, annak dimenzióját, számon tartja a 0∗ és 00 elemeket, a kötött sorokat és oszlopokat, a kérdéses szabad nulla sorát és oszlopát, valamint a kérdéses 0∗ oszlopát. Az adatok tárolásához szükséges helyek lefoglalását természetesen dinamikusan oldottam meg, valamint a helyigényüket

próbáltam csökkenteni Kihasználtam ui. a Magyar módszer két speciális tulajdonságát: • adott sorban legfeljebb egy 00 található (adott oszlopban esetleg több 00 is lehet), • adott sorban és adott oszlopban legfeljebb egy 0∗ található. Ennek megfelel®en, a 00 és 0∗ elemek feljegyzését egy-egy n elem¶, egészeket tartalmazó tömb használatával valósítottam meg. Ez céljainknak megfelel®, hiszen így az adatok visszanyerése elég kényelmes és elég gyors is (21. oldal) Valójában még egy speciális tulajdonságot is kihasználtam: a legtöbb nyelven sorfolytonosan, balról jobbra írunk. Ha esetleg nem ilyen nyelv¶ adatvisszanyerésre lenne szükség, az újabb meggondolásokat igényelne az adattárolás és visszanyerés hatékonyságainak tekintetében. Érdemes egy kicsit részletesebben megnéznünk, hogyan valósítható meg az, hogy az osztály privát adatai referenciákon keresztül se legyenek módosíthatóak. Pl: public int

[]getZeroStars() { int []stars = new int[nDim]; for(int i = 0; i < nDim; i++) { 10 } stars[i] = zeroStars[i]; } return stars; A fenti kódrészletb®l az látható, hogy lényegében a zeroStars[] privát elérés¶nek szánt adat másolatának referenciáját (stars ) adom vissza a metódust hívó eljárásnak, amely így már nem lesz képes módosítani az eredeti adatot. A MyList2D osztály A MyList2D osztályt a Magyar módszerben szerepl® láncképzés megvalósítása érdekében alakítottam ki. Azért hoztam létre egy önálló egységet ehhez a feladathoz, hogy egy esetlegesen hatékonyabb adatszerkezetre vagy algoritmusra való áttérés még könnyebben megvalósítható legyen Az osztály alapjául a standard Java könyvtárban szerepl® Polygon osztály szolgált, de azon lényeges egyszer¶sítéseket hajtottam végre. Az osztálynak három metódusa van, mind publikusan hozzáférhet® Az egyik listába helyezi a cij mátrix elem (i, j) indexeit, a másik

lekérdezi, hogy az (i, j) indexpár megtalálható-e a listában, a harmadik pedig kiüríti a listát. Valójában ez utóbbi m¶velet  hatékonysági okokból  csak 0-ra állítja a listában található elemek számát, hiszen a Java-ban alapvet®en nincs mód a foglalt memória felszabadítására (mindez automatikusan a háttérben történik). Az ap csomag m¶ködése Ebben a fejezetben az ap csomag m¶ködésér®l szólok részletesebben, hiszen  a f® célkit¶zéseknek megfelel®en  ez a szoftver legfontosabb, másrészt egyik legáttekinthet®bb része. package ap; public abstract class APBase { public APBase(int costs[][]) { apData = new APData(costs); } public int [] getAssignment() { int rep = 0; int step = 1; apData.reset(); step0(); while(true) { switch( step ) { case 1: if(step1(rep)) { return apData.getZeroStars(); } step = 2; break; case 2: 11 } } . } } step = step2(); break; case 3: step3(); step = 2; break; case 4: step4(); step = 1; rep += 1; break;

case 5: step5(); step = 2; break; default: break; A fenti kódrészlet az APBase osztály konstruktorát és a Magyar módszert megvalósító, algoritmikus keretet mutatja. Az els® sorban azt jeleztem, hogy az osztály az ap csomagba tartozik. Látható, hogy a konstruktorban egy APData típusú objektumot hozunk létre, amelyet a paraméterként kapott költségmátrixszal inicializálunk Mivel csak egy konstruktort határoztam meg az osztályhoz, ezért garantált, hogy az osztályból létrejöv® objektumok mind megfelel®en vannak inicializálva  természetesen amennyiben az APData osztály helyesen m¶ködik. Az APBase típusú objektum életre hívása után, másik publikus eljárását, a getAssignment() metódust hívhatjuk meg. Ez a költségmátrix alapján,  a 2 oldalon ismertetett  Magyar módszer segítségével egy optimális hozzárendelést határoz meg. Az eljárás során nyilván kell tartanunk, hogy hányadik iteráció és hányadik lépés következik,

el®bbire a rep (repetition  ismétlés), utóbbira a step (lépés) egész érték¶ lokális változók szolgálnak. A helyes kezd®értékek beállítása után, az APData típusú apData objektum reset() metódusát hívtam meg, amely lehet®vé teszi az APData osztály újra inicializálását a költségmátrix ismételt megadása nélkül. Ezt követ®en végrehajtjuk a Magyar módszer el®készít® lépését, amelyet a step0() metódussal valósítottam meg. Itt gondoskodtam a sor- és oszlopminimumokkal végzett módosításokról (preconditionCostMatrix()), majd a független 0-rendszer kialakításáról private void step0() { preconditionCostMatrix(); makeIndependentZeroSystem(); } A költségmátrix el®készítése után, a getAssingment() metódus egy while12 ciklusban található, switch-elágazás segítségével gondoskodik arról, hogy a módszer lépései a megfelel® sorrendben legyenek végrehajtva. Mivel a step változó értéke kezdetben 1 volt, ennek

megfelel®en a case 1 ág kerül el®ször kiértékelésre. Itt a step1() metódust hívjuk meg a rep paraméterrel (erre a paraméterátadásra csak azért volt szükség, hogy a megfelel®  itt nem idézett  sendMsgXXX() üzenet meg tudja jeleníteni azt az információt, hogy hányadik iterációban ért véget az eljárás). private boolean step1(int rep) { if(apData.getNumberOfZeroStars() == apDatagetDimension()) { return true; } tieColumns(); return false; } A fenti step1() függvény egy boolean típusú értéket ad vissza, amely igaz érték¶, amennyiben optimális hozzárendelést találtunk az adott iterációban (a független 0-rendszer elemszáma megfelel®), hamis érték¶ ellenkez® esetben. Ha ez utóbbi (hamis) ágra kerülünk, akkor a return utasítást megel®zi a megfelel® oszlopok lekötése (tieColumns()), ahogy azt a Magyar módszer ismertetésénél láttuk. A visszaadott értéknek megfelel®en, vagy visszaadjuk az optimális hozzárendelést leíró 

egész értékeket tartalmazó  tömb referenciáját, vagy rátérünk a második lépésre a következ® while-ciklusban (step = 2). A második lépést megvalósító, step2() elnevezés¶ metódus sem sokkal összetettebb a lehetséges visszatérési értékét tekintve, amely három értéket vehet fel. private int step2() { if(!hasFreeZero()) { return 5; } else { int row = apData.getRowOfFreeZero(); if(!apData.hasRowZeroStar(row)) { return 4; } else { apData.setColumnOfZeroStarInRow(row); return 3; } } } Amennyiben nincs szabad nulla, az eljárást az ötödik lépéssel folytatjuk a következ® ciklusban (return 5;), különben a módszernek megfelel®en megvizsgáljuk az illet® szabad 0 sorát (row). Ha ez a sor nem tartalmaz 0∗ -ot, akkor a negyedik lépés következik (return 4;), ellenkez® esetben a harmadik lépéssel folytatjuk (return 3;), ahol viszont fel kell jegyeznünk, hogy melyik volt a kérdéses 0∗ oszlopa. A harmadik vagy ötödik lépést elvégezve, a

második lépésre térünk vissza (step = 2); míg a negyedik lépés után újabb iterációba kezdünk (rep += 1), az els® lépést®l kezd®d®en (step = 1). Most lássuk ezeket kicsit részletesebben! private void step3() { int row = apData.getRowOfFreeZero(); 13 int col = apData.getColumnOfFreeZero(); } apData.setZeroMark(row, col); apData.setRowTied(row); apData.setColumnFree(apDatagetColumnOfZeroStar()); Azaz a harmadik lépésben 0 -vel jelöljük meg a talált szabad nullát (setZeroMark(row, col)), majd lekötjük sorát (setRowTied(row)), valamint felszabadítjuk a sor 0∗ -ot tartalmazó oszlopát. (Ezért kellett feljegyeznünk a második lépésben, hogy hányadik oszlopban található a szabad nulla sorában lév® 0∗ .) private void step4() { makeChain(apData.getRowOfFreeZero(), apDatagetColumnOfFreeZero()); remakeMatrices(); } Az eljárásnak megfelel®en a negyedik lépésben megkezdjük a láncképzést a talált szabad nullától elindulva

(makeChain()), majd a kapott láncnak megfelel®en, a mátrixban módosítjuk a bejegyzéseket (0, 00 , 0∗ ). private void step5() { reconditionCostMatrix(); } A Magyar módszer ötödik lépése egyszer¶en a költségmátrix speciális átalakítását írja el®, amelyet ezen a szinten  a fentiekkel összhangban  nem részleteztem tovább. 14 További feladatok megvalósítása A f® feladat mellett  amely a Hozzárendelési feladat, Magyar módszerrel megvalósított számítógépes megoldását jelentette , a következ®ket tekintettem kiegészít® feladatoknak: • legalább két üzemmód, amely az eljárást kísér® szöveges üzenetek részletességét jellemzi, • grakus szemléltetés, amely a szöveges üzeneteket kíséri. Valójában amit megvalósítottam, az ennél jóval több, hiszen ha csak azt vesszük gyelembe, hogy három  jól elkülöníthet®  m¶ködési módot terveztem és valósítottam meg a szoftverben, valamint az esetleges

oktatási szempontok érdekében, a [2] jegyzet jelöléseihez h¶ grakus szemléltetést választottam, már ez is szép eredménynek tekinthet®.8 Hasonló jelleg¶ feladatok számítógépes megjelenítésekor, találkozhatunk az ember számára ebben az esetben nem túl szemléletes, ám jóval egyszer¶bben kivitelezhet® színkódos megoldásokkal. A kezdeti nehézségek után valójában bennem is felmerült, hogy a könnyebb utat választom, azonban ragaszkodtam eredeti elképzelésemhez, amely végül jóval esztétikusabb és a felhasználó számára könnyebben áttekinthet® eredményt adott. A gaps csomag A gaps csomag (Graphic Assignment Problem Solver  Grakus Hozzárendelési Feladat Megoldó) az ap csomagra épülve, a grakus felhasználói felület (gui) kialakításáért- és az ismertetett eljárás (2. oldal) grakus megjelenítéséért felel®s Kb. 2000 sorával ez a szoftver grakus motor ja A részletek ismertetése el®tt, elöljáróban annyit, hogy a

GAPSStarter osztály indítja be a grakus motor t. A GAPS osztály a grakus felület váza, míg a GAPSPanel keretet biztosít az AssignmentMatrixPanel osztálynak, amely a számunkra legérdekesebb tevékenységet, a szemléltetést végzi. A GAPSStarter osztály A GAPSStarter (GAPS Indító) osztály a JApplet-b®l származik, azaz alapvet®en applet-ként funkcionál. Azonban tartalmaz egy public static void main(String args[]) 8 A szoftverben található további hasznos lehet®ségekr®l a 26. oldaltól kezdve számolok be 15 metódust, amely lehet®vé teszi, hogy közvetlenül is életre keltsük. Itt kell el®készíteni programunk arra a kett®s szerepre, hogy applet-ként és önálló alkalmazásként is elindíthassuk. Valójában ez egy igen egyszer¶ (de nagyszer¶) dolog A legfontosabb sorok ehhez a következ®k: JFrame f = new JFrame(); JApplet applet = new JApplet(); applet.init(); f.setContentPane(appletgetContentPane()); f.setVisible(true); applet.start();

Itt f egy JFrame típusú objektum, amelynek tartalom paneljét (ContentPane), az applet-ként elindított alkalmazás, tartalom paneljére állítjuk be. Innent®l kezdve lényegében ugyanúgy m¶ködnek. Egyetlen boolean típusú változó használatával azt is feljegyezhetjük, hogy miként indították az alkalmazást, vagyis az appletill. applikáció-specikus kód is elkülöníthet®9 A tárgyalt osztály vizuálisan lényegében csak egy JButton-t tartalmaz. Ezt aktivizálva a GAPS osztály egyik példányát hívjuk életre (ld a 3 ábrát!) Az osztály alapötlete onnan származik, hogy a GAPS osztály nagyobb szabadságot kaphasson azáltal, hogy  böngész®be ágyazott futtatása esetén  ne a web-oldal részeként, hanem önálló ablakban jelenjen meg. Gyakorlatilag ez az ablak tetsz®leges átméretezésére ad lehet®séget, amely az igényesebb felhasználó természetes kívánságát elégíti ki. Web-oldalba ágyazott applet Beágyazott indító gomb

Önálló ablakban futó applet 3. ábra Az ábra bal oldalán látható, applet-et indító (web-oldalba ágyazott) indító gomb és az önálló ablakban futó applet kombinációja el®nyösebbnek t¶nik, mint a jobb oldalon látható megoldás, amely a tisztán web-oldalba ágyazott applet lehet®ségét illusztrálja. Programomban a jobbnak t¶n®, önálló ablakban futó megoldást választottam, továbbá a kényelmesebb, gyorsabb használhatóság érdekében, az ablak a képerny® középre igazítva jelenik meg. A legtöbb ablakkezel® menedzser ui automatikusan a képerny® bal fels® sarkába vagy véletlenszer¶ helyre igazítja a felbukkanó új ablakokat. 9 Tipp: a main() metódus csak akkor hajtódik végre, ha alkalmazásként hívták meg a programot. 16 A GAPS osztály A GAPS osztály szintén a JApplet osztályt b®víti (extends), azaz bel®le származik. Ezt az osztályt tisztán applet-ként való futtatásra terveztem, és a fentebb ismertetett okok

miatt alkottam meg számára a GAPSStarter osztályt A GAPS osztály megvalósítja (implements) az ActionListener interfészt, amelyre a menü-események kezelése miatt volt szükségem. Az osztály konstruktorában egy  képerny® közepére centrált  keretet hozok létre. Majd a konstruktorból meghívom az applet start() metódusát, amely közvetve az init() metódus végrehajtását kezdi meg. Az init() metódusban létrehozom és elhelyezem a menüt és egy  alapértelmezett konstruktorral hívott  GAPSPanel objektumot. Az applet-ekben meglév®, felüldeniálható stop() metóduson keresztül gyelmeztetem a GAPSPanel-t, hogy befejezheti m¶ködését, hiszen a web-oldalt elhagyták vagy a programból kilépni szándékozott a felhasználó. Az osztály által kínált menüb®l kiválasztva lehet elindítani az újabb feladatok bevitelét, azok újra futtatását, a beállítások módosítását, a szerz®i információk megjelenítését. A menü további

beállítási lehet®ségeir®l csak a 26 oldaltól kezdve írok részletesebben. Ennek oka az, hogy  bár nagyon hasznosnak találom mindet  az eredeti f® célkit¶zést®l kicsit távolabb állnak. A kiválóan dokumentált és jól felépített Java könyvtárra jellemz®, hogy egy olyan dialógus ablak megvalósítása, amely arra kérdez rá, valóban ki akarunk-e lépni a programból, pár sorból áll csupán, elrontani sem lehet. Lényegében ezt a megoldást alkalmaztam erre a célra: private boolean isExitConfirmed() { Object []options = {"Yes", "No"}; int n = JOptionPane.showOptionDialog(this, "Are you sure?", "About exit", JOptionPane.YES NO OPTION, JOptionPane.QUESTION MESSAGE, null, options, options[0]); if(n == JOptionPane.YES OPTION) { return true; } return false; } Amennyiben igaz értéket kapunk vissza kiadom a f.dispose(); utasítást, amely megszünteti a vizuális komponenseket tartalmazó, JFrame típusú

objektumot.10 10 A keret (frame) képerny®re centrálását a következ® módon oldottam meg: Pontosabban nem megszüntetésr®l van szó, hanem arról, hogy elenged minden általa és gyermekei által lekötött natív er®forrást. 17 private void setFrameCentered(JFrame frame, int width, int height) { GraphicsEnvironment ge = GraphicsEnvironment.getLocalGraphicsEnvironment(); Rectangle r = ge.getMaximumWindowBounds(); if(width > r.width) { width = rwidth; } if(height > r.height) { height = rheight; } Point p = ge.getCenterPoint(); frame.setBounds(px - width/2, py - height/2, width, height); } A GAPSPanel osztály A GAPSPanel-t a JPanel osztályból hoztam létre, azzal a céllal, hogy a GAPSThread vizuális komponenseit tárolja. Nevezetesen egy AssignmentMatrixPanel típusú panelt középen és egy JButton típusú nyomógombot alatta. A két komponenst a GAPSThread osztály egyik példánya helyezi el rajta (ld. lentebb), amelyet a megfelel® konstruktorból

indítunk public GAPSPanel(int costs[][], Locale locale, Verbosity verbosity) { gapsThread = new GAPSThread(this, costs, locale, verbosity); } Publikus removeNotify() metódusában gyelmeztetem az esetlegesen futó GAPSThread szálat, hogy fejezze be m¶ködését, hiszen a komponens megsz¶nik, további lépéseket már nem kell végrehajtania a Magyar módszerb®l. A GAPSThread osztály Végül elérkeztünk az egyik legfontosabb osztályhoz, ez az osztály tölti fel tartalommal az APBase absztrakt metódusait! A GAPSThread ennek megfelel®en az APBase osztályból származik, ezért be kell hívnia az ap csomagot. A GAPSThread osztály konstruktorában megkapja • szül®je referenciáját, • a költségmátrixot, amellyel dolgoznia kell, • az aktuális nyelvre vonatkozó beállításokat, • a kívánt m¶ködési módot, amely az üzenetek kiírásának részletességét határozza meg. A konstruktorban, az átadott paraméterekkel inicializálom az osztályt, majd

létrehozom a fentebb említett nyomógombot, panelt is. A gomb (continueButton) célja, hogy használatával lehet®vé váljon a felhasználó és a program interakciója a szemléltetett eljárás végrehajtása során. A következ® módon lehetséges ezt elegánsan megoldani: 18 continueButton.addActionListener( new ActionListener() { public void actionPerformed(ActionEvent e) { doContinue(); } }); Ez a megoldás jó példa a Java eseménykezelésére, valamint a névtelen objektumok használatára. A Java-t kevésbé ismer®knek szokatlannak t¶nhet a fenti kódrészlet, ezért részletesebben elmagyarázom, mir®l is van szó A continueButton egy JButton típusú objektum, amelynek meghívjuk az (AbstractButton-tól származó) addActionListener() metódusát. Ez a metódus  nem túl meglep®  egy ActionListener interfésszel bíró objektumot vár paraméterként. Most jön a trükk! Ott helyben létrehozunk egy névtelen, ActionListener típusú interfészt

megvalósító objektumot. Mivel az interfész egy olyan osztály, amelynek minden metódusa absztrakt, ezért ahhoz hogy bel®le objektumot hozhassunk létre, meg kell valósítanunk minden egyes metódusát. A fenti interfésznek csak egyetlen metódusa van, a void actionPerformed(ActionEvent e) ezért az a három sor középen. (Az actionPerformed() metódus egy ActionEvent típusú objektumot vár paraméterként, amit most nem használunk fel.) Mit kaptunk végül? Egy olyan nyomógombot, amelyet bármikor aktivizálva (lenyomva) végrehajtódik a doContinue() metódus. Elegáns megoldás, nem?11 Még egy fontos dolgot kell áttekintenünk ahhoz, hogy a további magyarázatokat folytathassam. Ez pedig a szálak kezelése, melyr®l egy rövid bevezetés a 6 oldalon olvasható. Java-ban alapvet®en kétféleképpen hozhatunk létre szálakat programjainkban. Az egyik megoldás szerint: class ComputingThread extends Thread { . public void run() { // computing. } . } A szál

bef¶zése programunk szövetébe a következ® módon történik: ComputingThread t = new ComputingThread(.); t.start(); 11 Bonyolultabb (értsd: több soros) eseménykezelés esetén, nem célszer¶ ezt a megoldást választani, a kód áttekinthetetlensége miatt. Ilyenkor pl a (fenti esetben a nyomógombot) deklaráló osztálynak kell megvalósítania az interfész metódusait. 19 Ennek a megoldásnak az a szépséghibája, hogy Java-ban  az interfészek kivételével  csak egyszeres ágú öröklés lehetséges. De ahogy a Galaxis Útikalauz Stopposoknak mondja: Ne ess pánikba! Valóban, van megoldás arra az esetre is, ha szeretnénk valamely másik osztálynak fenntartani a szül®i el®jogokat. Íme: class ComputationRunner implements Runnable { . public void run() { // computing. } . } A szál elindítása ebben az esetben egy kicsit másként néz ki: ComputationRunner r = new ComputationRunner(.); new Thread(r).start(); Mint korábban említettem, a

GAPSThread osztály az APBase absztrakt alaposztályból származik, ezért a második megoldási módot valósítottam meg.12 Az osztály konstruktorában, a szál létrehozása el®tt, meg kell gy®z®dnünk arról, hogy az AssignmentMatrixPanel típusú objektum készen áll a kimen® üzenetek fogadására. Pontosabban arról van szó, hogy ha létrehoztunk egy gui objektumot, azt csak az esetleges szálak gyelembevételével szabad módosítani (thread-safety). Vagyis hibát követhetünk el, ha egy másik szálról akarjuk azt a grakus objektumot módosítani, amely még az esemény-közvetít® szálon (event-dispatching thread) várakozik frissítésre. Pl hibás megközelítés esetén, nem garantált, hogy a panel grakus háttere készen áll már, amikor az üzeneteket küldeni szeretnénk rá kirajzolásra.13 B®vebb leírásokra pl. a 45 oldalon található Java leckék között lelünk Ezeknek megfelel®en, én lényegében így oldottam meg a fenti problémákat:

public GAPSThread(GAPSPanel owner, int costs[][], Locale locale, Verbosity verbosity) { super(costs); . amp = new AssignmentMatrixPanel(costs); owner.add(amp, BorderLayoutCENTER); continueButton = new JButton(" "); continueButton.addActionListener(); owner.add(continueButton, BorderLayoutSOUTH); owner.setVisible(true); // Do not add GUI code after this line! myThread = new Thread(this); myThread.start(); } 12 Az osztály elnevezése ezek ellenére mégis GAPSThread, és nem GAPSRunner, hiszen végeredményben mégis csak szálról van szó. 13 Vigyázat! Amint meghívjuk a szál start() metódusát, több független szálon kell gondolkodnunk. 20 Az osztály legterjedelmesebb részét a megvalósítandó metódusok teszik ki. Ezekben a metódusokban a következ® sémát követtem: protected void sendMsgXXX(.) { if(currentVerbosity.getLevel() == VerbosityHIGHEST LEVEL) { } else if(currentVerbosity.getLevel() == VerbosityMEDIUM LEVEL) { } else { . } } Az egyes

if-else-ágakban az aktuális üzenetnek, nyelvnek és részletességnek megfelel®, grakus szemléltetés- ill. szöveges magyarázat kiadására vonatkozó utasítások találhatóak. Az elágaztatások helyett, esetleg létrehozhattam volna több különböz® osztályt az egyes szinteknek megfelel®en, de akkor azt a lehet®séget veszítettük volna el, hogy futás közben módosítsuk a kezdetben beállított üzemmódot. A futás közbeni üzemmód váltásnak pedig van értelme, hiszen könnyen elképzelhet®, hogy a felhasználó az adott feladat megoldásának különböz® részeit különböz® részletességgel szeretné megtekinteni. Az osztálynak  mivel vállalta, hogy megvalósítja a Runnable interfészt  meg kell határoznia a run() metódust. Ez ilyen egyszer¶en fest ezek után: public void run() { super.getAssignment(); } Akárcsak eddig, a super itt is a szül® osztályt szimbolizálja. Vagyis meghívtam az ®s osztály getAssignment() metódusát, amely

során rendre végrehajtódnak az eljárásba ékelt sendMsgXXX() metódusok. Ezek pedig itt a GAPSThread osztályban, az aktuális futási módnak megfelel® részletességgel generálják üzeneteiket, amelyeket az AssignmentMatrixPanel fogad. Az AssignmentMatrixPanel osztály Az AssignmentMatrixPanel osztályban valósítottam meg azokat a m¶veleteket, amelyek a szakdolgozatban kit¶zött szemléltetéshez szükségesek. Az osztály két legfontosabb vizuális komponense a görgethet® tartókba14 helyezett JTextAreaill. JPanel típusú objektumok El®bbiben a megoldást kísér®, szöveges üzeneteket helyezem el, utóbbiban a grakus ábrázolást végzem. Megjegyzem, hogy a konstruktorban átvett, egészeket tartalmazó költségmátrixot átalakítom karakterláncokat (String) tartalmazó cellákká. Ez azért t¶nt számomra el®nyösebbnek, mert így kényelmesen végezhet®k a cellák tartalmán olyan átalakítások, mint pl. egy 0 megjelölése 0 -vel, vagy éppen egy

0∗ átalakítása 0-vá 14 Egész pontosan a JScrollPane-r®l van szó. 21 Az infoArea elnevezés¶, JTextArea típusú, szöveges üzeneteket tartalmazó komponens kezelése meglehet®sen egyszer¶. A kapott karakterláncot egyszer¶en hozzáf¶zöm a korábbi szöveghez, majd gondoskodom a szöveg automatikus görgetésér®l, a kurzor (caret) szöveg végére helyezésével. Az alapelv itt látható: public void printMsg(String s) { infoArea.append(s); infoArea.setCaretPosition(infoAreagetDocument()getLength()); } A 10. oldalon említett 0∗ -ok visszanyerését az alább látható módon oldottam meg. A független 0-rendszert leíró mátrixot soronként írom ki a komponensre, egyessel jelezve azt, ha az adott nulla eleme a független 0-rendszernek, nullával, ha nem public void printMsg(int []zeroStars) { int x; for(int i = 0; i < n; i++) { x = zeroStars[i]; for(int j = 0; j < n; j++) { if(x == j) { infoArea.append("1 "); } else {

infoArea.append("0 "); } } infoArea.append(" "); } infoArea.append(" "); infoArea.setCaretPosition(infoAreagetDocument()getLength()); } A grakus megjelenítésért felel®s komponens el®készítése valamivel több munkát igényel, de megéri a fáradságot. Az osztály konstruktorában található a következ®, itt csak vázlatosan lejegyzett kódrészlet: drawingPanel = new JPanel() { protected void paintComponent(Graphics g) { super.paintComponent(g); Graphics2D g2D = (Graphics2D)g; if(firstTime) { bufferedImage = (BufferedImage)createImage(size.width, sizeheight); graphics2D = bufferedImage.createGraphics(); . firstTime = false; } }; } g2D.drawImage(bi, 0, 0, this); A drawingPanel komponens paintComponent() metódusát ott helyben felül írtam. Természetesen a rstTime boolean típusú változó kezdetben igaz logikai értékkel bír A Dimension típusú, size elnevezés¶ paraméter átadásakor, a változónak a graka kívánt méretét

kell tartalmaznia. 22 Mire jó ez az egész? Amit ezzel a módszerrel nyerünk az a puerelt graphics2D objektum, amelyre ezután bármikor rajzolhatunk, és újrafestésnél a puer tartalma villódzás nélkül megjelenik a képerny®n.15 Lássunk egy egyszer¶ példát, amely egy vonallal áthúzza a kívánt sort! (Ez a m¶velet a Magyar módszer ötödik lépésében szerepel, segítségével könnyebben számba vehet®k a szabad-, az egyszeresen- ill. kétszeresen lekötött elemek) public void drawLineThroughRow(int row) { int y = topMargin + FONT SIZE + row*(cellHeight + cellVerticalSpace) + cellHeight/2 - 1; int left = leftMargin; int right = left + n*cellWidth + (n-1)cellHSpace - 1; graphics2D.drawLine(left, y, right, y); drawingPanel.repaint(left, y, right-left, y+1); } Megjegyzés Ez az osztály valószín¶leg jól hasznosítható lenne pl. a Szállítási feladat szemléltetéséhez is Az AboutDialog osztály Az osztály egy kis dialógus ablakot kínál fel

nyugtázásra, amelyben a programról és a szerz®r®l közöl pár soros információt. A többi épít®elemt®l való függetlensége indokolja önállóságát Kis módosítással könnyen általánosabbá lehetne tenni, és akkor egy igazán kényelmesen újra hasznosítható komponenst nyernénk. A Verbosity osztály Ez az osztály a gaps csomag legegyszer¶bb darabja, feladata mindössze annyi, hogy segítségével elrejtsük a b®beszéd¶ség (verbosity) szintjeit, tároljuk annak beállítható értékeit. Akárcsak az el®bb, az osztály haszna az implementáció elrejtésben és az újra hasznosíthatóságban keresend®. Jelenleg három jól elkülöníthet® szintet határoztam meg, a Magyar módszerhez igazodva. A három szintnek megfelel®en, a következ® információk kerülnek kiírásra: • a kezdeti költségmátrix, a talált optimális hozzárendelés, az iterációk száma, a teljes költség (indítás után nem igényel felhasználói interakciót) • a

fentiek kiegészítve a mátrix el®készítésével, az átalakítások során kapott mátrixokkal (az egyes lépések megkezdésekor kíván felhasználói interakciót) 15 Ismer®sek a régi, villódzó grakájú awt-s Java animációk? 23 • a fentieken túl az aktuálisan vizsgált sor, oszlop, elem és azok állapota (kötött, szabad, jelölt stb.) A table csomag Ez a csomag a grakus felhasználói felületen keresztül történ® adatbevitelért felel®s, segítségével egészeket tartalmazó mátrixokat lehet bekérni a felhasználótól. Az IntegerField osztály felel®s azért, hogy csak egész értékekkel lehessen feltölteni a mátrixokat. A MyTableEditor a mez®k mátrixba rendezéséért felel®s, míg a MyTableDialog az egész érték¶ mez®ket tartalmazó mátrix megjelenítéséért felel Az érdekl®d® olvasó sok ötletet meríthet pl. a 45 oldalon felsorolt, idevágó leckékb®l A MyTableDialog osztály Ez az osztály a JDialog-ból származik,

viszont az általam megvalósított getValues() metódusán keresztül egészeket tartalmazó mátrixok referenciájának visszaadására is képes. Konstruktorát a következ®re terveztem: public MyTableDialog( } . Frame owner, String caption, int dimensionOfMatrix, int minimumValue, int maximumValue, int defaultValue, String keyI18N, Locale currentLocale ) { Ilyen módon lehet®ség nyílik korlátok közé szorítani-, alapértelmezett értékkel ellátni a bekérend® mátrix elemeit, valamint  a nyelvi beállításoknak megfelel®en  üzenetet kiírni arra vonatkozólag, hogy milyen bemenetet is várunk. Ez az osztály azonban csak egyfajta keretként m¶ködik, a piszkos munkát a következ® osztályok végzik. A MyTableEditor osztály A MyTableEditor osztály már csak az itt látható adatokat kapja meg konstruktorában, amely elegend® is m¶ködéséhez: public MyTableEditor( } . int int int int dimensionOfMatrix, minimumValue, maximumValue, defaultValue 24

) { Ez az osztály beágyazva egy AbstractTableModel osztályt tartalmaz, amely Integer típusú cellák kezelésére van felkészítve. A táblázat fejlécében feltüntetem az oszlopok sorszámát, segítend® az eligazodást nagyobb mátrixokban. Az IntegerField osztály Ez az osztály a JTextField-b®l származik, itt történik az egyes cellák kezelése. Néhány egyszer¶ módszerrel elérhet®, hogy ne fogadjuk el a hibásan formázott karakterláncokat, valamint azokat az egészeket, amelyek a beállított értéktartományon kívül esnek. Ezekben az esetekben jelzem, hogy szabálytalanság történt, valamint beállítom az alapértelmezett értéket az adott cellára. Megjegyzés Az érték szerkesztését nyugtázással kell befejezni (pl. az Enter billenty¶ leütésével, vagy egy másik cellára váltással) 25 Extra funkciók megvalósítása A többnyelv¶ség megvalósítása E funkció megvalósítását az a tény motiválta, hogy ma már nem lehet

eladni igényesebb szoftvereket egyetlen nyelv alkalmazásával. A Java pedig könnyedén lehet®vé teszi több nyelv rugalmas használatát is A program többnyelv¶ségének megteremtését a GAPS osztály következ® beállításaival értem el: private Locale []locales = {new Locale("en", "US"), new Locale("hu", "HU")}; private Locale currentLocale; private ResourceBundle messagesBundle; Majd az alábbi metódust használtam a nyelv megváltoztatására: private void setMyLocale(Locale locale) { currentLocale = locale; messagesBundle = ResourceBundle.getBundle("APMessagesBundle", locale); } Az APMessagesBundle.properties ill APMessagesBundle xx XXproperties nev¶, szöveges fájlok  egyenl®ségjellel elválasztva  kulcsokat és értékeket tartalmaznak. (Pl: Step0=El®készít® lépés) A kulcsnak megfelel® érték kiválasztása pedig például így történhet: String internationalizedString =

messagesBundle.getString("Step0"); A Java api-ban rendelkezésre álló osztályok segítségével a programozó ennél többre is képes lehet. Az éles szem¶ felhasználó meggyelheti ezt, a számokat is magukba foglaló, különböz® nyelv¶ kiírások összevetésekor Pl: Tying the 1 column és A(z) 1. oszlop lekötése16 Ábra és szöveg mentése közvetlenül a programból E funkció kialakításához az AssignmentMatrixPanel a MouseListener és KeyListener interfészeket valósította meg. Amennyiben a fenti panel két ábrázolást végz® komponense birtokolja a fókuszt, és leütjük a megfelel® billenty¶t (s: save), vagy kattintunk az egér adott gombjával (második vagy harmadik), a panelek tartalma mentésre kerül. Az eljárást illusztráló ábrákat png (Portable Network Graphics) formátumban írom fájlba, míg a kísér® leírásokat egy egyszer¶ szöveges fájlként. 16 Lássuk például az egérrel történ® mentésre vonatkozó

kódrészletet! Lehet®ség lenne a nével®k automatikusan helyes kiválasztására, de ezt a többletmunkát ezen a szinten nem vállaltam. 26 public void mouseClicked(MouseEvent me) { int btn = me.getButton(); if(btn == MouseEvent.BUTTON3 || btn == MouseEventBUTTON2) { saveContent(); } } Mivel csak a megfelel® komponensek hallgatóznak egér- és billenty¶ esemény után, ezért nem vizsgálom meg az esemény forrását. Azt viszont le kell kérdeznünk, hogy az egér melyik gombja (vagy melyik billenty¶) váltotta ki az eseményt. A megfelel® esetekben, a saveContent() privát metódust hívom meg, amely lényegét tekintve a következ®: private void saveContent() { File filePIC = new File("matrix.png"); try { ImageIO.write(bi, "png", filePIC); } catch(IOException ioe) { . } } File fileTXT = new File("solution.txt"); try { FileOutputStream fos = new FileOutputStream(fileTXT); fos.write(infoAreagetText()getBytes()); fos.close(); }

catch(IOException ioe) { . } Látható, hogy a grakára alkalmazott technika milyen hasznos, gyakorlatilag egyetlen sorral képesek vagyunk fájlba írni a kívánt tartalmat. Hasonló megoldást kínál a JTextArea is, hiszen a szöveges fájl mentése sem t¶nik bonyolultnak. Dolgozatom 31. oldalától kezdve konkrét példákkal igyekszem illusztrálni ezt a lehet®séget és az el®z® módszert. Megjegyzések A tárgyalt funkció bizonyos el®készületeket igényel, ha a szoftvert applet-ként futtatjuk. A Policytool nev¶ standard Java eszközre lehet szükségünk, amellyel feljogosíthatjuk a programot fájlok írására stb A 45 oldalon található címeken járhatunk a részletek után Az ismertetett m¶ködési módot els®sorban oktatási célból gondolom hasznosnak, mert így tetsz®leges feladat  akár igen részletes  megoldásának ismertetéséhez, nem kell bajlódni az illusztráló ábrák elkészítésével. A gyorsítóbillenty¶k alkalmazása Ezen

lehet®ség legnagyobb nyertesei azok a mozgáskorlátozott emberek, akik képtelenek a számítógépes egér használatára. Azonban mások számára is hasznos lehet ez a funkció. Tapasztalatom szerint, a program teljes érték¶en használható 27 gyorsítóbillenty¶k (ún. mnemonic: alt + a menü elem els® karaktere)-, tab- és navigációs billenty¶k segítségével. Megjegyzem, hogy a mentési lehet®ség az s billenty¶ leütésével érhet® el A nyelvvel dinamikusan változó gyorsítóbillenty¶k beállítása, a fentebb említettek ismeretében, meglehet®sen egyszer¶: String str = menuBundle.getString("XXX"); xxxMenuItem.setText(str); xxxMenuItem.setMnemonic(strcharAt(0)); Beépített példa feladatok A szoftverbe négy beépített példát helyeztem el, amelyek hasznát leginkább a tesztelések során láttam. Kezdetben ui még nem volt adatbevitelre lehet®ség, de ezen példák segítségével már akkor lehetett tesztelni az alapvet®

eljárásokat. Kés®bb pedig, a grakus felhasználói felület hozzávet®leges elkészülte után, nem kellett minduntalan újabb és újabb feladatokat betáplálni ahhoz, hogy a kisebb-nagyobb esztétikai, technikai hibákat kijavíthassam. Ha kés®bb feleslegesnek bizonyulna ez a funkció, nem okoz semmiféle problémát a kódból való eltávolítása. A példákat, az itt látható vázlatnak megfelel®en, a JMenuItem (AbstractButtontól örökölt) doClick() metódusának hívásával indítottam el automatikusan: private void startExample(int i) { switch(i) { case .: costMatrix = new int[][] { {., , }, . {., , } }; break; . } againMenuItem.doClick(); } 28 Technikai részletek Kezdetben egy gnu makele-t használtam a gyakran kiadott parancsok automatizálására, azonban ez Java-ra nem bizonyult olyan hatékonynak, mint pl. a c nyelvre, ezért egy saját shell szkripttel cseréltem fel. Ma már pedig tudom, hogy legközelebb az Ant elnevezés¶ eszközt fogom

használatba venni.17 A szoftver fájlokba szervezése A fejlesztés során, ahogy n®tt a szoftver mérete, hamar eljött az az id®, hogy elkezdtem a rendszert struktúrálni. Az alábbi könyvtárszerkezetet hoztam létre, a fejlesztés f®könyvtárában: ./bak ./classes ./doc ./html ./messages ./src A bak könyvtár a módosítás el®tti, tömörített formátumú mentéseket tartalmazza (BAcK-up). Tömörítéshez a zip programot használtam, mert tapasztalatom szerint ez található meg a legtöbb rendszeren, így a mentés is hordozhatóbb. A clas- ses könyvtár kezdetben a manifest.mf elnevezés¶ fájlt tartalmazta, amely a jar fájl m¶ködéséhez szükséges, majd ebbe a könyvtárba kerültek a lefordított osztályok (class-ok). A doc könyvtár a programozó számára tartalmaz hasznos információkat: mi a következ® fontos feladat, tapasztalt hibák stb. A html könyvtárban az applet m¶ködéséhez szükséges oldalakat és a szoftverhez tartozó leírásokat

helyeztem el, html formátumban. A programban olvasható, idegen- és magyar nyelv¶ üzeneteket tartalmazó fájlokat messages bejegyzés alatt találjuk. A src könyvtár a forráskódot rejti az ap, gaps és table alkönyvtárak alatt. A szoftver fordítása A programot a fejlesztés f®könyvtárából az alábbi módon fordíthatjuk le, majd csomagolhatjuk össze egy jar fájlba: javac -deprecation -sourcepath src src/*/.java -d classes cp messages/*.properties classes/ cd classes jar cmf MANIFEST.MF gapsjar */.class *.properties 17 Kedves olvasó, te ne járd végig feleslegesen a fenti utat! 29 A HTML-oldal beállításai A html-oldal testébe, minimálisan az alábbiakat kell írnunk ahhoz, hogy web-es felületen keresztül is m¶ködtethessük a programot: <applet code="gaps/GAPSStarter" archive="gaps.jar" width=250 height=50 </applet> Természetesen ebben az esetben, a html-oldalt tartalmazó könyvtárba kell helyeznünk a fent

elkészített jar fájlt. 30 A szoftver m¶ködés közben, tesztelés Be van fejezve a nagy m¶, igen. A gép forog, programozó tesztel. A Java nyelvnek  platform-függetlensége révén  kétségtelenül megvan az az el®nye, hogy csak egy kódot kell karban tartani. Nem kell minden egyes cél operációs rendszerre, szoftveres környezetre kódrészleteket kidolgozni Általában azonban a programozó ekkor sem úszhatja meg azt, hogy tesztelje programját a lehet® legváltozatosabb környezetekben. A szoftver tesztelését, a minimálisan szükséges 1.4-es verziójú jre (Java Runtime Environment  Java Futtató Környezet) megléte mellett, az alábbi szoftverkörnyezetekben végeztem: • Windows98 (Internet Explorer 5.0 és IE 60, FireFox 08, Mozilla böngész®k), • Windows2000 Professional (Internet Explorer 6.0, Netscape 71 böngész®k), • Red Hat Linux 9.0 (Gnome, kde, twm ablakkezel®k és Mozilla 121, Konqueror 31-12 böngész®k) A szoftver az elvárt

módon, sikerrel m¶ködött minden esetben. A jelenlegi változatban nem tapasztaltam rendellenes m¶ködést18 Linux alatt fejleszt®knek talán a twm ablakkezel®t ajánlanám fejlesztéshez, mert puritánsága miatt, ui. ami ott m¶ködik, az szinte biztos, hogy a többi ablakkezel® menedzser alatt is jól fog viselkedni. Személyes tapasztalatom, hogy pl a modális (dialógus) ablakokat nem az api dokumentációban leírtaknak megfelel®en használva, mindegyik fent felsorolt rendszer saját kezébe vette a menedzselést, kivéve a twm. Ennek megfelel®en nem volt könny¶ eldöntenem, hogy hol a hiba: az ablakkezel®ben vagy a programomban. Végül szerencsésen 19 ráakadtam a megoldás kulcsára, és megszüntettem egy kellemetlen problémát, amely csak twm használata esetén jelentkezett. A következ®kben két kisebb méret¶ példán keresztül mutatom be programom m¶ködését. Illusztrálom a különböz® nyelvek használatának lehet®ségét, a különböz®

részletesség¶ magyarázatokat, és a beépített példák használatát. A képaláírásokat és a kiemelt szövegeket a program állította el®. 18 19 Természetesen korábbi fázisokban mutatkoztak hibák, amelyeket folyamatosan javítottam. A kitartó munkával pontosabb meghatározás lenne. 31 Els® példa A beállítások között a magyar nyelvet és a részletes magyarázatokat választva, majd a második beépített példa megoldását elindítva20 , a következ® szemléltet® ábrákat és magyarázatokat menthetjük el magából a programból.21 A megoldandó feladat költségmátrixát a 4. ábrán láthatjuk 4. ábra El®készít® lépés A kezdeti költség mátrix A költségmátrix el®készítése megkezd®dött. Az els® fázis után (sor-minimumok kivonása a sorokból) 2 3 1 0 1 1 0 2 1 2 0 0 1 1 0 0 2 1 0 2 1 0 2 3 2 A második 2 1 0 0 1 fázis után (oszlop-minimumok kivonása az oszlopokból) 3 0 0 1 0 1 1 2 0 0 1 0 2 0 0 2 0 1 3 2 A

költségmátrix el®készítése befejez®dött. Itt a független 0-rendszer kialakítására vonatkozó információk következnek. A leírásból látjuk, hogy oszlopfolytonosan halad a keresés. A magyarázat tartalmazza, hogy az eljárás melyik oszlopban és melyik sorban tart, vagy ha újabb független nullát vett fel a rendszerbe. A független nulla-rendszer elkészítése megkezd®dött. 20 21 A példa megtalálható [2] jegyzetben is. Az itt látható ábrák és leírások csak egy részét képezik a teljes szemléltetés folyamatának. 32 . A(z) 3. oszlop vizsgálata A(z) 1. sor vizsgálata A független nulla a(z) [1][3] helyen nulla-csillag lesz. Az els® független 0-rendszer az 5. ábrán található 5. ábra A független nulla-rendszer elkészítése A nulla-csillag elemek Ezen a ponton az oszlopok lekötése következik, amelyet a 6. ábra mutat be A(z) 1. oszlop lekötése A(z) 2. oszlop lekötése A(z) 3. oszlop lekötése A(z) 4. oszlop lekötése Az

oszlopok lekötése befejez®dött. 6. ábra Els® lépés Az oszlopok lekötése befejez®dött Ekkor megkezd®dik a szabad nullák keresése: 33 Második lépés (szabad nullák keresése sorfolytonosan) A szabad nullák keresése megkezd®dött. A(z) 1. sor vizsgálata A(z) 1. sor nincs lekötve A(z) 1. oszlop vizsgálata A(z) 1. oszlop le van kötve . Szabad nulla a(z) [3][5] pozíción. A 7. ábrán, a harmadik lépést szemlélteti a program (vö a 6 ábrával!) 7. ábra Harmadik lépés (sor lekötése, oszlop felszabadítása) A(z) [3][5] pozícióban lev® szabad nulla vessz®vel megjelölése. A(z) 3 sor lekötése A(z) 1 oszlop felszabadítása, mely a nulla-csillag oszlopa volt. Ezután folytatódik a szabad nullák keresése: Második lépés (szabad nullák keresése sorfolytonosan) A szabad nullák keresése megkezd®dött. A(z) 1. sor vizsgálata A(z) 1. sor nincs lekötve A(z) 1. oszlop vizsgálata A(z) 1. oszlop nincs lekötve . Szabad nulla a(z) [4][1]

pozíción. Harmadik lépés (sor lekötése, oszlop felszabadítása). A(z) [4][1]. pozícióban lev® szabad nulla vessz®vel megjelölése A(z) 4. sor lekötése A(z) 4. oszlop felszabadítása, mely a nulla-csillag oszlopa volt Tovább folytatódik a szabad nullák keresése: Második lépés (szabad nullák keresése sorfolytonosan) . Szabad nulla a(z) [1][4] pozíción. Harmadik lépés (sor lekötése, oszlop felszabadítása). A(z) [1][4]. pozícióban lev® szabad nulla vessz®vel megjelölése A(z) 1. sor lekötése A(z) 3. oszlop felszabadítása, mely a nulla-csillag oszlopa volt 34 Még mindig folytatódik a keresés, de végül nem találunk szabad nullát, ezért az ötödik lépéssel (a költségmátrix speciális átalakításával) folytatódik az eljárás (ld. a 8 ábrát!) Második lépés (szabad nullák keresése sorfolytonosan) . A(z) 5. sor vizsgálata A(z) 5. sor nincs lekötve A(z) 1. oszlop vizsgálata A(z) 1. oszlop nincs lekötve . A(z) 5. oszlop

vizsgálata A(z) 5. oszlop nincs lekötve A szabad nullák keresése befejez®dött. 8. ábra Ötödik lépés (költségmátrix átalakítása) A szabad elemek minimuma: 1 Felsorolva láthatjuk, hogy melyik elem van kétszeresen lekötve és mely elemek szabadok. Itt ilyen sorokat találunk: A(z) [.][] kétszeresen lekötött elem kijelölése növelés céljából A(z) [.][] szabad elem kijelölése csökkentés céljából Majd kapjuk az átalakított költségmátrixot (9. ábra) Az átalakítások után folytatódik a keresés, amely után a harmadik lépés következik. Második lépés (szabad nullák keresése sorfolytonosan) A szabad nullák keresése megkezd®dött. A(z) 1. sor vizsgálata A(z) 1. sor le van kötve A(z) 2. sor vizsgálata A(z) 2. sor nincs lekötve A(z) 1. oszlop vizsgálata A(z) 1. oszlop nincs lekötve Szabad nulla a(z) [2][1] pozíción. 35 9. ábra A költségmátrix átalakítás után Harmadik lépés (sor lekötése, oszlop felszabadítása).

A(z) [2][1]. pozícióban lev® szabad nulla vessz®vel megjelölése A(z) 2. sor lekötése A(z) 2. oszlop felszabadítása, mely a nulla-csillag oszlopa volt Majd tovább folytatódik a szabad nullák keresése, amelyet a negyedik lépés, a lánckészítés m¶velete követ (ld. a 10 ábrát!) Második lépés (szabad nullák keresése sorfolytonosan) A szabad nullák keresése megkezd®dött. . Szabad nulla a(z) [5][1] pozíción. 10. ábra Negyedik lépés (lánckészítés) A(z) [5][1] pozícióban lev® nulla megjelölése Nullacsillag a(z) [3][1] pozícióban Nulla-vessz® a(z) [3][5] pozícióban 36 A leírásból láthatjuk, a lánckészítés befejez®dött, majd azt, hogy az új költségmátrix elkészítése megkezd®dött. Ezt követ®en a mátrix elemek vizsgálata következik (11. ábra) Mátrix elem vizsgálata a(z) [1][4]. pozícióban A vizsgált nulla-vessz® nem volt a láncban, ezért szabad nulla lesz bel®le. . Mátrix elem vizsgálata a(z) [2][1].

pozícióban A vizsgált nulla-vessz® nem volt a láncban, ezért szabad nulla lesz bel®le. . Mátrix elem vizsgálata a(z) [3][1]. pozícióban A vizsgált nulla-csillag a láncban volt, ezért szabad nulla lesz bel®le. . Mátrix elem vizsgálata a(z) [3][5]. pozícióban A vizsgált nulla-vessz® a láncban volt, ezért nulla-csillag lesz bel®le. Mátrix elem vizsgálata a(z) [4][1]. pozícióban A vizsgált nulla-vessz® nem volt a láncban, ezért szabad nulla lesz bel®le. . 11. ábra Mátrix elem vizsgálata a(z) [5][1] pozícióban A vizsgált nulla-vessz® a láncban volt, ezért nulla-csillag lesz bel®le. Az átalakítások után az új és egyben végs® költségmátrixot kapjuk (12. ábra), amely kijelöli a független 0-rendszert is. Végül: Els® lépés (független nulla-rendszer kialakítása) Optimális hozzárendelést találtam. 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 Az elvégzett iterációk száma = 1 A teljes költség = 12 Vége 37 12.

ábra Az új költségmátrix elkészítése befejez®dött Második példa Most lássunk egy igen kis méret¶, de a Magyar módszer számára érdekes feladatot! A vázlatos magyarázatok angol nyelv¶ek. Ismét, a magyarázó szövegeket és szemléltet® ábrákat a programból  egy-egy gombnyomással  mentettem el. A megoldandó Hozzárendelési feladat költségmátrixa a 13. ábrán látható 13. ábra A második példában szerepl® kiindulási költségmátrix Step #0 (pre-condition) The initial cost matrix: 1 2 3 5 Pre-conditioning of cost matrix has been started. After first phase (subtracting row-minimums from rows) 0 1 0 2 After second phase (subtracting column-minimums from columns) 0 0 0 1 Pre-conditioning of cost matrix has been finished. Making of independent zero-system has been finished. 38 Step #1 (create independent zero-system) Step #2 (search for free zeros) Step #3 (tie row, untie column) Step #2 (search for free zeros) Step #4 (make chain) Making of

chain has been finished. 0* 0 0 1 A lánckészítés utáni állapotot a 14. ábrán láthatjuk 14. ábra A lánckészítést mutató ábra Re-making of cost matrix has been finished. 0 0* 0* 1 Step #1 (create independent zero-system) An optimal assignment was found 0 1 1 0 Number of iterations = 1 The total cost = 5 The End A 15. ábrán szerepl® végs® költségmátrix jelöléseib®l leolvasható az optimális megoldás, amelyet fentebb a szövegben is láthatunk. 15. ábra A második példában szerepl® feladat végs® költségmátrixa 39 Összefoglalás Szakdolgozatom kit¶zött témája az operációkutatásból jól ismert Hozzárendelési feladat, Magyar módszerrel megvalósított számítógépes megoldása és az eljárás szemléltetése volt. A feladatot sikeresen oldottam meg Java programozási nyelven, s®t a nyilvánvaló elvárásokon túl (helyes m¶ködés, futásidej¶ feladatok kezelése), már a tervezés során több el®nyös szempontot is

gyelembe vettem. A megvalósított szoftver: • végrehajtható kód szintjén platform- ill. architektúra-független, • önállóan és web-böngész® segítségével, hálózaton keresztül is m¶ködtethet®, • többnyelv¶ grakus felhasználói felülettel rendelkezik, • több üzemmódban képes a feladatok kezelésére (a megoldásokat kísér® üzenetek és a grakus szemléltetés részletességét tekintve), • szemléltet® ábrái és leírásai a programból menthet®k, • grakus szemléltetése h¶ egyetemi jegyzetünk jelöléseihez[2], • egérrel és billenty¶zetr®l (gyorsítóbillenty¶k segítségével) is vezérelhet®. A fejlesztéshez, a Sun jóvoltából ingyenesen elérhet® Java szoftverfejleszt® eszköztár, jelenleg legfrissebb 1.41 02-es változatát használtam, Red Hat Linux 90 operációs rendszer alatt. A több, mint 3000 sornyi forráskód szerkesztéséhez, az igen hatékony gvim szövegszerkeszt®t használtam. Nem vettem igénybe

ún Gyors Alkalmazás-Fejleszt® eszközök segítségét, azért hogy minél mélyebb ismeretekre tehessek szert a Java nyelv¶ programozás területén. A megvalósított szoftvert széles kör¶en teszteltem, az 1.4-es verziójú Java Runtime Environment jelenlétében A teszteléshez tankönyvi példákat használtam, a környezetemben elérhet® (legelterjedtebb) szoftverkörnyezetekben. A végs® tesztek során nem tapasztaltam rendellenes m¶ködést, mindvégig megbízhatóan, az elvárásoknak megfelel®en m¶ködött. 40 A célkit¶zések mindegyikének eleget tettem, hiszen a szakdolgozatom részeként megvalósított, és itt részletesen ismertetett szoftver helyesen oldja meg a  grakus felszínen keresztül megadható  Hozzárendelési feladatokat, Magyar módszerrel. Programom az eljárás során kívánság szerinti részletességgel (3 szint) és nyelven (magyar, angol) jellemzi szövegesen, valamint szemlélteti grakusan az adott lépést. Az applet 

ideiglenes  elérhet®sége a következ®: http://www.studu-szegedhu/SzilardAndras/gaps/gapshtml Mivel a fenti oldal id®vel megsz¶nik, javaslom a Graphic Assignment Problem Solver kifejezés használatát kedvenc web-es keres®jében, hogy rátaláljon a bemutatott programra, vagy annak segítségével szerz®jére. 41 Irodalomjegyzék [1] IMREH Balázs. Kombinatorikus optimalizálás Novadat, 1999, Gy®r [2] IMREH Balázs. Operációkutatás JATEPress, 2000, Szeged (Újabb, átdolgozott kiadása: BAJALINOV Erik, IMREH Balázs Operációkutatás. SZTE Bolyai Intézet, 2001, Szeged) [3] Bruce ECKEL. Thinking in Java  3rd ed, rv 40 http://wwwmindviewnet/ Books/TIJ 42 Nyilatkozat Alulírott Szilárd András, programozó matematikus szakos hallgató, kijelentem, hogy dolgozatomat a Szegedi Tudományegyetem, Informatikai Tanszékcsoport Alkalmazott Informatikai Tanszékén készítettem, programozó matematikus diploma megszerzése érdekében. Kijelentem, hogy a dolgozat

saját munkám eredménye, és csak a hivatkozott forrásokat (szakirodalom, eszközök stb.) használtam fel Tudomásul veszem, ha szakdolgozatom a Szegedi Tudományegyetem könyvtárában, a kölcsönözhet® könyvek között helyezik el. Szeged, 2004. április 30 Szilárd András 43 Köszönetnyilvánítás Szívb®l jöv® köszönetet mondok Szaniszló Erikának, amiért mindvégig támogatott és ötleteivel javította a dolgozatot. 44 Függelék Források a WWW-n A Java programozási nyelvvel kapcsolatos oldalak http://java.suncom Legjobb a forrásnál kezdeni http://java.suncom/j2se/150 A Sun legújabb Java fejleszt®i eszköze http://java.suncom/applets A Sun applet-gy¶jteménye http://java.suncom/docs/books Java dokumentumok a Sun-tól http://java.suncom/docs/books/tutorial Java leckék a Sun-tól http://java.suncom/docs/books/tutorial/uiswing Java Swing leckék a Sun-tól http://java.suncom/docs/books/tutorial/uiswing/components/table html Java Swing JTable

leckék a Sun-tól http://java.suncom/j2se/142/docs/tooldocs/windows/policytool A Sun Policytool-ról írt dokumentációja Algoritmusok szemléltetésével kapcsolatos oldalak http://sziami.csbmehu/~gsala/alg anims Algoritmusok szemléltetése http://users.iemsnwuedu/~swann/assignhtml Egy oldal a Hozzárendelési feladatról http://www.magiclogiccom/assignmenthtml Egy másik oldal a Hozzárendelési feladatról http://www unix.mcsanlgov/otc/Guide/CaseStudies/qap A kvadratikus Hozzárendelési feladatról Operációkutatással kapcsolatos oldalak http://www.euro-onlinecom Operációkutatás Európában http://www.horshu Operációkutatás Magyarországon 45