StateR osztály

A feladatok jelentős részénél az állapottér eleme több módon is megváltoztatható. Ha a 8 királynő problémájára gondolunk, a királynők egymástól függetlenül mozgathatók. Ennek megfelelően az aktuális állapot környezetét felbontjuk szűkített környezetekre. Azaz ha a 8 királynő feladatában szomszédos állapotot jelent az, ha valamely királynőt elmozdítjuk a saját oszlopában, akkor egy konkrét szűkített környezetbeli szomszédos állapotokat jelent, ha csak a 3. királynőt mozgatjuk.

Ebben az osztályban azokat a metódusokat írjuk elő, melyek a szűkített környezetek kezeléséhez szükségesek. Természetesen ez az osztály az előbb megadott osztály kiterjesztése:

package hu.unideb.inf.optimization.methods;
/**
 * Absztrakt adattípus a szűkített környezetek ábrázolására.
 * @author ASZALÓS László
 */
public abstract class StateR extends State{

Nagyon gyakran az adatszerkezet minden elemét megváltoztathatjuk. Ekkor a szűkített környezetek száma és az adatszerkezet mérete egybeesik. Viszont elképzelhető olyan eset is, amikor ez nem teljesül. Erre felkészülve egy külön metódus adja meg az aktuális állapot szűkített környezeteinek a számát.

/**
 * Szűkített környezetek száma.
 * @return környezetek száma
 */
public abstract int numberOfRestrictedNeighbours();

Szükségünk van a hagyományos szomszédok és szűkített szomszédok közti ide-oda váltásra. Azaz ha megadjuk az x aktuális állapot N(x) környezete egyik elemének sorszámát, akkor kíváncsiak vagyunk, hogy ez melyik Ri szűkített környezethez tartozik,

/** Megadja, hogy az <code>index</code> sorszámú szomszéd melyik
 * szűkített környezetben található
 * @param index szomszéd sorszáma
 * @return szűkített környezet azonosítója
 */
public abstract int getRestrictedNeighbour(int index);

valamint, hogy ebben a környezetben milyen azonosítóval hivatkozhatunk rá.

/** Megadja, hogy az <code>index</code> sorszámú szomszéd a
 * szűkített környezet melyik eleme lesz
 * @param index szomszéd sorszáma
 * @return elem azonosítója
 */
public abstract int getRestrictedNeighbourValue(int index);

Minden szűkített környezetnek van mérete, az azt alkotó elemek száma.

/**
 * <code>index</code> azonosítójú szűkített környezet mérete.
 * @param index szűkített környezet
 * @return környezet mérete
 */
public abstract int sizeOfRestrictedNeighbours(int index);

Természetesen az adatszerkezetünkből azt is vissza szeretnénk kapni, hogy az aktuális állapot az index-edik szűkített környezetben hányadik elemet tartalmazza.

/**
 * Szűkített környezet <code>index</code> azonosítójához tartozó
 * aktuális érték
 * @param index környezet azonosítója
 * @return aktuális érték
 */
public abstract int getRestrictedValue(int index);

Nem csak lekérdezni, hanem beállítani is szeretnénk ezeket az értékeket.

/**
 * Szűkített környezetben érték beállítása
 * @param index környezet azonosítója
 * @param value érték
 */
public abstract void setRestrictedValue(int index, int value);

A célfüggvény lehet annyira speciális, hogy az egyes szűkített környezetre számolt értékek összegeként áll elő. Ez azért jó, mert ha adott szűkített környezet egy elemét tekintjük, akkor a célfüggvényértékek különbségét nagyon könnyen számíthatjuk, ami felgyorsíthatja a program futását. Mivel ezt a metódust csak a MinMaxTools osztály és annak variánsa használja, amikor ez a kedvező tulajdonság nem teljesül a feladatunkra, konkrét interpretációnak nyugodtan megadhatunk egy konstansfüggvényt.

/**
 * Célfüggvényérték leszűkítése adott szűk környezetre
 * @param index szűkített környezet azonosítója
 * @return célfüggvény-részlet
 */
public abstract int conflicts(int index);

A gyakorlatban nekünk sokat segített, ha nem csak egy konkrétan beállított állapot valamely szűkített környezetéhez tartozó célfüggvény-részletet számolhatjuk ki, hanem már a szűkített környezet egy szomszédos eleméhez tartozó célfüggvény-részletet is.

/**
 * Célfüggvény érték leszűkítése adott szűk környezetre és
 * lehetséges értékre
 * @param index szűkített környezet azonosítója
 * @param value lehetséges érték
 * @return célfüggvény-részlet
 */
public abstract int possibleConflicts(int index, int value);

Ha az x aktuális állapot index-edik szűkített környezetének értékét value-ra változtatva kapjuk y-t, akkor az alábbi metódus megadja f(y)-f(x) értékét. Jobb esetben ez a metódus a megelőző kettőn alapszik:

/**
 * Adott szűkített környezet és lehetséges érték által meghatározott állapot
 * és aktuális állapothoz tartozó célfüggvényértéket különbsége
 * @param index szűkített környezet azonosítója
 * @param value lehetséges érték
 * @return célfüggvényértékek különbsége
 */
public abstract int diffRestrictedNeighbour(int index, int value);

Néhány módszernél az aktuális állapottól bizonyos mértékben el kell térni. Nem csak valamelyik szomszédos elemet kell kiválasztani, hanem százalékos mértékben eltávolodni az aktuális állapottól. Ezt jellemzően a következő módon valósítjuk meg: minden szűkített környezetben a megadott eséllyel egy szomszédos elemet választunk. Mivel a szűkített környezetek jellemzően ortogonálisak egymásra, így az egymást követő szomszédra lépések jócskán képesek eltávolítani az aktuális állapottól.

/**
 * Az adatszerkezetünket véletlenszerűen megváltoztatjuk.
 * @param r mutáció foka
 */
public abstract void mutate(float r);
}