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

2.2.2. Módosítható megoldáskeresők

Információ kellene tárolni az információkeresés múltjáról. Ha felismerjük, hogy rossz irányba haladunk, akkor visszalépünk.

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


 

2.2.2.1. Visszalépéses (backtrack)

Adatbázis: a keresőgráf egy része kerül ide. start-ból induló, aktuális csúcsba vezető aktuális út. Ez az az út amiből véljük, hogy elérjük valamelyik terminális csúcsot. A múltból mi van nyilvántartva: a start-ból milyen módon jutottunk el az aktuális csúcsba.

Műveletek: operátorok + visszalépés
   
  operátorok: állapottérreprezentációs műveletek
  visszalépés: technikai művelet


 

Operátor: alkalmazzuk az utolsó csúcson, ezzel új állapot keletkezik. Ezt felfűzzük az aktuális útra (annak hossza 1 élnyivel megnő). Ez lesz az új aktuális csúcs.

Az operátor alkalmazása tehát növeli az utat!

Visszalépés: töröljük az aktuális csúcsot, és az aktuális csúcs a megelőző csúcs lesz. Vagyis az út rövidebb lesz.

Vezérlő: eldönti, hogy az adatbázis melyik részén mikor, melyik műveletet kell végrehajtani (az aktuális csúcsra fog alkalmazni egy műveletet).
Mit figyeljen?

Ha nemterminális a csúcs, akkor ezen az úton remény van-e még a megoldás megtalálására vagy sem? Vagy: érdemes-e még folytatni egyáltalán a keresést?

Hogy fog a vezérlő megoldást keresni?

a) "alap" backtrack

1. inicializálás. Az út egy csúcsból áll: (start csúcs)
  Van adatbázis, aktuális út, aktuális csúcs
 
2. tesztelés. Az aktuális csúcs terminális-e?
  igen: kész vagyunk
  nem: tovább tudunk-e lépni? Van-e alkalmazható operátor?
    igen, van: választunk, alkalmazzuk. Új aktuális csúcs, ismét tesztelés (2. pont)
    nincs: másik művelet: visszalépés.
      (vagyis ha az akt. csúcsban nincs alkalmazható operátor)



 

Ha az aktuális csúcsban nincs alkalmazható operátor, akkor meg kell próbálni a megoldást valamilyen másik irányban keresni. A reprezentációs gráfban valamilyen másik irányba kellene lépni. Az adatbázisnak viszont ezt tudnia kell, minden csúcsban nyilván kell tertani, hogy abból a csúcsból mely alkalmazható operátorokat alkalmaztuk, vagy nem alkalmaztuk (ez egy plusz információ).

A visszalépés során előállt új aktuális csúcsban egy még nem alkalmazott alkalmazható operátort kell alkalmazni.

Van ilyen?
  igen: alkalmazzuk, folytatjuk a keresést
  nem: visszalépés a szülőre, s a reprezentációs gráfban egy másik irányba
    kell próbálkozni. Vagyis: aktuális csúcsban már minden alkalmazható operátort kipróbáltunk, sikertelenül visszalépés.
     
Terminálási feltételek:
  1. az aktuális csúcs célcsúcs-e?
  2. start csúcsban teljesül a visszalépési feltételünk
    (vagyis már nincs olyan operátor, amit ne alkalmaztunk volna már sikertelenül)
    Ekkor nincs megoldás!


Ha a reprezentációs gráfunk olyan véges gráf, hogy nem tartalmaz köröket, a visszalépéses megoldáskereső - ha van megoldás - garantáltan előállít egy lehetséges megoldást. Ha nincs megoldás, akkor azt fel lehet ismerni.

Eltérés hol lehet? Az operátorok választásában. Ez történhet:

Heurisztika: tudásunk alapján megbecsülhetjük, hogy a cél milyen távol van. Ezért választhatunk olyat, ami közelebb visz (hasonló a hegymászó módszerhez).

Mik a problémák? Olyan reprezentációs gráfok esetén garantálja a megoldást, amelyben nincsenek körök. Ekkor ui. nincs garantálva a megoldás, végtelen ciklus alakulhat ki. (Végtelen sokszor ugyanazt választjuk ki).
Ötlet: ne engedjük, hogy egy körön végtelen sokszor végigmenjen, vagy ne is engedjük bezárni ezt a kört:

b) kör kiküszöbölése

lesz egy újabb visszalépési feltétel: az aktuális csúcs szerepelt-e már az aktuális úton
  Ha igen: rögtön visszalépés (így nem zárjuk be a kört). Azaz körök nélkül próbáljuk meg megtalálni a megoldást. (Ha van megoldás, akkor van körmentes megoldás is).

c) úthossz-korlát

Egy másik megoldás az, hogy úthossz-korlátot vezetünk be: l (megoldás)
Fává egyenesítünk, végtelen fagráfot állítunk elő. Nem engedjük, hogy az aktuális út hossza meghaladja az úthosszkorlátot.
   
aktuális út hossza úthossz-korlát (ha ez teljesül visszalépés)

Viszont ha túl rövidre választjuk az úthossz-korlátot (túl alacsonyan vágjuk el a gráfot) akkor nem találunk megoldást.

Ha a start csúcsban áll elő a visszalépési feltétel, akkor:
  1. nincs megoldás
 

2. túl rövidre választottuk az úthossz-korlátot

Arról, hogy melyik, nem ad információt!

Ez utóbbi (úthossz-korlátos) tartalmazhat kört a megoldásban. Ha körmenteset akarunk, akkor onnan nekünk kell kivágni a kört.

Nem feltétlenül véges fa-gráf esetén, ha garantáltan van az úthossz-korlátnál rövidebb megoldás, akkor azt megtalálja.

d) optimális megoldás keresése

A backtrack alkalmas-e optimális megoldás keresésére? Azaz van költség, s a legkisebb költségű megoldást szeretnénk előállítani. Ez lesz az ág és korlát algoritmus.

van egy induló költségkorlát k (megoldás)
(felső becslés)

Ennél a költségkorlátnál nem költségesebb megoldást keresünk. Csak addig megyünk a reprezentációs gráfban a keresés során, míg a költségkorlátot el nem érjük.
Ha találunk egy megoldást, akkor ez lesz az új költségkorlát! (Ez ugye induló költségkorlát)
Folytatjuk a megoldáskeresést. Ezt a megoldást elraktározzuk, s úgy tekintjük, mintha nem lett volna megoldás. Ha van újabb megoldás, akkor annak költsége már csak lehet, mint ez. Ismét csere, eltárolás, stb.
Így a reprezentációs gráf elég nagy részét nem kell bejárni, egyre kisebb utakat járunk be. Addig folytatjuk, míg a start csúcsból el tudunk valamerre indulni.

Mit garantál ez?

CSAK körmentes gráfok esetén működik!

Vissza a lap tetejére