State osztály

A fejlesztésben részt vevő hallgatók kérésének megfelelően a jegyzetben szereplő rendszer Java nyelven lett implementálva. Ennek megfelelően az összes programrészletet ezen a nyelven mutatjuk be. A programrendszer írása során, már a kezdetektől több szempontot is figyelembe vettünk. Ezek a következők:

  • A kapott kód legyen hatékony!

  • A forráskód legyen könnyen megérhető, hogy felhasználhassuk az oktatásban!

  • Használjuk ki az objektumorientáltságot, hogy minél kevesebbet kelljen ismételni magunkat!

Elterjedt megoldás algoritmusokat pszeudokódban ismertetni. Ekkor természetesen az algoritmuson van a hangsúly, az implementációval kapcsolatos kérdéseket a szőnyeg alá lehet seperni. Mi ebben a jegyzetben viszont szemben megyünk ezzel az irányzattal, teljes programrendszert publikálunk, a forráskód minden sorát beleértve.

Lassan harminc évre tekint vissza a literate programming stílus, mely sajnos nem került be a fő áramlatba, és így a dokumentáció és a forrás szoros összekapcsolása teljes hatékonyságában nem oldható meg. Mi egy részleges megvalósítását használtuk a jegyzet elkészítése során, ami a pylit elnevezésű rendszer. Ez, és a pandoc formázó rendszer teszi lehetővé, hogy a fordító számára ehető forrás automatikusan bekerüljön a jegyzetbe, így csökkenthessük a sajtóhibák számát, illetve a kód rendszeres felülvizsgálatával összhangban a jegyzet is frissüljön.

Mivel tucatnyi módszer több variánsa is leírásra kerül, ezért az adatszerkezeteinkhez kapcsolódóan igen sok metódust kell szerepeltetnünk. A könnyebb érhetőség, és a minél általánosabb módszerek megadása érdekében az adatszerkezet leírását három részre bontottuk.

2.3. ábra - State és bővítéseinek osztálydiagramja

State és bővítéseinek osztálydiagramja

A State absztrakt osztály a legáltalánosabb ezek közül. Itt az aktuális állapot környezetét használhatjuk kizárólag. Gondoljunk például a huszártúrára, amikor a lépéssorozat közbenső lépését nem változtathatjuk meg, csak újabb lépésekkel bővíthetjük, vagy az utolsó lépést visszavehetjük. Egyszerűbb keresési módszerek esetén elegendő az adatszerkezet megadásakor csak az itt szereplő metódusokat implementálni.

Miután az állapottér egyes állapotait szeretnénk egymással összehasonlítani, esetleg állapotok egy sorozatát sorba rendezni, így támaszkodunk a Java által biztosított Comparable osztályra, melyhez majd a konkrét megvalósításnál meg kell adnunk egy compareTo metódust.

package hu.unideb.inf.optimization.methods;
/**
 * Absztrakt osztály az általános adattípus tárolására
 * @author ASZALÓS László
 */
public abstract class State implements Comparable<State> {

Természetesen alapfeladat az aktuális állapothoz tartozó függvényérték kiszámítása.

/** Adatszerkezethez tartozó célfüggvényérték kiszámítása */
public abstract void calculate();

A calculate metódus kiszámolja a célfüggvény értékét, de nem adja vissza. Erre az alábbi metódust kell használnunk. Ennek a szétválasztásnak az a haszna, hogy így csak egyszer számoltatunk, de akárhányszor felhasználhatjuk a kiszámolt értéket. Az viszont a mi felelősségünk, hogy a módszereinkben a getValue minden egyes felhasználását megelőzze a függvényérték kiszámítása.

/**
 * Adott állapothoz tartozó célfüggvényérték.
 * @return célfüggvény értéke
 */
public abstract int getValue();

Az előbbi módszer elnevezése már utal arra, hogy szükségünk van egy attribútumra, mely az aktuális állapothoz tartozó célfüggvény-értéket tartalmazza. A diszkrét feladatok alapján feltesszük, hogy feladatainkban az egész típus megfelelő függvényértéknek.

private int value;

A keresések jelentős része lokális keresés. Ekkor az aktuális állapot szomszédai közül kell egy megfelelő állapotot kiválasztani. Természetesen érdemes tudni, hogy az aktuális állapotnak hány szomszédja van. Vigyázzunk viszont arra, hogy ez az érték nem feltétlenül konstans. A huszártúra során a sarokban csak 2 szomszéd van, míg a tábla közepén akár 8 is!

/** Szomszédok száma
 * @return szomszédok száma
 */
public abstract int numberOfNeighbours();

Valamint az is fontos, hogy az aktuális állapotot fel tudjuk cserélni valamely szomszédos állapottal:

/**
 * Az aktuális állapotból átlép a megadott szomszédba.
 * @param neighbour szomszéd azonosítója
 */
public abstract void chooseNeighbour(int neighbour);

Ezek után lényegében már csak technikai metódusok szerepelnek. Az egyik ilyen a felhasználó által megadott adatszerkezet alaphelyzetbe állítása, vagy másképp fogalmazva törlése.

/** Adatszerkezet kitakarítása, kezdőállapotba állítás */
public abstract void clean();

Nagyon gyakran a szomszédos állapotot az aktuális állapot másolatából állítjuk elő, illetve igen gyakran az is előfordul, hogy az aktuális állapotot el kell menteni. A Java egy sima másolásnál csak rejtett mutatókat állítgat, így a másolat megváltoztatásakor az eredeti is megváltozik, szándékunk ellenére. Épp ezért alkalmazzuk a deep copy-t.

A megszokott clone metódus helyett a copy névű metódussal jelöljük, hogy a felhasználó döntésén múlik, mi az amiről valódi másolat készül. A későbbiekben ismertetett Cluster osztálynál a Groups osztály valóban másolódik, míg a Matrix részre csak mutatókon keresztül hivatkozunk.

/**
 * Az aktuális állapotról egy másolatot adunk vissza.
 * @return aktuális állapot másolata
 */
public abstract State copy();

Speciális feladattípusoknál az aktuális és valamely szomszédos állapothoz tartozó célfüggvényérték különbsége meghatározható anélkül, hogy a célfüggvények értékét ki kelljen számolni. Ebben az esetben az alábbi metódus alkalmazásával számítási időt takaríthatunk meg. Ha ez nem teljesül, akkor a konkrét megvalósításnál ki kell számolni a két függvényértéket, és vissza kell adni a különbségüket. Ha x jelöli az aktuális állapotot, és y a neighbour-adik szomszédot, akkor ez a metódus visszaadja az f(y)-f(x) értékét. Miután alapvetően minimalizálási feladatokkal dolgozunk, számunkra az lesz a jó, ha ez a függvény negatív értékkel tér vissza, azaz a szomszéd kedvezőbb, mint az aktuális állapot.

/**
 * Adott sorszámú szomszéd és aktuális állapot célfüggvényeinek különbsége.
 * @param neighbour
 * @return célfüggvényértékek különbsége
 */
public abstract int diffNeighbour(int neighbour);

A módszerek nagy részénél szerepet kap a véletlen, például igen gyakran véletlen kezdőállapotból indítjuk a módszereket. Ehhez kapcsolódik az alábbi módszer.

/** Adatszerkezet véletlen feltöltése */
public abstract void fillRandom();

Az egyes megoldások összehasonlításában sokat segíthet, ha sikerül azokat valami hasonló alakra hozni. Például az előbb említett huszártúra esetén tekintsük azokat a megoldásokat, melyek az a1 mezőről indulnak, és a c2 mezőre lépnek elsőként. Az ilyen egységesítésekre az alábbi metódust használhatjuk:

/** Adatok egységesítése */
public abstract void normalize();
}