3. Problémamegoldás kereséssel forrásának megtekintése

{{GlobalTemplate|Infoalap|MIOsszefoglaloProblemamegoldasKeresessel}}


__TOC__

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

===3.1 Problémamegoldó ágensek===
 
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.)

*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.

*Cél*: A világ állapotainak egy olyan részhalmaza, amelyekben a cél teljesül.

*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.

===3.2 Problémamegfogalmazás===

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.

*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.

*Problémák*: négy lényegileg eltérő probléma típus
* ''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.
* ''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.
* ''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.
* ''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.

'''Jól definiált''' probléma:
* ''kiinduló állapot'' (ágens tudja, hogy abban az állapotban van)
* _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
* ''állapottere'' azon állapotok, melyek a kiindulási állapotból valamilyen cselekvési sorozattal elérhetőek
* _célteszt_: egy állapotról megállapítja, hogy célállapot-e
* _útköltség_: az utat alkotó cselekvések költségének összege
* A '''megoldás''' a keresési algoritmus kimenete: a kiindulási állapotból egy olyan állapotba vezető út, amely teljesíti a céltesztet.
	
'''Több állapotú, jól definiált''' probléma:
* ''kiinduló állapothalmaz''
* ''operátorok''
* ''célteszt''
* ''útköltség''
* a '''megoldás''' egy út, mely olyan állapothalmazba vezet, ahol minden állapot célállapot

A *keresési költség*: a megoldás megtalálásához szükséges idő, és memóriaszükségelet.

'''Keresés hatékonyság''' mérése:
* egyáltalán talál-e megoldást - célteszt teljesítése.
* a megtalált megoldás jó megoldás-e - alacsony útköltségű 
* keresési költség

A keresés összköltsége: az útköltség és a a keresési költség összege.

(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)

===3.3 Példaproblémák===

Játékproblémák:
* 8-as kirakójáték
* 8 királynő sakktáblán
* Hittérítők - kanibálok

Valósvilág-beli problémák:
* utazó-ügynök probléma (Traveling Salesperson Problem) - NP by [[AlgEl]]
* VLSI

===3.4 Megoldások keresése===

*Keresés*: új  állapotok generálása - az állapot kifejtése.

*Keresési stratégia*: ez határozza meg a kifejtendő állapot kiválasztását.

*Csomópontok*: öt komponensből álló adatszerkezet
* a csomóponthoz tartozó állapottér állapot
* a keresési fa azon csomópontja, amely ezen csomópontot generálta (szülő csomópont)
* a csomópontot generáló operátor
* a gyökér csomóponttól eddig a csomópontig vezető út csomópontjainak a száma (a csomópont mélysége)
* a kiinduló állapottól a csomópontig számított út költsége

*Ö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.

===3.5 Keresési stratégiák===

*Négy kritérium*:
* teljesség: a stratégia garantáltan megtalálja a megoldást, amennyiben létezik
* időigény: mennyi ideig tart egy megoldás megtalálása
* tárigény: a keresés elvégzéséhez mennyi memóriára van szükség
* 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

'''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.

* ''szélességi'' keresés: (BFS) 
** teljes és optimális (feltéve hogy az útköltség a csomópont mélységének nemcsökkenő függvénye)
** amennyiben a megoldás egy d hosszú út, a csomópontok száma O(b<sup>d</sup>)
** tárigény > időigény
* egyenletes költségű keresés (uniform cost search): a hullámfront legkisebb költségű csomópontját fejti ki
* ''mélységi'' keresés: (DFS)
** lineáris tárigény O(b*m), időigénye O(b<sup>m</sup>)
** 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.
** nem teljes és nem optimális
* ''mélységkorlátozott'' keresés (Depth Limited Search)
** korlát a maximális mélységre, a megfelelő mélységeben vágási korlát
** jól megválasztott korlát esetén teljes, de nem optimális
** 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)
* ''iteratívan mélyülő'' keresés (Iterative Deeping Search - IDS)
** mélységkorlátozott keresések egymás után, egyre növekvő mélységgel
** optimális, teljes kicsi forrásigénnyel rendelkezik
** 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
** á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
*  ''kétirányú keresés''
** a start és cél állapotból egyszerre indítja el a keresést, ezáltal a gyorsabb lesz
** 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
** tárigénye következménye annak hogy legalább az egyik részfa összes csomópontját tárolni szükséges

*A keresési stratégiák összehasonlítása*:

{| border="1"
|*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ó)*
|-
|*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>  
|-
|*Tár igény*	||  B<sup>d</sup>  ||  b<sup>d</sup>  ||  bm  ||  bl  ||  bd  ||  b<sup>d/2</sup>  
|-
|*Optimális?*  ||  Igen  ||  Igen  ||  Nem  ||  Nem  ||  Igen  ||  Igen  
|-
|*Teljes?*	  ||  Igen  ||  Igen  ||  Nem  ||  Igen, ha l >= d  ||  Igen  ||  Igen  
|}


*A keresési stratégiák értékelése*:
* b az elágazási tényező: minden egyes új állapotot kifejtve b darab új állapot jelenik meg.
* d a megoldás mélysége
* m a keresési fa maximális mélysége
* l a mélység korlát.

*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].

===3.6 Ismételt állapotok elkerülése===

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ő.

===3.7 Kényszerkielégítéses keresés (CSP - Constraint Statiction Problem)===

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.

* ''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.
* ''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.
* ''élkonzisztencia'' (TK. - 121 vagy 192)
 


==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?==
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).

==13. Milyen elemekből áll össze a problémamegoldás formális modellje - a problématér O(b<sup>d</sup>)  modell?==
Kiinduló állapot, lehetséges cselekvések halmaza(Operátorok).

==14. Mik az un. "jól definiált" probléma komponensei?==
Kiinduló állapot, operátorok, célteszt, útköltség.

==15. Mire utal az "informált" jelző bizonyos keresési módszereknél?==
Probléma specifikus tudást alkalmazó keresés.

==16. Mit jelent, hogy a keresés nem informált?==
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.

==17. Milyen heurisztikát nevezünk elfogadhatónak?==
h(n) elfogadható: mindig kisebb értéket ad, mint az n csomópont állapotából a célhoz vezető legrövidebb út hossza.

==18. Mi a heurisztika? Milyen egy jó heurisztika? ==
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ó.

==19. Az informált keresés mire használja fel a problémára/problémakörnyezetre vonatkozó tudást?==
Optimális választáshoz az útkeresés során. Ez alapján készítjük a heurisztikus fügvényt.

==20. Hogyan lehet mérni a keresés hatékonyságát?==
Teljesség, optimalitás, tár-, és időigény.

==21. Miért az útvonal keresési problémákhoz jó heurisztikus függvény a légvonalban mért távolság?==
Mert soha nem becsüli túl a távolságot, és a szükséges utat.

==22. Mi a heurisztika szerepe az intelligens rendszer működésében?==
Az optimális választás segítése.

==23. Mi az un. relaxált probléma, mit szolgál az ilyen problémák megfogalmazása?==
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.

==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)?==
Á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.

==25. Milyen alapvető kritériumokat figyelembe kell venni a keresési stratégiák összehasonlításánál?==
Teljesség, optimálitás, futási időigény, tárigény (komplexitás).

==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?==
A teljesség. Mivel egy keresésnél a legfontosabb, hogy biztosan megtaláljuk a megoldást.

==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!==
Teljesség, optimálitás, futási időigény, tárigény (komplexitás)

{| border="1"
|*Kritérium *  || '''Szélességi'''  || '''Mélységi''' 
|-
|*Idő igény*	||  B<sup>d</sup>  ||	b<sup>m</sup>  
|-
|*Tár igény*	||  B<sup>d</sup>  ||  bm  
|-
|*Optimális?*  ||  Igen  ||  Nem  
|-
|*Teljes?*	  ||  Igen  ||  Nem  
|}

==28. Vesse össze a szélességi keresés jó és rossz tulajdonságait?==
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.

==29. Magyarázza meg az iteratívan mélyülő keresés jó tulajdonságait?==
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.

==30. Mi az iteratívan mélyülő keresés?==
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).


[[Category:Infoalap]]