6. fejezet - Speciális keresési módszerek

Tartalom

Összevonás mint keresési módszer
Összevonás segédosztálya
Összevonások módszere
Összevonás variáns segédosztálya
Összevonás variáns
Kombinált módszerek
Minimális konfliktusok és összevonás
Max-min konfliktusok és összevonás
Max-min variáns és összevonás
Feladatok

Az általános módszerek mellett léteznek speciális módszerek is. A fejezet következő részében bemutatunk pár ilyen, a szerzőktől származó módszert, melyek speciálisan a partíciók problémájának megoldására születtek.

Összevonás mint keresési módszer

A korábbi módszerek jelentős része apró változásokkal operált. Kiváló példa erre a lokális keresések bármelyike, egy-egy helyen változtatta meg az állapotot. Tekintsünk egy ettől teljességgel eltérő irányt! Nézzük meg, hogy van-e értelme két partíciót összevonni! Először is vizsgáljuk meg, hogy mitől függ két partíció összevonásának a haszna. Ha egy-egy partíción belüli csúcsok között - kapcsolat van, akkor az beleszámít a célfüggvény értékébe is. Ha a két partíciót összevonjuk, akkor ez a kapcsolat továbbra is megmarad, és továbbra is beleszámít a célfüggvény értékébe. Azaz az összevonás tekintetében ez nem számít. Ha két belső csúcs között + kapcsolat van, akkor az nem számít konfliktusnak, nem kell számolni vele. Nézzünk két olyan csúcsot, ahol az egyik az egyik partícióban van, míg a másik a másikban. Ha köztük + kapcsolat van, akkor amíg két külön partícióról beszélünk, addig ez konfliktust jelent, viszont összevonás után már nem! Ha eredetileg - kapcsolat van köztük, akkor az összevonás előtt nem jelent konfliktust, viszont összevonás után már konfliktusnak fog számítani.

Ha összegezzük az elhangzottakat, akkor a két külön partícióba eső csúcs között pozitív él volt, akkor összevonással csökken a konfliktusok száma, míg negatív él esetén nő. Ezért tekintsük a két partíció közti összes negatív és pozitív élek számát, és ha több a pozitív él mint a negatív, akkor van értelme összevonni.

Könnyedén előfordulhat az is, hogy van több partíció, amit páronként érdemes összevonni, de összest egy partícióvá alakítani már nem. Ezért a módszerünket mohó algoritmusként tervezzük meg, mindig azt az összevonást hajtjuk végre először, amely leginkább csökkenti az állapothoz tartozó célfüggvény-értéket.

A módszer fontos eleme az összevonás hasznosságának kiszámítása. Ezt újra és újra megtehetjük minden lépés előtt, vagy akár el is tárolhatjuk az értéket, ám ekkor gondoskodni kell azok karbantartásáról. A módszer változataként bemutatunk egy kísérleti köztes megoldást is.

6.1. ábra - Összevonás módszereinek osztálydiagramja

Összevonás módszereinek osztálydiagramja

Összevonás segédosztálya

A segédosztály tárolja a következő összevonáshoz szükséges információkat. Jelen állapotban minden egyes összevonás után ezeket az adatokat újraszámolja a program. Megfelelő adatszerkezetek használatával ez az újraszámolás részben megspórolható.

package hu.unideb.inf.optimization.methods;
import hu.unideb.inf.optimization.clustering.Cluster;
/**
 * Elvégzi az összevonásokat, és megkeresi az összevonás helyét
 * @author ASZALÓS László
 */
public class ContractTools {

Szükségünk van az i. és j. csoport közti élek előjeles számára minden i és j pár esetén:

protected int t[][] = null;

A t mátrixban eddig talált legnagyobb elemről feljegyezzük annak indexeit, valamint az értékét:

private int maxI;
private int maxJ;
private int maxV;

Az összevonást valójában a Cluster osztály egy metódusa valósítja meg:

void contract(Cluster x){
    x.substitute(maxJ, maxI);
}

Annak érdekében, hogy a t tömb legnagyobb elemét meghatározzuk, először is fel kell tölteni a tömböt. Ezt a Cluster osztály error metódusa teszi meg nekünk.

Ezután nincs más dolgunk, mint a szimmetrikus tömb egyik felén végigmenni, és a maximális elemét megkeresni. Elsőként a tömb első (nem átlón szereplő) elemét jegyezzük fel. Miután bejártuk az egész tömböt, a legnagyobb elem értékét adjuk vissza.

public int getMaxValue(Cluster x) {
    t = x.errors();
    if (1== t.length) {return 0;}
    maxI = 0;
    maxJ = 1;
    maxV = t[0][1];
    int temp = t.length;
    for (int i = 0; i < temp; i++) {
        for (int j = i + 1; j < temp; j++) {
            if (t[i][j] > maxV) {
                maxV = t[i][j];
                maxI = i;
                maxJ = j;
            }
        }
    }
    return maxV;
}}

Összevonások módszere

Az összevonás módszere azon az egyszerű ötleten alapul, hogy az egymáshoz hasonló elemeket, vagy azok csoportjait egy csoportba vonjuk össze.

package hu.unideb.inf.optimization.methods;
import hu.unideb.inf.optimization.clustering.Cluster;
/**
 * Keressük azokat a partíciókat, melyeket érdemes összevonni.
 * @author ASZALÓS László
 */
public class Contract extends SolvingMethod<Cluster> {

A módszer paramétermentes, ám ezt tudatni kell a keretrendszerrel:

@Override
public void constants(String name, int numerator, int denominator) {
}

A módszer igen egyszerű. A korábbi véletlen kiinduló állapot helyett egy olyat választunk, ahol a gráf minden csúcsa külön csoportot alkot. Ezután a segédosztály metódusait felhasználva megnézzük, hogy van-e két csoport, melynek az összevonása csökkenti a célfüggvényt. Ha van ilyen, akkor végezzük el ennek a két csoportnak az összevonását.

@Override
public Cluster solve(Cluster x) {
    ContractTools cnt = new ContractTools();
    x.fillDiagonal();
    while (cnt.getMaxValue(x) > 0) {
        cnt.contract((Cluster) x);
    }
    return x;
}}

Összevonás variáns segédosztálya

Az előző segédosztályban csak egy tömböt kellett újra és újra feltölteni, majd megkeresni annak maximális elemét. Ha a gráf nagy, akkor ez a feltöltés időigényes. Szeretnénk ezt a feltöltést minél ritkábban végrehajtani. A kevesebb számolás viszont összetettebb adatszerkezetet igényel. Itt most a tömb mellett egy vektort is feltöltünk, és ha a vektor kiürül, csak akkor kell a tömböt újra feltölteni.

package hu.unideb.inf.optimization.methods;
import hu.unideb.inf.optimization.clustering.Cluster;
/**
 * Egyszerűsítjük a keresést egy plusz adatszerkezet felhasználásával
 * @author ASZALÓS László
 */
public class ContractVectorTools extends ContractTools {

Ahogy korábban többször, most is speciális elemmel jelezzük, ha az adott helyen még nincs használható érték:

private final static int EMPTY = -1;

A korábbi egy érték helyett itt most értékek sorozatát kell tárolni:

private int[] vector;

Valamint azok első és második koordinátáját/csoportját:

private int[] first;
private int[] second;

Az egyszerűség kedvéért egy indexet használunk a vektor feltöltöttségi szintjének jelzésére:

private int vectorPointer;

A konstruktor paramétere az adatok tárolására használt tömbök mérete. Itt nem teszünk mást, mint alaphelyzetbe állítjuk a segédtömböket:

ContractVectorTools(int length) {
    //this.length = length;
    vector = new int[length];
    first = new int[length];
    second = new int[length];
    vectorPointer = 0;
    vector[vectorPointer] = EMPTY;
}

Az ősosztályban az összevonást egyszerűen végrehajtottuk. Most viszont figyelembe fogjuk venni a segédtömböket:

@Override
void contract(Cluster x) {
    int cx = first[0];
    int cy = second[0];
    if (cx==cy) {
        System.err.println("contract azonos elemek");
        System.exit(1);
    }
    drop();
            x.substitute(cy, cx);

Ha valódi összevonásról beszélhetünk, akkor azt végrehajtottuk. Ennek következményeit kell még adatszerkezeteinken átvezetni:

int temp;
t[cx][cx] += t[cy][cy]; 
t[cy][cy] = 0;
for (int k = 0; k < t.length; k++) {
    temp = cy < k ? t[cy][k] : t[k][cy];
    if (cy < k) {
        t[cy][k] = 0;
    } else {
        t[k][cy] = 0;
    }
    if (cx < k) {
        t[cx][k] += temp;
        if (cx != k && t[cx][k] > 0) {
            insert(t[cx][k], cx, k);
        }
    } else {
        t[k][cx] += temp;
        if (cx != k && t[k][cx] > 0) {
            insert(t[k][cx], k, cx);
        }
    }
}}

A vektor tömbre egy olyan sorként tekintsünk, amely rendezett. Ha az első elemét felhasználtuk, akkor az törölni kell:

/**
 * Az első elemet kidobjuk a vektorból, a többiek egyet előre lépnek
 */
private void drop() {
    for (int i = 1; i < vectorPointer; i++) {
        vector[i - 1] = vector[i];
        first[i - 1] = first[i];
        second[i - 1] = second[i];
    }
    vectorPointer--;
    vector[vectorPointer] = EMPTY;
}

Az algoritmus kezdetekor, vagy a vektor kiürülésekor újra kell számolni az értékeket. Ehhez megint az error metódust használjuk. Viszont ezután minden számunkra érdekes (pozitív) elemet megpróbálunk beszúrni a vektorba.

/**
 * Töltsük fel a vektort a legjobb pozitív elemekkel!
 * @param t adatainkat tartalmazó háromszögtömb
 */
private void fillVector(Cluster x) {
    if (null == t) {
        t = x.errors();
    }
    int temp = t.length;
    for (int i = 0; i < temp; i++) {
        for (int j = i + 1; j < temp; j++) {
            if (t[i][j] > 0) {
                insert(t[i][j], i, j);
            }
        }
    }
}

Korábban a tömböt végig kellett böngésznünk, hogy a legnagyobb elemre rábukkanjunk. Ha még nincs tömb, akkor lényegében ezt csináljuk a fillVector metódusban is. Ha már van tömb, és a vektorban is van valami, akkor megvizsgáljuk, hogy az első elem valóban létezik-e vagy sem. Könnyen elképzelhető, hogy a korábban létező elem összevonás révén megszűnt, vagy értéke megváltozott. Ekkor nem ezt kell figyelembe venni, hanem a következőt:

@Override
public int getMaxValue(Cluster x) {
  do {
          if (0 == vectorPointer) {
        fillVector(x);
    }
    while (vectorPointer > 0
            && t[first[0]][second[0]] != vector[0]) {
        drop();
    }
    if (vectorPointer > 0) {
        return vector[0];
    } 
  } while (vectorPointer > 0);
    return EMPTY;
  }

Ha bőven van hely a vektorban, akkor berakjuk annak végére. Ha nincs, de ez jobb elem, mint vektorban az utolsó, akkor lecseréljük vele. Ha nem is jobb, akkor pedig elfelejtjük.

/**
 * Megpróbáljuk beszúrni a value adatot a vektor végére
 * @param value beszurandó adat
 * @param i az adatelem első indexe
 * @param j az adatelem második indexe
 */
private void insert(int value, int i, int j) {
    if (vectorPointer < vector.length) {
        put(vectorPointer, value,i,j);
        vectorPointer++;
    } else {
        if (vector[vector.length - 1] < value) {
            put(vector[vector.length-1], value, i, j);
        } else {
            return;
        }
    }
    insertionStep();
}

A beszúrással csak a sor végére raktuk az elemet, most megkeressük a helyét. Ehhez a már rendezett sorban kell az utolsó elemet a helyére mozgatni, melyhez a beszúró rendezésből származó módszert használjuk:

/**
 * A beszúró rendezés egy lépése, mellyel a vektorban
 * csökkenő sorrendben helyezzük el az elemeket.
 */
private void insertionStep() {
    int j = vectorPointer - 1; // ide raktuk be az utolsót
    int value = vector[j];
    int x = first[j];
    int y = second[j];
    while ((j > 0) && (vector[j - 1] < value)) {
                put(j, vector[j - 1], first[j - 1], second[j - 1]);
        j--;
    }
    put(j, value, x, y); 
}

Annak érdekében, hogy ne ismételjük magunkat, a sorba írást külön metódusként adjuk meg:

/**
 * Az adatot a kijelölt helyre beírja.
     * @param pointer beírás helye
 * @param value beirandó adat
 * @param i az adatelem első indexe
 * @param j az adatelem második indexe
 */
    private void put(int pointer, int value, int i, int j){
        vector[pointer] = value;
    first[pointer] = i;
    second[pointer] = j;
}}

Összevonás variáns

Az összevonás módszerét kicsit megváltoztatva a számítási igény jelentősen csökken.

package hu.unideb.inf.optimization.methods;
import hu.unideb.inf.optimization.clustering.Cluster;
/**
 * Az összevonás módszerének variánsa
 * @author ASZALÓS László
 */
public class ContractV extends Contract{

Szükségünk van egy tömbre, melyben tároljuk a leginkább hasznos összevonásokat. A tömböt a segédosztályban tároljuk, itt csupán annak a méretére lesz szükség.

private int LENGTH;

A megszokott módon ezt a paramétert be kell olvasni:

@Override
public void constants(String name, int numerator, int denominator) {
      if (name.equals("LENGTH")) {
        LENGTH = numerator;
    }
}

A megoldást kereső algoritmusunk szinte szóról szóra megegyezik az előzővel, csak a felhasznált segédosztály más:

@Override
public Cluster solve(Cluster x) {
    ContractVectorTools cnt = new ContractVectorTools(LENGTH);
    x.fillDiagonal();
    while (cnt.getMaxValue(x) > 0) {
            cnt.contract((Cluster) x);
    }
    return x;
}}