Lássunk egy másik megközelítést is. Az lőzőekben tárgyalt algoritmusok nem túl hatákonyak mival vagy csak egy csúcsot vagy csak egy irányított utat figyeltek. Nekünk olyan kéne ami extra ciklus ezzel együtt lassítás nélkül hajlandó lenne figyelni minden lehetséges utat. Na erre adnak lehetőséget a keresőfával kereső rendszerek. A tárgyalásuk ugyanazon az elven történik mint eddig:
  1. Adatbázis: Az állapottér gráf adott most is mint minden eddigi esetben. No de, hogy fogunk ebben nyilvántartani minden lehetséges utat? Hát kicsit másként tároljuk a dolgot. Továbbra is csomópontok lesznek az adatbázisban egy hajszálnyi módosítással de a struktúrája az adatbázisnak egy csöppet más. Ketté fogjuk bontani az adatbázist de lássuk csak, hogy pontosín miért. Az adatbázisban a gráf már bejárt részét feszítő fát fogjuk eltárolni amit igen szellemesen keresőfának szokás nevezni. Ezt a keresőfát fogjuk nyilvántartani a csomópontokban de a csomópontokban most is variálunk egy kicsit.
    1. Az a állapot amelyet az adott csúcs reprezentál.
    2. Egy mutatót amely megmutatja, hogy az aktuális csúcs mely csúcsnak a leszármazottja.
    3. Azt az operátort amellyel előállt az aktuális állapot.
    4. Egy Státusz nevű jelzőt ami meg fogja osztani az adatbázisunkat. Pontosan két részre fogja osztani az adatbázist:
      • Nyílt: Ez azt jelenti, hogy az adott csúcs ugyan előállt már a keresés során valamilyen operátor alkalmazásának hatásaként, de arra még nem alkalmaztunk egy darab operátort sem. Ez azt jelenti, hogy annak még nem állítottuk elő egyik leszármazottját sem (ha van neki).
      • Zárt: Totál ellentettje az előzőnek, neki már előállítottuk az összes leszármazottját.
  2. Műveletek: A műveletek itt is két csoportba lesznek sorolva mint a backtrack algoritmusoknál. Bezony ennek van köze ahhoz, hogy az adatbázis megoszlik két csoportra.
    1. Operátorokból származtatott műveletek.
    2. Technikai műveletek: Nos szép és jó, hogy vannak nyílt csomópontok és zárt csomópontok de mire lesz ez nekünk jó? A dolog egyszerű de még nem lövöm le a poént. Azt máris ki lehet találni, hogy milyen technikai műveletünk lesz. A nyílt csomópontok azok amelyeknek még nem állítottuk elő egyik leszármazottját sem. Ez a keresőfában a levélelemeket jelenti. Ezesetben kizárásos alapon a zárt csomópontok a nem levél elemeket jelölik a keresőfánkban. Akkor ahhoz, hogy építhessük a keresőfát vagyis az adatbázist nyilván a csúcsoknak elő kell állítani a leszármazottjait. Ezt a folyamatot amikor egy nyílt csúcsnak előállítjuk az összes leszármazottját kiterjesztésnak nevezzük. Ez lenne a technikai műveletünk és nagyon hasznos és egyszerű dologról van szó.
        1. Procedure kiterjeszt(<A, kezdo, c, O>, Csúcs, Nyíltak, Zártak)
        2.     FOR EACH o IN O LOOP
        3.         IF o.alkalmazási_előfeltétel(Csúcs->Állapot) THEN
        4.             állapot <- o.alkalmaz(Csúcs->Állapot)
        5.             ny <- SELECT * FROM Nyíltak WHERE Állapot = állapot
        6.             z <- SELECT * FROM Zártak WHERE Állapot = állapot
        7.             IF ny IS NULL AND z IS NULL THEN
        8.                 új_csomópont->Állapot <- állapot
        9.                 új_csomópont->Szülő <- Csúcs
        10.                 új_csomópont->Operátor <- o
        11.                 új_csomópont->Státusz <- Nyílt
        12.                 Nyíltak.Add(új_csomópont)
        13.             ENDIF
        14.         ENDIF
        15.     END LOOP
        16.     Csúcs->Státusz <- Zárt
        17.     Zártak.Add(Csúcs)
        18.     Nyíltak.Remove(Csúcs)
        19. END
  3. Vezérlő: A vezérlő feladata ezúttal is az, hogy ellenőrizze előállt-e a célfeltételnek megfelelő állapot amely esetben megvan egy megoldás, valamint egy nyílt csomópont kiválasztása amelyet majd kiterjesztünk. Valamint itt bejön egy nagyon jó tulajdonsága ezen keresőknek. Ha elfogytak a nyílt csomópontok – ami azt jelenti, hogy bejártuk az egész gráfot ahová vezetett irányított út a startcsúcsból – de nem volt egy darab terminális csúcs sem, akkor nem létezik megoldása a problémának az adott reprezentációban. Bizony az algoritmus fölismeri, hogy van-e megoldás avagy sem. Ha van megoldás akkor véges sok lépés után talál egyet, de ha nincs akkor ezt felismeri azon jelenség bekövetkezésekor, hogy elfogynak a nyílt csomópontok. Az azonban, hogy milyen gráfban talál rá egy megoldásra nagyban függ az alkalmazott keresési stratégiától azaz attól, hogy mi alapján választja ki a kiterjesztendő csúcsot.

No és akkor lássunk egy általános sémát a keresőfával kereső algoritmusra is ha már korábban is adtam. A dolog ismételten rendkívül egyszerű mert a séma ugyanaz maradt mint eddig volt.

  1. Procedure Keresőfával_Kereső(<A, kezdo, c, O>)
  2.     Terminálisok <- Inicializál(c)
  3.     Csomópont->Állapot <- kezdő
  4.     Csomópont->Szülő <- NULL
  5.     Csomópont->Operátor <- NULL
  6.     Csomópont->Státusz <- Nyílt
  7.     Nyíltak.Add(Csomópont)
  8.     Zártak <- NULL
  9.     WHILE(TRUE) DO
  10.         IF Nyíltak IS NULL THEN
  11.             STOP
  12.         ENDIF
  13.         Csomópont <- SELECT * FROM Nyíltak
  14.         IF Csomópont IS IN Terminálisok THEN
  15.             STOP
  16.         ENDIF
  17.         Kiterjeszt(<A, kezdo, c, O>, Csomópont, Nyíltak, Zártak)
  18.     END DO
  19.     IF Nyíltak IS NOT NULL THEN
  20.         Kiír(Csomópont)
  21.     ELSE
  22.         Kiír("Nincs megoldás")
  23.     ENDIF
  24. END

Ennyi lenne a keresőfával megoldást keresők általános sémája. A következőkben tárgyalt algoritmusok mivel mindegyike ugyanerre a sémára épül, csak azt fogom elmondani ami másként van és kihagyom a szokásos Adatbázis/Műveletek/Vezérlő tárgyalását mert az mindegyiknél ugyanaz lesz.

Advertisements