„4. Informált keresési módszerek” változatai közötti eltérés
Új oldal, tartalma: „{{GlobalTemplate|Infoalap|MIOsszefoglaloInformaltKereses}} __TOC__ ==Általános tudnivalók, tételek, definíciók== ===4.1 Legjobbat-először keresés (Best-Fir…” |
Nincs szerkesztési összefoglaló |
||
| 10. sor: | 10. sor: | ||
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. | 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ő | 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==== | ====Mohó keresés==== | ||
Minimalizálja a cél eléréséhez szükséges becsült költséget: | 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 | * 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 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''' | * 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 | * 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 | ||
| 42. sor: | 42. sor: | ||
TK 134. oldal szerint a mohó, és az egyenletes költségű ötvözése az A*, ami így nem mohó. | 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 | <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*: | *Példa*: | ||
| 73. sor: | 73. sor: | ||
** => <math> \frac{b\cdot f^*}{\delta} < b \cdot d </math> | ** => <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 ε-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ó*. | ** 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 | * 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=== | ===4.4 Iteratívan javító algoritmusok=== | ||
| 91. sor: | 91. sor: | ||
==31. Mi az egyszerűsített memória korlátos A* (EMA*) keresés alapötlete?== | ==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ő | 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?== | ==32. Mi a kétirányú keresés gondolata?== | ||
| 106. sor: | 106. sor: | ||
*Problémák*: | *Problémák*: | ||
* lokális maximumok a globális maximumhoz viszonyítva olyan csúcs, ami | * 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 | * 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 | ||
| 114. sor: | 114. sor: | ||
==37. Mitől "mohó" a mohó keresés?== | ==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 | 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?== | ==38. Mi az A* keresés keresési stratégiája?== | ||
| 125. sor: | 125. sor: | ||
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. | 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 | ==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) | * 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) | * teljes: ha létezik megoldás, akkor megtalálja (A* teljes) | ||
| 133. sor: | 133. sor: | ||
A heurisztikát meg az útköltséget. | A heurisztikát meg az útköltséget. | ||
==43. Milyen lényegi javításokat tartalmaz az A* keresési algoritmus a gradiens | ==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. | 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. | ||