3. Problémamegoldás kereséssel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

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

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^d)
  • 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^m)
  • 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*:

*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*	Bd	bd	bm	bl	bd	bd/2
*Tár igény*	Bd	bd	bm	bl	bd	bd/2
*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 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^d) 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)

*Kritérium *	Szélességi	Mélységi
*Idő igény*	Bd	bm
*Tár igény*	Bd	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^d) 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^d), tárigénye O(bd).