https://vik.wiki/index.php?action=history&feed=atom&title=3._Probl%C3%A9mamegold%C3%A1s_keres%C3%A9ssel3. Problémamegoldás kereséssel - Laptörténet2026-05-12T02:33:47ZAz oldal laptörténete a wikibenMediaWiki 1.43.8https://vik.wiki/index.php?title=3._Probl%C3%A9mamegold%C3%A1s_keres%C3%A9ssel&diff=137704&oldid=prevUnknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|MIOsszefoglaloProblemamegoldasKeresessel}} __TOC__ ==Általános tudnivalók, tételek, definíciók== ===3.1 Problémamegoldó ágensek==…”2012-10-21T20:05:44Z<p>Új oldal, tartalma: „{{GlobalTemplate|Infoalap|MIOsszefoglaloProblemamegoldasKeresessel}} __TOC__ ==Általános tudnivalók, tételek, definíciók== ===3.1 Problémamegoldó ágensek==…”</p>
<p><b>Új lap</b></p><div>{{GlobalTemplate|Infoalap|MIOsszefoglaloProblemamegoldasKeresessel}}<br />
<br />
<br />
__TOC__<br />
<br />
==Általános tudnivalók, tételek, definíciók==<br />
<br />
===3.1 Problémamegoldó ágensek===<br />
<br />
Célvezérelt ágens egy típusa: olyan cselekvés sorozatokat keres, amelyek kívánt állapotokba vezetnek. (Az ágens egy célt tud kitűzni maga elé és megpróbálja azt elérni.)<br />
<br />
*Cél megfogalmazás*: A probléma megoldás első lépése, amikor a cél megfogalmazás során az ágens olyan tényezőket akar figyelembe venni, melyek hatással vannak a cél elérhetési módjának az ágens által megítélt hasznosságára.<br />
<br />
*Cél*: A világ állapotainak egy olyan részhalmaza, amelyekben a cél teljesül.<br />
<br />
*Cselekvések*: Hatására a világ állapotai közötti állapotátmenetek mennek végbe, az ágensnek nyilvánvalóan azt kell megkeresnie, hogy mely cselekvések juttatják el egy célállapotba.<br />
<br />
===3.2 Problémamegfogalmazás===<br />
<br />
A problémamegfogalmazás a cél megfogalmazását követő folymat, mely során eldönti, hogy mely cselekvések és állapotokat vegyen figyelembe.<br />
<br />
*Keresés*: amennyiben az ágens előtt közvetlenül több ismeretlen értékű lehetőség áll, ki tudja választani, hogy mit tegyen: ha megvizsgálja a lehetséges cselekménysorozatokat, melyek ismert értékű állapotokba vezetnek és ezek közül kiválasztja a legjobbat.<br />
<br />
*Problémák*: négy lényegileg eltérő probléma típus<br />
* ''Egy-állapotú'' problémák: az ágens pontosan tudja, melyik állapotban van, tudja a cselekévsei következményeit, meg tudja határozni a cél érdekében szükséges cselekvéssoroztatot.<br />
* ''Több-állapotú'' problémák: az ágens ismeri az összes cselekvésének a hatását, de nem ismeri az aktuális állapotát az állapothalmazból (előfordulhat, hogy egyetlen érzékelővel sem rendelkezik). Ekkor a kiindulási állapottól függetlenül kell megoldást találnia az összes lehetésges állapot és átmenet ismeretének segítségével.<br />
* ''Eshetőségi'' problémák: az ágensnek a cselekvések egy teljes fáját kell kiszámítania, nem pedig egyetlen cselekvéssorozatot. A fa minden egyes ága egy lehetséges felmerülő eshetőséggel foglalkozik. Néha a tudatlanság megakadályozza az ágenst egy garantált megoldás megtalálásában. Nem létezik rögzített cselekvés sorozat, amely ebben az esetben garantálná a megoldást.<br />
* ''Felfedezési'' problémák: az ágens semmilyen információval nem rendelkezik a cselekvései hatásáról. (térkép nélkül eltévedünk egy idegen országban). Ki kell kísérleteznie a létező állapotokat, és cselekvéseinek hatását. Ez a legnehezebb feladat, amivel egy intelligens ágens találkozhat.<br />
<br />
'''Jól definiált''' probléma:<br />
* ''kiinduló állapot'' (ágens tudja, hogy abban az állapotban van)<br />
* _operátorok_: ágens rendelkezésére álló lehetséges cselekvések halmaza - állapotátmenetek, egy cselekvés leírása, a cselekvés egy adott állapotban történő alkalmazásának hatására az ágens mely állapotba kerül<br />
* ''állapottere'' azon állapotok, melyek a kiindulási állapotból valamilyen cselekvési sorozattal elérhetőek<br />
* _célteszt_: egy állapotról megállapítja, hogy célállapot-e<br />
* _útköltség_: az utat alkotó cselekvések költségének összege<br />
* A '''megoldás''' a keresési algoritmus kimenete: a kiindulási állapotból egy olyan állapotba vezető út, amely teljesíti a céltesztet.<br />
<br />
'''Több állapotú, jól definiált''' probléma:<br />
* ''kiinduló állapothalmaz''<br />
* ''operátorok''<br />
* ''célteszt''<br />
* ''útköltség''<br />
* a '''megoldás''' egy út, mely olyan állapothalmazba vezet, ahol minden állapot célállapot<br />
<br />
A *keresési költség*: a megoldás megtalálásához szükséges idő, és memóriaszükségelet.<br />
<br />
'''Keresés hatékonyság''' mérése:<br />
* egyáltalán talál-e megoldást - célteszt teljesítése.<br />
* a megtalált megoldás jó megoldás-e - alacsony útköltségű <br />
* keresési költség<br />
<br />
A keresés összköltsége: az útköltség és a a keresési költség összege.<br />
<br />
(Anytime algoritmus: már a 0. időpillanatban is ad választ, és azt az idő elteltével folyamatosan javítja, így a rendelkezésre álló időt teljesen kihasználva ad megoldást)<br />
<br />
===3.3 Példaproblémák===<br />
<br />
Játékproblémák:<br />
* 8-as kirakójáték<br />
* 8 királynő sakktáblán<br />
* Hittérítők - kanibálok<br />
<br />
Valósvilág-beli problémák:<br />
* utazó-ügynök probléma (Traveling Salesperson Problem) - NP by [[AlgEl]]<br />
* VLSI<br />
<br />
===3.4 Megoldások keresése===<br />
<br />
*Keresés*: új állapotok generálása - az állapot kifejtése.<br />
<br />
*Keresési stratégia*: ez határozza meg a kifejtendő állapot kiválasztását.<br />
<br />
*Csomópontok*: öt komponensből álló adatszerkezet<br />
* a csomóponthoz tartozó állapottér állapot<br />
* a keresési fa azon csomópontja, amely ezen csomópontot generálta (szülő csomópont)<br />
* a csomópontot generáló operátor<br />
* a gyökér csomóponttól eddig a csomópontig vezető út csomópontjainak a száma (a csomópont mélysége)<br />
* a kiinduló állapottól a csomópontig számított út költsége<br />
<br />
*Összegezve*: a csomópont nem az állapot, a csomópont egy adatszerkezet; egy állapot a világ egy konfigurációja. A csomópont rendelkezik mélységgel és szülővel, míg az állapot nem.<br />
<br />
===3.5 Keresési stratégiák===<br />
<br />
*Négy kritérium*:<br />
* teljesség: a stratégia garantáltan megtalálja a megoldást, amennyiben létezik<br />
* időigény: mennyi ideig tart egy megoldás megtalálása<br />
* tárigény: a keresés elvégzéséhez mennyi memóriára van szükség<br />
* optimalitás: a stratégia megtalálja a legjobb minőségű megoldást, amikor több különböző megoldás létezik<br />
<br />
'''Vak keresési módszerek''' (nem informált keresés): Semmilyen információnk nincs az aktuális állapotból a célállapotba vezető út lépésszámáról vagy út költségéről. Ezen keresési algoritmusok csak annyira képesek, hogy meg tudják különböztetni a célállapotokat a nem célállapotoktól.<br />
<br />
* ''szélességi'' keresés: (BFS) <br />
** teljes és optimális (feltéve hogy az útköltség a csomópont mélységének nemcsökkenő függvénye)<br />
** amennyiben a megoldás egy d hosszú út, a csomópontok száma O(b<sup>d</sup>)<br />
** tárigény > időigény<br />
* egyenletes költségű keresés (uniform cost search): a hullámfront legkisebb költségű csomópontját fejti ki<br />
* ''mélységi'' keresés: (DFS)<br />
** lineáris tárigény O(b*m), időigénye O(b<sup>m</sup>)<br />
** rossz útra keveredve elakadhat, végtelen mély ág esetén előfordulhat, hogy végtelen ciklusba ugrik, s talál az optimálisnál rosszabb megoldást.<br />
** nem teljes és nem optimális<br />
* ''mélységkorlátozott'' keresés (Depth Limited Search)<br />
** korlát a maximális mélységre, a megfelelő mélységeben vágási korlát<br />
** jól megválasztott korlát esetén teljes, de nem optimális<br />
** az állapottér átmérője igen jó mélységi korlátot ad (bármely pont elérhető legfeljebb az átmérő hosszú úttal minden pontból)<br />
* ''iteratívan mélyülő'' keresés (Iterative Deeping Search - IDS)<br />
** mélységkorlátozott keresések egymás után, egyre növekvő mélységgel<br />
** optimális, teljes kicsi forrásigénnyel rendelkezik<br />
** hátránya hogy töbször fejti ki ugyanazon csomópontokat, ugyanakkor az elágazási tényező növelésével csökken a redundancia<br />
** általánosságban nagy keresési tér esetén, ha a megoldás mélysége nem ismert, akkor az IDS a javasolt alkalmazás<br />
* ''kétirányú keresés''<br />
** a start és cél állapotból egyszerre indítja el a keresést, ezáltal a gyorsabb lesz<br />
** felmerülő problémák: elődcsomópontok megtalálása, ha az összes operátor reverzibilis, több célállapot esetén - állapothalmaz fogalma. A frissen generált állapot már nem létezik-e a másik irányú fában. A két irányban akár különböző keresési mód is választható, melyiket érdemesebb<br />
** tárigénye következménye annak hogy legalább az egyik részfa összes csomópontját tárolni szükséges<br />
<br />
*A keresési stratégiák összehasonlítása*:<br />
<br />
{| border="1"<br />
|*Kritérium * ||*Szélességi* ||*Egyenletes költségű* ||*Mélységi* ||*Mélység-korlátozott*||*Iteratívan mélyülő* ||*Kétirányú (amennyiben alkalmazható)*<br />
|-<br />
|*Idő igény* || B<sup>d</sup> || b<sup>d</sup> || b<sup>m</sup> || b<sup>l</sup> || b<sup>d</sup> || b<sup>d/2</sup> <br />
|-<br />
|*Tár igény* || B<sup>d</sup> || b<sup>d</sup> || bm || bl || bd || b<sup>d/2</sup> <br />
|-<br />
|*Optimális?* || Igen || Igen || Nem || Nem || Igen || Igen <br />
|-<br />
|*Teljes?* || Igen || Igen || Nem || Igen, ha l >= d || Igen || Igen <br />
|}<br />
<br />
<br />
*A keresési stratégiák értékelése*:<br />
* b az elágazási tényező: minden egyes új állapotot kifejtve b darab új állapot jelenik meg.<br />
* d a megoldás mélysége<br />
* m a keresési fa maximális mélysége<br />
* l a mélység korlát.<br />
<br />
*Tanulság*: A tárigénnyel el tudunk bánni, de az időigény exponenciális marad. Lásd [http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=9449 2005. nov. 4. zh megoldása].<br />
<br />
===3.6 Ismételt állapotok elkerülése===<br />
<br />
Ne térjen vissza az eggyel korábbi állapotba, kört tartalmazó út létrehozása tilos, korábban létrehozott állapot újralétrehozása elkerülendő.<br />
<br />
===3.7 Kényszerkielégítéses keresés (CSP - Constraint Statiction Problem)===<br />
<br />
Az állapotokat a változók értékei határozzák meg és a célfüggvényt a kényszerek halmaza adja meg, melyeknek teljesülnie kell az elfogadáshoz.<br />
<br />
* ''visszalépés'' (backtracking): a követő csomópont generálása ''előtt'' ellenőrizzük, hogy az idáig megtett változó hozzárendelések nem sértették-e meg valamelyik kényszert.<br />
* ''előretekintés'' (forward checking): a változók értékkapásakor az értékkel még nem rendelkező válozók értékkészletéből törli az eddigi feltételek által létrehozott kényszerekkel ellentétes értékeket.<br />
* ''élkonzisztencia'' (TK. - 121 vagy 192)<br />
<br />
<br />
<br />
==12. Miért beszélünk arról, hogy nagy különbség lehet egy probléma "elvi", illetve gyakorlati megoldása között?==<br />
Az elvi, tehát optimális megoldás megtalálása exponenciáils idő-, és tárigényt igényelhet, ezért törekszünk az optimálist csak közelitő gyakorlati megoldás megkeresésére (az elvit nehezebb megtalálni).<br />
<br />
==13. Milyen elemekből áll össze a problémamegoldás formális modellje - a problématér O(b<sup>d</sup>) modell?==<br />
Kiinduló állapot, lehetséges cselekvések halmaza(Operátorok).<br />
<br />
==14. Mik az un. "jól definiált" probléma komponensei?==<br />
Kiinduló állapot, operátorok, célteszt, útköltség.<br />
<br />
==15. Mire utal az "informált" jelző bizonyos keresési módszereknél?==<br />
Probléma specifikus tudást alkalmazó keresés.<br />
<br />
==16. Mit jelent, hogy a keresés nem informált?==<br />
Nincs információnk az aktuális állapotból a célállapotba vezető út lépésszámáról, vagy az út költségéről.<br />
<br />
==17. Milyen heurisztikát nevezünk elfogadhatónak?==<br />
h(n) elfogadható: mindig kisebb értéket ad, mint az n csomópont állapotából a célhoz vezető legrövidebb út hossza.<br />
<br />
==18. Mi a heurisztika? Milyen egy jó heurisztika? ==<br />
h(n), az n csomópont állapotából egy cél állapotba vezető legolcsóbb út becsült költsége. A jó heurisztika értéke minél nagyobb, de elfogadható.<br />
<br />
==19. Az informált keresés mire használja fel a problémára/problémakörnyezetre vonatkozó tudást?==<br />
Optimális választáshoz az útkeresés során. Ez alapján készítjük a heurisztikus fügvényt.<br />
<br />
==20. Hogyan lehet mérni a keresés hatékonyságát?==<br />
Teljesség, optimalitás, tár-, és időigény.<br />
<br />
==21. Miért az útvonal keresési problémákhoz jó heurisztikus függvény a légvonalban mért távolság?==<br />
Mert soha nem becsüli túl a távolságot, és a szükséges utat.<br />
<br />
==22. Mi a heurisztika szerepe az intelligens rendszer működésében?==<br />
Az optimális választás segítése.<br />
<br />
==23. Mi az un. relaxált probléma, mit szolgál az ilyen problémák megfogalmazása?==<br />
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 bizonyul az eredeti problémára.<br />
<br />
==24. Mi az effektív elágazási tényező, mire szolgál és milyen egy jól megtervezett heurisztikus függvény esetén (és miért)?==<br />
Átlagosan egy csomópontból kiindulva hány utat fejt ki. Jól mutatja a heurisztikus fügvény használhatóságát. A jó heurisztikus függvény esetén az egyet közelíti.<br />
<br />
==25. Milyen alapvető kritériumokat figyelembe kell venni a keresési stratégiák összehasonlításánál?==<br />
Teljesség, optimálitás, futási időigény, tárigény (komplexitás).<br />
<br />
==26. A keresési stratégiák összehasonlításánál használt kritériumok közül melyiket tartja a legfontosabbnak és miért?==<br />
A teljesség. Mivel egy keresésnél a legfontosabb, hogy biztosan megtaláljuk a megoldást.<br />
<br />
==27. Milyen szempontok szerint szokás mérlegelni a kereső eljárásokat? Hasonlítsa össze azok felhasználásával a mélységi és a szélességi keresést!==<br />
Teljesség, optimálitás, futási időigény, tárigény (komplexitás)<br />
<br />
{| border="1"<br />
|*Kritérium * || '''Szélességi''' || '''Mélységi''' <br />
|-<br />
|*Idő igény* || B<sup>d</sup> || b<sup>m</sup> <br />
|-<br />
|*Tár igény* || B<sup>d</sup> || bm <br />
|-<br />
|*Optimális?* || Igen || Nem <br />
|-<br />
|*Teljes?* || Igen || Nem <br />
|}<br />
<br />
==28. Vesse össze a szélességi keresés jó és rossz tulajdonságait?==<br />
Először a legsekélyebben fekvő csomópontot fejti ki a fában. Teljes, azonos költségű operátorok esetén optimális, és O(b<sup>d</sup>) idő-, és tárigénnyel rendelkezik. Tárigénye miatt a legtöbb esetben nem célszerű alkalmazni.<br />
<br />
==29. Magyarázza meg az iteratívan mélyülő keresés jó tulajdonságait?==<br />
Mélységkorlátozott keresésnél a mélységkorlát megválasztása a legnehezebb. Az iteratívan mélyülő keresés megkerüli ezt a problémát mivel vegigprobálgatja az összes megoldást. Valójában ötvözi a szélességi és a mélységi keresés jó tulajdonságait. Szélességi kereséshez hasonlóan optimális, és teljes, viszont a mélységi keresés kis memóriaigényével rendelkezik. Bizonyos csomópontokat többször is kifejt, ám ez nem növeli nagyságrendileg a számításigényt.<br />
<br />
==30. Mi az iteratívan mélyülő keresés?==<br />
A cél megtalálásáig növekvő mélységkorláttal meghívja a mélységkorlátozott keresést. Teljes, és optimális. Időigénye O(b<sup>d</sup>), tárigénye O(bd).<br />
<br />
<br />
[[Category:Infoalap]]</div>Unknown user