4. Informált keresési módszerek forrásának megtekintése

{{GlobalTemplate|Infoalap|MIOsszefoglaloInformaltKereses}}


__TOC__

==Általános tudnivalók, tételek, definíciók==

===4.1 Legjobbat-először keresés (Best-First) ===

Következő kifejtendő csomópont? Ennek meghatározásához szükséges tudást általában egy kiértékelő függvény formájában adott, mely a csomópont kifejtésének szükségeségét (vagy szükségtelenségét) adja vissza.

A legjobbat először függvény esetén a csomópontokat a kiértékelő függvény értéke szerint sorrendbe teszi és a legjobb értékkel rendelkező csomópontot fejti ki először.

====Mohó keresés====
Minimalizálja a cél eléréséhez szükséges becsült költséget:
* mindig azt a csomópontot fejti ki, amelyhez tartozó állapotot a legközelebbinek ítéli a célállapothoz
* a stratégiai cél érdekében mindig a lehető leggyorsabb lépést próbálja megtenni, nem törődve azzal, hogy hosszútávon jó döntést hozzott-e
* a becslés lehet hibás, ezért '''nem optimális'''
* bizonyos problémák esetén '''nem teljes''', mert a mélységi bejáráshoz hasonlóan a csomópontok bejárása közben végtelen útra kerülhet
* időigénye O(b<sup>m</sup>), tárigénye megegyezik az időigényével; az ''átlagos időigény'' azonban jóval kisebb lehet megfelelő heurisztikus függvény esetén, érzékeny a hibás kezdőlépésre

====Heurisztikus függvény====
*Heuriszitka*: olyan állítás, melyet nem tudunk általánosan bebizonyítani, de az esetek döntő többségében igaz.

*Heurisztikus függvény*: h(n) = az n csomópont állapotából egy cél-állapotba vezető legolcsóbb út becsült költsége. h(n) = 0 , ha n célcsomópont.

*Elfogadható heurisztika*: h függvény - soha ne becsülje felül a cél eléréséhez szükséges költséget; (optimista, úgy gondolja, hogy a probléma megoldása kisebb költséggel jár, mint amekkora költséget a megoldás valójában igényel). 

*Példa*: útvonal keresési problémáknál elfogadható heurisztikus függvény a légvonalban mért távolság.

====A* keresés====
A teljes útköltséget minimalizálja azzal, hogy ötvözi az egyenletes költségű és a mohó keresés előnyeit.

A csomópontokat kiértékelő függvény: f(n) = g(n)+h(n), ahol g(n) a csomóponthoz vezető legrövidebb út (már kiszámítva), és h(n) egy ''elfogadható'' heurisztikus függvény.

Az A* algoritmus teljes, optimális és az összes ilyen algoritmus közül optimálisan hatékony.

*Lokálisan véges gráf*: minden csúcs fokszáma véges.

Az A* algoritmus lokálisan véges gráfokon teljes, feltéve, hogy létezik valamilyen &delta; pozitív konstans, amelynél semelyik operátor költsége sem kisebb.

TK 134. oldal szerint a mohó, és az egyenletes költségű ötvözése az A*, ami így nem mohó.

<span style="color:blue">Az A* keresésről ennél jóval többet tanultunk, lásd TK138 vagy 4. előadás fóliái.</span>

*Példa*:
* 8-as kirakójáték
** h1() - a rossz helyen álló lapkák száma 
** h2() - a lapkák célhelytől mért távolságának összege
** vízszintes + függőleges távolság (háztömb - Manhattan-távolság)
 
===4.2 Heurisztikus függvények===
A heurisztikus függvény minősítésére szolgál a b* *effektív elágazási tényező*: A* által kifejtett összes csomópont száma egy adott problémára N, a megoldás mélysége d, akkor b* annak a d mélységű kiegyensúlyozott fának az elágazási tényezőjével egyezik meg, amely N csomópontot tartalmazna:
	
<pre> N = 1 + b* + (b*)2 + ... + (b*)d. </pre>

lásd: [http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=9449 2005. nov. 4. zh]

h2 '''dominálja''' h1-et, ha minden n csomópontra h2(n) &ge; h1(n). Ekkor h2-t használó A* kevesebb csomópontot fog kifejteni, mint a h1-et használó.

Az olyan problémát, amelyben az operátorokra kevesebb megkötést teszünk, mint az eredeti problémában, '''relaxált problémának''' nevezzük. Nagyon gyakran teljesül, hogy a relaxált probléma pontos megoldásának költsége jó heurisztikus függvénynek (h) bizonyul az eredeti problémára.

Kényszerkielégítés (CSP) és a heurisztika:
* legjobban korlátozott változó
* legjobban korlátozó változó
* legkevésbé korlátozó érték

===4.3 Memóriakorlátozott keresés===
* IMA* - *iteratívan mélyülő keresés*: 
** minden egyes iteráció egy mélységi keresés, mélységkorlát helyett költségkorlátot használ az A*-ra tett kitételekkel teljes és optimális, természetesen a heurisztikus függvény minőségétől is függ
** &delta; = legkisebb operátor költség
** f* = az optimális megoldás költsége 
** => <math> \frac{b\cdot f^*}{\delta} < b \cdot d </math>
** Ha az f költséget az iteráció során növeljük egy rögzített &epsilon;-nal (az iterációk száma arányos lesz az &epsilon;-nal) csökken a költség, de nem optimális - az eltérés legfeljebb &epsilon; lehet, neve: &epsilon; elfogadható*. 
* EMA* - ''egyszerűsített memóriakorlátozott'' _A*_: Az összes rendelkezésére álló memóriát csatasorba állítja, aktuális úton megjegyzi az ismétlődő állapotokat, az alternáló útszakaszon viszont nem kerüli el őket. Ha a rendelkezésre álló memória elégséges a legsekélyebb megoldás tárolására, akkor az algoritmus ''optimális'', egyéként az adott memóriával elérhető legjobb utat adja vissza. Ha a legsekélyebb megoldási út tárolható, akkor az algoritmus ''teljes''. Ha a teljes keresési fát képes tárolni, optimálisan hatékony. ''Algoritmusa'' egyszerű, legalábbis vázlatos szinten. Amikor egy követő csomópontot kell legenerálnia és már nem áll rendelkezésére felhasználható memória, akkor helyet kell csinálnia a sorban. Ehhez egy csomópontot törölni kell a sorból. Az ily módon törölt csomópontokat elfelejtett csomópontoknak nevezzük.

===4.4 Iteratívan javító algoritmusok===

Az alapötlet ennél a megközelítésnél az, hogy egy teljes (de nem jó) konfigurációból indulunk ki és olyan módosításokat hajtunk végre, ami javítja a konfiguráció minőségét. Összes állapot kiterítése egy tájkép felületre, ahol a magasság a minőséget jelzi: a legmagasabb pontja az optimum.

Az iteratívan javító algoritmusok két nagy csoportba oszthatók. A ''hegymászó'' (vagy grádiens módszer), ha a kiértékelő függvényt költségnek nem pedig minőségnek tekintjük. Algoritmusok mindig olyan változtatásokat próbálnak meg végrehajtani, amik javítanak az aktuális állapoton. A ''szimulált lehűtési'' algoritmusok néha megengednek olyan lépéseket is, amelynek hatására (legalábbis átmenetileg) rosszabb állapotba kerülünk.

* A '''hegymászó keresés''' (gradiens módszer) egyszerűen csak egy ciklus, ami mindig javuló értékek felé lép. Az algoritmus nem tart nyilván keresési fát, ezért a csomópontot leíró adatszerkezetnek csak az állapotot és a kiértékelését kell nyilvántartania. Egy fontos finomítás, hogy amikor egynél több legjobb követő csomópont létezik, az algoritmus közülük véletlenszerűen bármelyiket kiválaszthatja. Ez a megközelítés három ismert problémával küszködik. (plateau [plató])
** _lokális maximum_: leállítja, még akkor is ha máshol létezik nála jobb minőségű 
** _fensík_: véletlen bolyongás
** _hegygerinc_: lassan emelkedik, viszont rá könnyedén feljut a kereső algoritmus és lassan szabadul el onnan, holott lehet hogy lenne más, gyorsabb (meredekebb) út a csúcs felé. Ha észre is vesszük a csapdát, nem tudunk visszatérni egy korábbi állapotba (mert nem tároltuk el), hanem előröl kell kezdenünk.

* '''Szimulált lehűtés''' ahelyett, hogy ismét véletlenszerűen újraindítanánk a keresést, amikor az algoritmus egy lokális maximumban ragad, megengedhetjük a keresési algoritmusnak, hogy néhány lefelé vezető lépést tegyen, hogy elmeneküljön a lokális maximumból. Durván ez az alapgondolata a szimulált lehűtésnek. A szimulált lehűtés legbelső ciklusa nagyon hasonlít a hegymászáshoz. A legjobb lépés megtétele helyett azonban egy véletlen lépést tesz. Ha a lépés javítja a helyzetet, akkor az mindig végrehajtásra kerül. Ellenkező esetben az algoritmus a lépést csak valamilyen, 1-nél kisebb valószínűséggel teszi meg. A valószínűség exponenciálisan csökken a lépés "rosszaságával" - azzal a &delta;(E) < 1 mennyiséggel, amivel a kiértékelő függvény értéke romlott. 

'''CSP''' - kényszerkielégítési problémamegoldás esete: A ~ esetén heurisztikus javító módszer szerint az új konfiguráció a lehető legkevesebb konfliktust generálja.

==31. Mi az egyszerűsített memória korlátos A* (EMA*) keresés alapötlete?==
A rendelkezésünkre álló összes memóriát felhasználjuk. Ha elfogy a memória, akkor a legnagyobb költségű út kifejtését töröljük a memóriából (annak költségét a szülő csomópontban feljegyezzük).

==32. Mi a kétirányú keresés gondolata?==
A kétirányú keresés alapgondolata, hogy egyszerre két irányból indítjuk el a keresést (egyiket a kezdő, másikat a cél állapotból) és akkor fejeződik be a keresés, ha a két keresés valahol találkozik.

==33. Mik a kétirányú keresés problémái?==
Nem biztos, hogy tudunk a célállapotból visszafelé haladni. A két keresés találkozásának detektálását meg kell oldani. Ehhez legalább az egyik fát a memóriában kell tartani. Meg kell oldani, hogy a találkozás detektálás lineáris költségü legyen. (pl.: hash)

==34. Milyen keresési stratégiákat ajánlana implementálni a kétirányú keresésnél?==
Mindenképpen érdemes legalább az egyik iránynak szélességi (vagy ahhoz hasonló, pl. egyenletes költségű) keresést választani, mivel ez az összes kifejtett csomópontot számon tartja. Lényegi kérdés ugyanis, hogy észrevegyük, hogy a két irányból indított keresés összetalálkozott.

==35. Mi a hegymászó keresés és milyenek a tipikus problémái?==
A keresés valójában csak egy ciklus, ami mindig a javuló érték felé lép. Az algoritmus nem tart nyílván keresési fát, ezért a csomópontot leíró adatszerkezetnek csak az állapotot, és a kiértékelését kell nyilván tartania.

*Problémák*:
* lokális maximumok a globális maximumhoz viszonyítva olyan csúcs, ami alacsonyabb az állapottér legmagasabb csúcsánál, ha eléri, akkor leragad
* fennsík egy olyan terület, ahol a kiértékelhető függvény gyakorlatilag lapos, ilyenkor bolyong, vagy leáll
* hegygerincek oldalai meredekek lehetnek és lehet, hogy a keresés oszcillál a hegygerinc két csúcsa között és csak lassan halad előre 

==36. Mi a legjobbat-először keresés?==
Kiértékelő függvény: egy csomópont kifejtésének szükségességét leíró szám. Ha a csomópontokat úgy rendezzük sorba, hogy a legjobb kiértékelő függvény értékkel rendelkező csomópontot fejtjük ki, akkor a legjobbat-először keresést kapjuk.

==37. Mitől "mohó" a mohó keresés?==
Mert az irányító heurisztikában mérve mindig "nagyot" akar lépni ahelyett, hogy az út globális optimitálitásával törődne.

==38. Mi az A* keresés keresési stratégiája?==
F(n) = G(n) + H(n), azaz a megtett út és a heurisztika összege alapján keresek.

==39. Milyen információt használ ki az A* keresési algoritmus?==
F(n) = G(n) + H(n), azaz a megtett út és a heurisztika összegét.

==40. Mi a szimulált lehűtés alapgondolata, milyen problémát hívatott orvosolni?==
Ha a lokális maximumban ragadt keresést nem indítjuk újra, hanem megengedjük neki, hogy néhány lefelé vezető lépést tegyen azért, hogy elmenjen a lokális maximumból szimulált, lehűtésnek nevezzük.

==41. A kereső algoritmusok körében mit jelent a komplexitás, a teljesség, és az optimalitás? Elemezze ilyen szempontból az A* algoritmust!==
* komplexitás: idő és tárigény (A*: exponenciális a valós problémákra)
* teljes: ha létezik megoldás, akkor megtalálja (A* teljes)
* optimális: a legjobb létező megoldást találja meg (A* optimális)

==42. Milyen információt használ ki az A* keresési algoritmus a megoldás megfogalmazásához?==
A heurisztikát meg az útköltséget.

==43. Milyen lényegi javításokat tartalmaz az A* keresési algoritmus a gradiens típusú keresési algoritmusokhoz képest?==
Az A* figyelembe veszi a megtett utat és a célig előretekint. Ellenben a gradiens nem veszi figyelembe a megtett utat, és csak közvetlen szomszédjáig néz előre.

==44. A keresés miért egy kulcsfontosságú téma az intelligens rendszerek témakörben?==
A cél eléréséhez a megfelelő cselekvéseket kereséssel választja ki a rendszer.

==45. Mivé fajul, és miért az egységnyi operátor költségű, zérus heurisztikával dolgozó A* keresési eljárás?==
Szélességi kereséssé.

==46. Mohó-e az A* keresési algoritmus? A válaszát feltétlenül indokolja meg!==
Nem, mert egyrészt figyelembe veszi a jövőbeli költségek egy becslését is, nem csak az eddig megtett utat; másrészt egyenletes költségű keresést végez, tehát tájékozódik az összes lehetőségről, mielőtt továbblépne.


[[Category:Infoalap]]