Előadó: Dr. Várterész Magdolna

Módosítható megoldáskeresők osztályozozása: 1. visszalépéses (backtrack)
  2. keresőgráffal


 

2.2.2.2. Keresőgráffal megoldást keresők

Adatbázis: keresőgráf, egy fa. A reprezentációs gráfnak a bejárt részét feszítő fa. Egy csúcspont lehet zárt (az út közbenső csúcsa, rajtuk már továbbhaladtunk), vagy lehet nyílt (az utak végén álló levelek, itt folytathatjuk majd a keresést).
Minden csúcsnak pontosan egy szülője lesz nyilvántartva a keresőgráfban (mivel fa). Az éleket visszamutatók segítségével realizáljuk. Így tudunk majd rekonstruálni.
(A visszalépéses megoldáskereső csak egy utat tartott számon. Itt több út is számon van tartva, rajtunk múlik, hogy hol folytatjuk).

Művelet: kiterjesztés. Levélelemből kivitelezi a továbblépést, Így tudunk majd élnyire továbbmenni. Az összes lehetséges irányba továbbmegyünk majd. (Egy új, nem kiterjesztett csúcsra alkalmazzuk az összes alkalmazható operátort).

Vezérlő: melyik nyílt csúcs legyen a következő lépésben kiterjesztve. A kiválasztott nyílt csúcsot tesztelni tudja (célcsúcs, nem célcsúcs), s van egy út visszafelé is. A nyílt csúcsok közül kell választania a megoldáskeresőnek.
Nincs megoldás: egyetlenegy nyílt csúcs sincs, amelyen a keresést folytathatnánk.

Szisztematikus keresőgráffal keresők

Szisztematikus keresőgráffal keresők:

2.2.2.2.1. Szélességi és mélységi kereső

A reprezentációs gráf csúcsait oly módon választjuk, hogy az 1. szinten, 2. szinten, stb. lévő csúcsokat vesszük.

mélységi szám: g(s)=0 a start csúcsé 0. 0 szintre van a start-tól
  g(m)=g(n)+1 a szülő mélységi száma + 1, ahol (n,m) E (vagyis él)

Egy csúcs előállításakor mindig kiszámítjuk a mélységi számát.


Kiterjesztésre melyik csúcsot választjuk ki?

szélességi+mélységi: egy adott csúcshoz vezető melyik út van éppen
  nyilvántartva? Mindegy, ezért a legelső számontartott
  utat fogjuk nyilvántartani.

1.
 adatbázis inicializálása:
ö
  
rögzítsük a mélységi számot:
0
ý
 S0(0) nyílt (nyílttá tesszük)
visszamutató:
0
ø
  
 
(azt is tudni kell, hogy az induló keresőgráf egyetlen csúcsa nyílt-e vagy zárt)
       
2.
 Van-e nyílt csúcs?
  nincs: be kell fejezni, nem tudjuk folytatni
  van: ki kell választani a nyílt csúcsok közül egyet
    (az alapján, hogy mélységi v. szélességi a keresés)
    A kiterjesztésre kiválasztott csúcsot teszteljük.
    Célcsúcs?
    nem: kiterjesztjük, őt zárttá, gyermekeit nyílttá
      tesszük. Gyermekek visszamutatnak a szülőre, mélységi szám beírása. Vissza a 2. pontra.
    igen: sikeres vég, mutatók alapján van egy út vissza

Szélességi, mélységi keresésnél nem cél az optimális megoldás kiválasztása: ha több út van az adott csúcsba, akkor tetszőlegesen tartjuk nyilván az egyiket (legegyszerűbb, ha maradunk az elsőnél). Mikor tesztelünk, a tesztelést előrehozhatjuk, mert nem cél az optimális megoldás.

Szélességi: tetszőleges reprezentációs gráfban ha van megoldás, akkor a legkevesebb operátor alkalmazásával előállítható valamelyik terminális. Mindig a legkisebb mélységi számú csúcsot teszteljük, terjesztjük ki, ezért a legkisebb hosszúságú megoldást állítjuk elő.
Ha nincs a problémának megoldása, akkor azt a nyílt csúcsok elfogyásával felismeri.

Mélységi: tetszőleges, véges reprezentációs gráfban ha van megoldás, akkor a mélységi kereső megoldás a terminál. Ha nincs megoldás: felismeri.

(Mint látható, nem kell megkövetelni a körmentességet - ellentétben a backtrack-kel).

Implementálás:

Szélességi esetben a nyílt csúcsokat egy sorban tartjuk nyilván, amelyből pont mélységi szám szerint növekvőleg fognak kijönni.
Mélységi esetben: veremben való kezelés.

Ezt onnan lehet könnyen megjegyezni, hogy "a sor széles, a verem pedig mély" :-)

Ha a reprezentációs gráf fagráf: kiterjesztéskor nem kell figyelni, hogy a gyermekek szerepeltek-e már vagy sem, mert nem szerepelhettek! (ui. fagráf esetén egy elemnek csak 1 szülője lehet, így egy elemet csak 1 irnyból, a szülő felől érhetjük el, s nem kell attól félnünk, hogy már korábban egy másik irányból kiterjesztették).

 

2.2.2.2.2. Optimális kereső

(a szélességi keresés is egyfajta opimális megoldást adott. Költség: út hossza).

r(n,m) d > 0 ,ahol (n,m) E

Minden csúcsnál számon tartjuk az odavezető út költségét.

  g(s)=0  
  g(m)=g(n)+r(n,m) ,ahol (n,m) E
    g(n):    szülő költsége, g(n) 0
    r(n,m): a szülő és gyermek közti él költsége
  g*(n) jelöljük így a start-ból n-be jutás optimális költségét
  g(n) g*(n) , n N

A nyílt csúcsok közül azt fogjuk kiterjesztésre kiválasztani, amelyik eddig a legolcsóbb volt (ott reméljük majd a legolcsóbb megoldást). A legkisebb költségű nyílt csúcsot választjuk ki kiterjesztésre.

Ha az új út kisebb költségűnek bizonyul mint a régi, akkor...

n m

  m szerepelt már akeresőgráfban:
  Ha az új út költsége < régi, akkor
átállítjuk a mutatót ill. a költséget (zölddel jelölve)
 
 
 
   
m lehetett nyílt: ekkor átállítjuk a mutatót ill. a költséget (lásd fentebb)
m lehetett zárt: már vannak részgráfjai! Az m-ből induló részgráf összes
  csúcsába is kisebb költséggel juthatnánk el. Gond!

DE! Bebizonyítható, hogy ha m zárt, akkor nem található hozzá vezető kisebb költségű út!

 
Mivel m zárt (most ezt feltételezzük), akkor
az m-et hamarabb kellett kiterjeszteni, mint n-et, azaz g(m) g(n)
 
g(m) g(n)
g(m) < g(n) + r(n,m)
 
 
 
Így tehát az előbbi probléma nem fog minket érinteni.

Mit garantál az optimális kereső? Tetszőleges reprezentációs gráfban ha van megoldás, akkor az optimális megoldással terminál. Ha nincs megoldás: jelzi.

Tesztelés: mikor teszteljük a csúcsokat, hogy terminális-e? Ez időnként előrehozható, például kiterjesztéskor, amikor előállítunk egy csúcsot akkor rögtön tesztelhetjük. Ez viszont csak csak szélességi és mélységi keresésnél működik ilyeténképpen, optimálisnál nem (ott csak kiválasztás után).

Heurisztikus keresőgráf

Heurisztika: a szisztematikus keresőgráffal keresők a gráf jóval nagyobb részét használják (egy egész fát, míg a korábbiak jóval kisebbet).
A heurisztika trükk, egyszerűsítés, mely a nagyméretű reprezentációs gráfban a keresést tudja korlátozni. Csak a gráf azon részét kelljen előállítani, amelyben a megoldást reméljük a tudásunk alapján (míg a szélességi bizonyos mélységig az egészet feltárja).

Példa:
szélességi keresés esetén:

1 csúcsnak van d gyermeke, s l hosszú a legrövidebb megoldás. Hány csúcsú keresőgráfot állítana ez elő?

Vagyis a megoldás mérete a megoldás hosszának exponenciális mérete.

Heurisztikával: a nyílt csúcsok közül ha mindig azt terjesztenénk ki, ahol a megoldást reméljük:

1 + d + d + ... + d = 1 + l × d

Ez az ún. perfekt heurisztika. Persze perfekt heurisztikánk NINCS (hiszen ha ismernénk a megoldást, akkor nem kellene keresni)! De ez lenne az ideális. A lényeg: csökkentsük a keresőgráf méretét!

 

2.2.2.2.3. Best-first kereső

(A legjobb irányban haladó keresés).

h(n) n becslő függvényérték, ahol n-ből meg tudjuk becsülni a célbajutás
  optimális költségét
h(n) 0  
h(t) = 0 , ha t T (vagyis ha terminális csúcsban vagyunk)
h(n) = , ha egy csúcsból (n-ből) nem érhető el egyetlen terminális sem,
  akkor valamilyen nagyon nagy számmal jelöljük

A keresőgráfban minden n csúcshoz előállítjuk h(n)-t.

Kiterjesztésre kiválasztás: legkisebb heurisztikájú nyílt csúcs
(CSAK ezt tárolja: abból a csúcsból kb. milyen hosszú lesz a hátralévő út. A múltról NEM tárol semmit.
Míg az optimális kereső: ami ADDIG a legolcsóbb volt, a múltat figyelte.
Ez: a jövőt nézi, milyen hosszú lesz még.)

Általában az elsőként nyilvántartott utat szoktuk nyilvántartani. Vagyis: ha kiterjesztés során előállítunk egy csúcsot, s szerepelt a keresőgráfban: nem foglalkozunk vele; nem szerepelt: nyílt csúcs lesz, visszamutatóval.

1.
 Adatbázis inicializálása: start csúcs, heurisztika megállapítása, nyílttá tesszük
2.
 Van-e nyílt csúcs?
nincs: nincs megoldás
van: kiválasztjuk a legkisebb heurisztikájút, s teszteljük. Célcsúcs?
  igen: rendben, visszamutatók alapján megvan a megoldás
    nem: kiterjesztjük. A keresőgráfban még nem szereplő gyermekeit
      felvesszük a nyílt csúcsok közé, szülőre visszamutatnak, becslés esetükben. A szülőt zárttá tesszük.


Nincs minősített megoldáskeresés. A terminálási feltételek előrehozhatók; például kiterjesztéskor gyermekek tesztelése.

Mit garantál? tetszőleges véges gráf esetén ha a reprezentációs gráf tartalmaz megoldást, akkor véges sok lépésen belül megoldást állít elő. Ha nincs megoldás: jelzi.

Probléma: ha a heurisztika nem elég jó, akkor a keresés biztonságát, a garanciát elveszíthetjük.

Vissza a lap tetejére