Ugorjunk rögtön a közepébe. A módosítható keresés azt jelenti, hogy ha alkalmazunk egy valamilyen állapotra egy arra alkalmazható valamilyen operátort, akkor annak az eredménye egy új állapot. Ezt az állapotot később vissza tudjuk vonni és vissza tudunk ugorni arra az állapotra amire az előbb alkalmaztuk az operátort. Ezt úgyjük el, hogy módosítunk a keresőrendszer adatbázisán. Lássuk akkor, hogy ez hogyan is működik a gyakorlatban:
  • Adatbázis: Az adatbázis egyetlen a startcsúcsból kiiunduló aktuális csúcsban végződő irányított utat tartalmaz amelyet csomópontok tartanak nylván. Ahhoz, hogy ezt az irányított utat nevezzük most listának be tudjuk járni ahhoz a csomópontokban nyilván kell tartani az alábbi információkat:
    • A csúcs által reprezentált állapotot.
    • Egy mutatót amely az aktuális csúcs szülőjét címzi meg.
    • Azt az operátort amellyel előállt az aktuális állapot.
    • Az alkalmazható operátorok listája / A már alkalmazott operátorok listája
  • Műveletek: A műveletek itt már bonyolódnak egy kicsit. Kötelesek vagyunk masszívan elkülöníteni a technikai műveleteket az operátorokból származtatott műveletektől.
    • Operátorokból származtatott műveletek: Ahhoz, hogy alkalmazhassuk az operátorokat lennie kell legalább egy csomóponmtnak az adatbázisban. Enélkül nincs semmi. Ha már van legalább egy csomópont akkor arra már tudunk keresni alkalmazható operátort amelyet ha alkalmazunk akkor ennek hatásaként létrehozunk egy új csomópontot amelyet befűzünk az adatbázisba.
    • Technikai műveletek: Nos mivel most éppen a Backtrack azaz a visszalépéses keresőt kívánom bemutatni, ezért a technikai művelet nagyon szellemesen a visszalépés lesz. A visszalépéshez szintén elengedhetetlen, hogy legyen legalább egy csúcs az adatbázisban de hatásaként az utolsónak befűzött csomópont törlődik.
  • Vezérlő: A vezérlő feladata, hogy figyelje elértünk-e egy terminális csúcsot, illetve amennyiben nem eldönti, hogy mely produkciós szabályt alkalmazza. A produkciós szabály itt együttesen jelenti az operátorokból származtatott műveleteket és a technikai műveleteket is.

Na de a kérdés gondolom ekkorra már mindenkiben felvetődik. Mikor kell használni a visszalépést? Nos a dolog rendkívül egyszerű, de érdemes előre leszögezni, hogy backtrack algoritmus esetében is használhatunk heurisztikát. Nos hogy ezt tisztáztuk lássuk mikor is használunk visszalépést:

  1. Ha zsákutcába futunk: Ezt arról tudjuk felismerni, hogy még nem teljesül a célfeltétel de az adott csúcs által reprezentált állapotra nincs egyetlen alkalmazható operátor sem.
  2. Ha a zsákutca torkolatában vagyunk: Ez akkor áll elő, ha már egyszer visszaléptünk egy zsákutcából is ismét erre az állapotra csak azt az egy operátort tudjuk alkalmazni, amellyel ismét zsákutcába jutunk. Erre a célra a csomópontban szükséges letárolni mind az alkalmazható mint a már alkalmazott operátorok listáját, különben a backtrack beragad.
  3. Ha valamilyen heurisztika segítségével úgy találjuk, hogy az adott utat fölösleges tovább vizsgálni.
  4. Ha elfogytak az alkalmazható operátorok: Ha nincs több alkalmazható operátor akkor a csúcsból nemtudunk tovább menni. Mondjuk erről csak a szakirodalmakban olvastam, szerintem teljesen fölösleges mert ez totál ugyanazt jelenti, mint az első pont azaz zsákutcában vagyunk. Szóval én ezt figyelmen kívül szoktam hagyni, illetve ezzel szoktam megnézni, hogy na vaj zsákutcában vagyunk-e avagy sem.

És akkor lássunk valamicske kódot a backtrack algoritmus ezen változatához:

  1.  Procedure BackTrack(<A, kezdo, c, O>)
  2.     Műveletek <- Inicializál(O)
  3.     Terminálisok <- Inicializál(c)
  4.     Adatbázis <- Inicializál(kezdo) 
  5.     WHILE(IGAZ) LOOP
  6.                 IF Adatbázis.Top IS IN Terminálisok THEN
  7.                         STOP
  8.                 ENDIF
  9.         o <- SELECT * FROM Műveletek WHERE alkalmazási_előfeltétel(Adatbázis.Top)  AND Adatbázis.Top->Alkalmazott_Operátorok(this) IS NULL
  10.         IF o IS NOT NULL THEN
  11.             új_állapot->állapot <- o.Alkalmaz(Adatbázis.Top)
  12.             új_állapot->szülő <- Adatbázis.Top
  13.             új_állapot->operátor <- o
  14.             új_állapot->alkalmazott_operátorok <- NULL
  15.             Adatbázis.Top->alkalmazott_operátorok.Add(o)
  16.             Adatbázis.Push(új_állapot)
  17.         ELSE
  18.             Adatbázis.Pop
  19.         ENDIF
  20.     END LOOP
  21.     IF Adatbázis IS NOT NULL THEN
  22.         KiírMegoldás(Adatbázis)
  23.     ENDIF
  24. END

A dolog meglehetősen önmagáért beszél az egyetlen dolog ami talán magyarázatra szorul az operátorok összegyűjtése. A lényeg a következő. Össze kell gyűjteni minden alkalmazható operátort amelyet alkalmazhatunk az Adatbázis utolsó elemére és arra a csomópontra még nem alkalmaztuk az éppen vizsgált operátort. Szóval ez implementáció szinten kőkemény 1db for ciklust foglal magában. Aztán a következő érdekes dolog az, hogy itt már azt is megnézzük, hogy volt e egyáltalán ilyen kritériumokkal rendelkező operátor. Ha van akkor alkalmazzuk ha nincs akkor viszont visszalépünk. A visszalépés annyira egyszerű, hogy azt már ragozni sem lehet. Az utolsó csomópontot kitöröljük az adatbázisból. Ennyi lenne a visszalépéses megoldáskereső.

Fontos továbbá megjegyezni azt, hogy ebben a formában a backtrack nem nevezhető éppen hatékonynak. Hogy miért?

  1. Nem fogja észrevenni ha talált egy kört, azaz az új állapot már szerepel az adatbázisban.
  2. Ha végtelen hosszú a gráf akkor az életben nem fog terminálni.

Ezen hiányosságok kiküszöbölésére létezik még két variánsa a backtrack algoritmusnak. A körfigyeléses backtrack algoritmus és a mélységi korlátos backtrack algoritmus. Mindkettő koncepciója rendkívül egyszerű! A körfigyeléses algoritmusnál mielőtt létrehoznánk az új csomópontot és hozzáadnánk azt az adatbázishoz megnézzük, hogy az adatbázisban volt e már olyan csomópont amely által nyilvántartott állapot megegyezik az aktuálissal. Ha igen akkor nem foglalkozunk vele újrakezdjük a ciklust. Ezzel a rendkívül egyszerű 1db IF szerkezettel garantáltuk azt, hogy véges akár köröket is tartalmazó gráfban amennyiben létezik megoldás akkor az algoritmusunk körmentes megoldást fog találni. A mélységi korlátos backtrack algoritmus koncepciója mégegyszerűbb mint a körfigyeléses társáé. A lényege az, hogy fel kell venni egy számlálót, és meg kell neki adni egy maximális úthosszkorlátot. Amikor beszúrunk egy csomópontot az adatbázisba akkor növeljük egyel a számlálót. Amennyiben a számláló eléri a korlátot akkor az adott gráfban nincs megoldás vagy van de az a korlátnál hoszabb.

És ha a fenti két koncepciót összeöntjük egy algoritmusba azaz, kört is figyelünk és mélységi korlátot is megadunk, akkor eljutunk az ág és korlát algoritmushoz. Jó ez nem igaz mert ehhez az egészet egy ciklusba kell tenni, azaz minden megoldást kell keresni nem csak egyet de csak azt tároljuk amelyik megoldás hossza kevesebb vagy egyenlő mint a korábban tárolt megoldás hossza. Ezzel nem, hogy körmentes megoldást találunk egy általános akár végtelen gráfban de az a megoldás optimális megoldás lesz.

Eljutottunk ezen lecke végéhez is, lássuk akkor a fenti három algoritmus elemzésést.

  1. Teljesség:
    • Backtrack algoritmus: Véges gráfban ha létezik megoldás akkor talál egyet azok közül.
    • Körfigyeléses backtrack: Szintén véges gráfban ha léteznek megoldások akkor ez egy körmentes megoldást fog találni.
    • Mélységi korlátos (Úthossz-korlátos) backtrack: Tetszőleges gráfban ha létezik az úthosszkorlátnál rövidebb megoldás akkor azok közül egyet meg fog találni.
    • Ág-és-Korlát algoritmus: Tetszőleges gráfban optimális megoldást talál.
  2. Optimalitás: Egyedül az Ág-és-Korlát algoritmus garantálja az optimális megoldás megtalálását.
  3. Időigény:
    • Backtrack: Az időigényének java részét az alkalmazható operátorok összegyűjtése teszi ki.
    • Körfigyeléses backtrack: Itt már nem csak arról van szó, hogy össze kell gyűjteni az operátorokat amiket tudunk alkalmazni az adott állapotra de ha jó nagy a kör a gráfban amire sikeresen ráfut a kereső akkor az elég kritikus tud lenni. Akkor vissza kell lépkedni ám elég rendesen azon a szép kis körön és hát azért ez elég időigényes.
    • Úthosszkorlátos backtrack: Ennél nincs probléma az időigénnyel, az egyik leggyorsabb backtrack variáns. Az időigényét a  megadott korlát szabályozza. Minél hoszabb korlátot engedünk meg neki annál tovább tart a keresés de annál nagyobb eséllyel talál megoldást véges gráfban, illetve minél kisebb korlátot adunk meg annál gyorsabb de annál kétségesebb az, hogy akár véges gráfban is talál megoldást.
    • Ág-és-Korlát algoritmus: Rendkívül időigényes. Nincs megadva implicit úthosszkorlát mindenképpen az első megoldás hossza adja az első korlátot majd ezután minden újabb megtalál megoldás akkor kerül letárolásra ha ezen megoldások hossza kisebb vagy egyenlő mint az előzőleg letárolt megoldásé. Ekkor a korlát is felülíródik és indul megint az egész előről. Ettől időigényesebb backrack variáns egyszerűen nincs. De cserébe tuti biztos, hogy akármilyen is a gráfunk a kapott megoldástól jobb megoldás nem létezik.
  4. Tárigény: Az első két backtrack variáns tárigénye nagyban függ a kiinduló robléma állapottér-gráfjától. Ha nagy méretű a gráf és hosszú megoldások vannak benne akkor a nyilvántartandó út is hosszú ezért nyilván több emóriát fog lefoglalni.
    • Úthosszkorlátos backtrack: Fix méretű az adatbázisa, ami az úthosszkorlátnyi csomópontot tárol.
    • Ág-és-Korlát algoritmus: Teljesen változó méretű az adatbázisa. Maximum a leghoszabb megoldás lépéseinek számányi csomópont lesz az adatbázisban de végül az adatbázis mérete pont az optimális megoldás hosszától függ.

Ennyi lenne a módosítható megoldáskeresők bevezetése és a backtrack algoritmus. A következő téma már egy kicsit elvontabb: Keresőfával kereső rendszerek és azon belül helyet kapnak a Szélességi és Mélységi keresők, Best-First és Optimális algoritmusok valamint az A algoritmus és az A* algoritmus alapjai.

Reklámok