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

2.4. Probléma-redukcióval leírt feladatok megoldását kereső módszerek

Osztályozásuk:

  1. nem-módosítható megoldáskeresők (nem foglalkozunk velük)
  2. módosítható keresők
    1. visszalépéses (backtrack)
    2. keresőgráffal

2.4.1. Backtrack (visszalépéses)

állapottér-reprezentáció esetén: adatbázis: start csúcsból induló valamilyen út a
    reprezentációs gráfban. Aktuális út. Aktuális állapot: az út végi csúcs. Ennek a vizsgálata döntötte el, hogy hogyan tovább.
ÉS-VAGY gráf esetén: adatbázis:

egy hiperút, a start csúcsból indul.
    Ebből szeretnénk megoldást készíteni. Aktuális hiperút.
     
Levelei: az eredeti problémának valamilyen szintű
  részproblémái. Ha a levelek mind egyszerű megoldható problémák: megoldás:
Csúcsok: probléma, részprobléma, amit éppen reprezentál


 

Miket tartunk nyilván a csúcsokban?

  1. mutató gyermekére, az 1. gyermekére
    köv. mutató a testvérre
    szülőre mutató mutató (a visszalépéshez)
  2. a még nem alkalmazott (de alkalmazható) redukciós operátorokra valamilyen információ
  3. címke (az adott probléma megoldását tartalmazza-e a hiperút vagy sem?)

Amikor egy csúcsot előállítunk megnézzük, hogy az egyszerű problémák között szerepelt-e már? Háromféle címkét fogunk alkalmazni:

  1. M (megoldható egyszerű probléma)
  2. N (nem megoldható egyszerű probléma)
  3. F (a többi problémának ez a címkéje, azt jelzi, hogy még folyik a munka)
Műveletek: 1. redukciós operátorok
  2. visszalépés


 

1. redukciós operátorok: csak F címkéjű levelekre alkalmazható!
  előállítjuk a részproblémákat, s felfűzzük az akt. hiperútra az adott csúcshoz, mint szülőhöz (szülőnél egy mutató fog az 1. gyermekre mutatni).
Szülőnél operátor törlése (mert azt már alkalmaztuk).
  Gyermekek: megjelenik az adott probléma
    szülőre visszamutató mutató
    mindegyiknél köv. mutató a testvérre
    felcímkézzük
    F címke esetén: összes alk. red. op. felvétele
     
2. visszalépés: csak N címkéjű levelekre alkalmazható!
  Ha a gyermekek közt megjelent egy N címkéjű csúcs, akkor visszalépés: valamilyen más redukcióval kell a hiperutat megoldani.
  Redukciós operátor hatásának visszavonása:
 
  Kitöröljük a szülő gyermekeit: az N címkéjű csúcsban van egy visszamutató a szülőre (1.), ahonnan elérhető az 1. gyermek (2.). Innen van egy mutató a következő testvérre, ezáltal a szülő gyermekeit be tudjuk járni, s ki tudjuk őket törölni.
   
  A visszalépés műveletét kell még akkor is alkalmaznunk, amikor az adott csúcsban elfogytak az alkalmazható operátorok. F címkéjű a csúcs, őt kellene redukálni, de már az összes operátor elfogyott: ekkor is visszalépés.


 

A vezérlő:

1.
 inicializálás:

 

 
   
  ha a címka F, akkor keresésről van szó
   


2.
 keresés (pszeudó-kód):
1
 van = választFlevél(n); //(*)
2
 while (van)
3
 {
4
    op = választRedOp(n);//(*)
5
    if (op != 0)
6
    {
7
       GY = alk(n, op);
8
       hiperútbővítés(GY, n, op);
9
       if (Ncímkéjű(n, m)) visszalép(m);
 
10
    }
 
11
    else visszalép(n);
 
12
  
 
13
    van = választFlevél(n);
 
14
 }
 
         
  magyarázat:        
 
1
 egy F címkéjű levéllel tér vissza, ha van ilyen
 
2
 addig dolgozunk, míg van F címkéjű csúcs
 
3
  
 
4
 a kiválasztott csúcs esetében választunk egy operátort
 
5
 ha van alkalmazható operátor, akkor (7-8-9), különben meg visszalépés
 
6
  
 
7
 előállítjuk a csúcs gyermekeit (GY)
 
8
 a gyermekeket felfűzzük: maga a probléma, szülő mutat az 1. gyermekre,
    gyermekek köv. mutatója a testvérre mutat,
    gyermekek visszamutatnak a szülőre,
    felcímkézzük a gyermekeket
 
9
 a szülőtől bejárjuk a gyermekeket, s N címkéjűt keresünk
    ha találunk (m-ben adja vissza), akkor visszalépés
 
10
  
 
11
 ha az 5-ös pontban nem találtunk alkalmazható operátort, akkor visszalépés
 
12
  
 
13
 keressük a következő F címkéjű csúcsot.
 
14
  
     
  Ha a start csúcsból lépünk vissza: sikertelen a megoldáskeresés.


Beszélhetünk szisztematikus ill. heurisztikus keresésről. Ezen megoldáskeresők a (*)-gal jelölt két választásban térhetnek el lényeges módon (valasztFlevel, valasztRedOp).
Heurisztikus esetben hogyan válasszunk? HA van becslés a megoldás költségére, akkor válasszuk a LEGNEHEZEBBET! A valasztFlevel() válassza a legnehezebb problémát!

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

Állapottér-reprezentációs esetben akkor volt meg a megoldás, amikor a tesztelésre kiválasztott csúcs eleget tett a célfeltételnek.

Problémaredukciós esetben a terminálás figyelésére bevezetjük a címkemódszert. Háromféle címkét fogunk alkalmazni:

  1. M (megoldható egyszerű probléma)
  2. N (nem megoldható egyszerű probléma)
  3. F (a többi problémának ez a címkéje, azt jelzi, hogy még folyik a munka)
Két eljárás: - címkéző (az előbb a visszalépéses módszernél
    tulajdonképpen egy ilyet használtunk. Amikor az adatbázisba bekerül egy új csúcs, akkor azt címkézzük).
  - címkemódosító (a címkék módosíthatóak. Ha a címkéző egy F-től
    különböző címkét ad egy csúcsnak, akkor ennek a szülőre nézve következményei lesznek).
 
  ha ő VAGY-gyermek, akkor a szülő is M lesz ekkor még nem tudunk mit mondani!
 
  még nem tudunk mit mondani! ha ő ÉS-gyermek és N címkéjű, akkor a szülő is N lesz


 

Ha a csúcsnál egy F-től különböző címke jelenik meg, akkor indul a címkemódosító eljárás a csúcs szülőjére nézve.

Ha a start csúcsban M címke jelenik meg: van megoldás, előállt a megoldás
Ha a start csúcsban N címke jelenik meg: nem oldható meg

Egyedül a start csúcs címkéjét kell tehát figyelni! Ha F: folytatjuk a keresést. Ha M, N: sikeres, sikertelen terminálás.

Az adatbázis ebben az esetben egy keresőgráf. Hiperutak, melyek a start csúcsból indulnak. Ezek valamelyikéből remélünk megoldást. ÉS-VAGY fagráfok.
A hiperutak közül választunk egyet, másrészt ha kiválasztottuk: ezen a hiperúton a még meg nem oldott problémák közül IS választani kell.

Itt is beszélhetünk szisztematikus ill. heurisztikus keresésről. Heurisztikus esetben: melyik hiperúton reméljük a megoldást, ill. azon belül a legnehezebb megoldást választjuk ki.

Ha kiválasztottuk: kiterjesztjük. Az összes redukciós operátort alkalmazzuk rá. A leveleket címkézzük, s ha kell módosítjuk a szülőt is. Megoldás: a start csúcs címkéje M-re vált.

Az N címkéjű csúcsokból induló hiperútrészleteket töröljük.

Az A-algoritmus valamilyen módosítását fogjuk alkalmazni. Ez lesz az:

AO-algoritmus

Adatbázis: s-ből induló hiperutak (keresés során már felderített hiperutak)

csúcsinformáció: maga a probléma
  1. gyermekre mutató mutató
  következő ÉS testvér (új)
  következő VAGY testvér (új)
  szülőre mutató mutató
  kiértékelő-függvény (új)
  címke
  információ a redukciós operátorokról

Művelet: kiterjesztés művelete (pszeudó-kóddal):

  while (vanMégRedOp(n, op))
  {
     GY = alk(n, op);
     hiperútbővítés(GY, n, op);
  }
  címkemódosító();
  kiértékelőfüggvényMódosító();
  NcímkéjűHiperutakEltávolítása();

Vezérlő: (pszeudó-kóddal):

1.
 inicializálás:

 

 
   
2.
van = választHiperút(h);
  while (van && (címke(h)!=M))
  {
     választFlevél(h, n);
     kiterjeszt(h, n);
     van = választHiperút(h);
  }


 

Kiértékelőfüggvény:

 
æ
 0, ha M címkéjű
 
ç
 , ha N címkéjű
f(n) =
í
  
 
ç
 h(n), ha F címkéjű és n levél
 
è
 , ha F címkéjű és n nem levél


 

Vissza a lap tetejére