4. Informált keresési módszerek

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Á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^m), 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 δ 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ó.

Az A* keresésről ennél jóval többet tanultunk, lásd TK138 vagy 4. előadás fóliái.

• 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:

 N = 1 + b* + (b*)2 + ... + (b*)d. 

lásd: 2005. nov. 4. zh

h2 dominálja h1-et, ha minden n csomópontra h2(n) ≥ 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
  • δ = legkisebb operátor költség
  • f* = az optimális megoldás költsége
  • => ${\frac {b\cdot f^{*}}{\delta }}<b\cdot d$
  • Ha az f költséget az iteráció során növeljük egy rögzített ε-nal (az iterációk száma arányos lesz az ε-nal) csökken a költség, de nem optimális - az eltérés legfeljebb ε lehet, neve: ε 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 δ(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.