7. tétel Flashcards
(24 cards)
Állapottér reprezentációja gráffal és fával
▪ Állapottér: kezdeti állapot és állapotátmenet fv. definiálja
▪ Állapottér reprezentálása: gráf vagy fa
* Ha egy állapotot több csúcson keresztül is elérhetünk, akkor gráf.
Keresési algoritmusok osztályozása
- Módosítható-e valahogy egy, már alkalmazott művelet hatása?
o Nem módosítható keresők
o Módosítható keresők - Használunk-e valamiféle speciális tudást a keresés során?
o Nem informált (vak, szisztematikus) keresők: semmilyen
információjuk nincs az állapotokról a probléma definíciójában
megadott információn kívül.
o Informált (heurisztikus) keresők: tudják, hogy az egyik
közbülső állapot ígéretesebb-e, mint egy másik közbülső
állapot. - Milyen irányú a keresés?
o Előre haladó (adatvezérelt) kereső: a kezdő állapotból
kiindulva keresünk célállapotba vezető utat.
o Visszafelé haladó (célvezérelt) kereső: a célállapotból kiindulva
visszafelé haladva próbáljuk rekonstruálni a kezdőállapotból
odavezető utat.
o Kétirányú kereső: mindkét irányból elindul és valahol
találkozik.
Keresőfával kereső algoritmusok általános működése, az algoritmusok kiértékelése
Adatbázisa az állapottér-gráf egy fává egyenesített része. Az adatbázisban tárolt fa csúcsait két csoportra osztjuk:
* Zárt csúcsok (CLOSED): a már korábban kiterjesztett csúcsok.
* Nyílt csúcsok (OPEN): a még ki nem terjesztett csúcsok.
Művelet: nyílt csúcs kiterjesztése – a csúcs gyerekeinek az előállítása.
Vezérlő működése:
1. Tedd a kezdeti állapotokat az OPEN-be!
2. Amíg OPEN nem üres:
2.1. Vegyünk egy N csúcsot az OPEN-ből.
2.2. Ha N célállapot, akkor:
2.2.1. leállás – eredmény megadása
2.3. Különben:
2.3.1. N törlése OPEN-ből
2.3.2. N kiterjesztése: N gyerekeinek hozzáadása az OPEN-hez.
3. Sikertelenség kiírása
Az algoritmusok kiértékelése:
* Teljesség: ha van megoldás, azt az eljárás megtalálja.
* Optimalitás: ha több megoldás létezik, akkor megtalálja a legjobbat (legalacsonyabb költségűt).
* Időigény: mennyi időre van szükség a megoldás megkereséséhez.
* Tárigény: mennyi memóriára van szükség a megoldás megkereséséhez.
Vak keresések
Szélességi, mélységi, korlátozott mélységű mélységi, iteratívan mélyülő mélységi, egyenletes költségű keresés.
Szélességi keresés
o Kiterjesztés: a legrégebben bekerült csúcs (FIFO: OPEN lista - sor)
o Teljes
o Optimális (ha az útköltség a csomópont mélységének nem csökkenő függvénye)
o Időigény = memóriaigény: 𝑂(𝑏𝑑+1), ahol b a szomszédok maximális száma, d a legkisebb mélységű célállapot mélysége
Mélységi keresés
o Kiterjesztés: LIFO (OPEN lista - verem)
o Csak akkor teljes, ha a keresési fa véges költségű.
o Nem optimális
o Időigény: 𝑂(𝑏𝑚), ahol b a szomszédok maximális száma, m a keresőfa maximális mélysége
o Memóriaigény: 𝑂(𝑏 ∗ 𝑚)
Korlátozott mélységű mélységi keresés
o Mélységi keresés mélységi korláttal
o A keresési fában mindig a legmélyebben lévő csomópontok valamelyikét terjeszti ki, feltéve, hogy nincs egy előre adott mélységi korlát (l) alatt.
o 𝑙 < 𝑑 esetén nem teljes o 𝑙 > 𝑑 esetén nem optimális
o Időigény: 𝑂(𝑏𝑙)
o Memóriaigény: 𝑂(𝑏 ∗ 𝑙), ahol b a szomszédok maximális száma, d a legkisebb mélységű célállapot mélysége, l a mélységi korlát.
Iteratívan mélyülő mélységi keresés
o Korlátozott mélységű keresés egyre növekvő mélységi korláttal.
o Redundáns, ennek ellenére ez a legjobb informálatlan kereső. o A teljesség és optimalitás a szélességi kereséssel egyezik meg.
o Időigény: 𝑂(𝑏𝑑)
o Memóriaigény: 𝑂(𝑏 ∗ 𝑑), ahol b a szomszédok maximális száma, d a legkisebb mélységű célállapot mélysége.
Egyenletes költségű keresés
o Kiterjesztés: először a legkisebb költségű csúcs
o Csak akkor teljes, ha minden él költsége ≥ > 0
o Csak akkor optimális, ha minden él költsége ≥ > 0
o Időigény = memóriaigény: 𝑂(𝑏1+(𝐶∗/ )), ahol b a szomszédok maximális száma, C* az optimális megoldás költsége.
Heurisztikus kereső algoritmusok, heurisztika
mohó legjobbat először keresés, A* algoritmus, iteratívan mélyülő A* algoritmus, rekurzív legjobbat először keresés
Heurisztika: gyakorlati tapasztalat vagy módszer, ami segít a cél elérésében és segít dönteni, hogy melyik választás a jobb.
A heurisztikus kiértékelő függvény a probléma egy állapotához egy számot rendel. Célja a feladat megoldásával járó számításigény csökkenése és adott erőforrás használat mellett a lehető legjobb megoldás megtalálása.
A keresett objektum költsége (f(n)) = megtett út költsége (g(n)) + hátralévő út költsége (h(n))
Mohó legjobbat először keresés
o A kiértékelés alapja egyedül a céltól becsült távolság alapján (f(n) = h(n)) o Azt a csomópontot fejti ki a következő lépésben, amelyiknek az állapotát a legközelebbinek ítéli a célállapothoz (becslés).
o Az OPEN lista f(n) alapján rendezett.
o Teljes, de csak akkor, ha a keresési fa véges mélységű és ha n célcsúcs, akkor f(n) = 0
o Nem optimális
o Időigény = memóriaigény = 𝑂(𝑏𝑚)
A* algoritmus
o Figyelembe veszi a meglátogatott csúcsok eléréséhez szükséges költséget is
(f(n) = g(n) + h(n)).
o Az OPEN listáról azt az elemet terjeszti ki, amelyiknek a legkisebb az f(n) értéke. o Az OPEN lista f(n) alapján rendezett.
o A memóriaigényt a heurisztika határozza meg (ha h(n) = 0, akkor a keresés egyenletes, ha h(n) egy tökéletes becslés, akkor az algoritmus egyenesen a célba megy).
Iteratívan mélyülő A* algoritmus
o Az iteratívan mélyülő mélységi algoritmus adaptálása heurisztikus keresésre. o Mélységi korlát helyett jósági korlát f(n)-re.
o Jósági korlát meghatározása: hatékonyabb, ha az aktuális korlátot nem léptetve növeli, hanem az előző iterációs ciklusban választja ki. A vágási érték az a legkisebb f költség, ami az előbbi iterációban használt vágási értéknél nagyobb.
Rekurzív legjobbat először keresés
o A mohó legjobbat először algoritmuson alapul.
o Tárolja a rendelkezésre álló legjobb alternatíva f értékét. Ha az aktuális f érték meghaladja azt, akkor visszalép a legjobb alternatíva útjára. A visszalépés közben lecseréli az elhagyott ág f értékét a legjobb gyerekének f értékére, így az elhagyott ág újból folytatható. o Optimális algoritmus, feltéve, hogy a h(n) heurisztikus függvény elfogadható.
Lokális kereső algoritmusok, működésük
hegymászó algoritmus, szimulált lehűtés algoritmusa.
A lokális keresők egyetlen állapottal, az aktuálissal foglalkoznak és az egyik szomszédos állapotukba viszi át őket. A megoldási utat nem kell nyilvántartani, ennél fogva minden keresés lokális. Működésük lényege egy optimalizációs eljárás, melyben egy célfüggvény értékét próbálják maximalizálni / minimalizálni.
Működésük általános algoritmusa:
1. Válasszunk egy véletlen kezdőállapotot.
2. Értékeljük ki az állapotra jellemző célfüggvényt.
3. Hajtsunk végre lokális módosítást ezen az állapoton (lépjünk egy szomszéd állapotba).
4. Ismételjünk a 2. lépéstől addig, míg a célállapotba nem érünk, vagy nincs az algoritmusnak megfelelő lokális módosítás.
Előnye, hogy kis memóriaigényű, valamint nagy vagy végtelen keresési térben jobban alkalmazható. Ezen esetekhez ésszerű megoldást talál.
Hegymászó keresés
o A keresés egy ciklus, ami mindig a leginkább javuló értékek irányába lép.
o Az algoritmus megáll, amikor felér egy olyan csúcsra, ahol nincsenek már magasabb értékű szomszédjai.
o Gyors, viszont gyakran lokális minimumot / maximumot talál
Szimulált lehűtés algoritmus
o Cél a lokális maximumok / minimumok kiküszöbölése. o A hegymászó algoritmus és véletlen séta kombinációja.
o Ellentétben a hegymászó algoritmussal, nem a legjobb szomszéd irányába megy, hanem random választ a szomszédok közül. Ha a kiválasztott szomszédos állapot jobb, mint a jelenlegi, akkor odalép. Ha rosszabb, akkor 1-nél kisebb valószínűséggel választja, vagy nem csinál semmit.
Populáció keresők
nyaláb keresés, PSO algoritmus, genetikus algoritmus
Nyaláb keresés
o A hegymászó algoritmus általánosítása populációval.
o k db véletlen állapotból indul ki. Minden ciklusban veszi ezen populációk közvetlen követőit, s ezen halmazból a k db legjobbat választja következő állapotoknak. o Hátránya, hogy az állapotok gyorsan koncentrálódhatnak a tér egy kis részére.
Részecske raj optimalizálás (PSO) algoritmus
o Alapgondolata: a részecskék a rajban a lehetséges megoldásokat jelképezik. Minden részecske az optimumot keresi. Minden részecske mozog és van egy sebessége. Minden részecske emlékszik az eddigi legjobb pozíciójára. A részecskék a rajban kooperálnak. Kicserélik az információt azokról a helyekről, ahol már jártak.
o A sebességet befolyásolja a részecskék tehetetlensége, az eddigi saját legjobb pozíciója, a raj eddigi legjobb pozíciója. o Komponensei:
▪ Kognitív komponens: saját tapasztalat
▪ Szociális komponens: hit a társak tapasztalatában
Genetikus algoritmus
o Alapötlet: genetika és a természetes kiválasztódás o Fogalmak:
▪ Egyed: egy lehetséges megoldás / állapot.
▪ Populáció: egyedek halmaza.
▪ Rátermettség (fitness-függvény): a rátermettebb egyed magasabb fitness értékkel rendelkezik.
▪ Genetikus kód: az egyed reprezentációja.
▪ Genetikus műveletek: keresztezés, mutáció
o Az algoritmus általános leírása:
▪ k db véletlen állapot kiválasztása
▪ Iteratívan ismételjük az alábbi lépéseket:
* Fitness-értékek meghatározása az egyedekre
* Egyedek kiválasztása szaporodásra (a rátermettebb egyedek
választásának valószínűsége a nagyobb)
* Új generáció létrehozása (két szülő keresztezésével vagy
mutációval)
* Leállási feltétel ellenőrzése (nem javul a fitness érték, vagy az
adott generációszámot elérjük)
Kétszemélyes játékok
Többágenses környezetben minden ágensnek számolnia kell más ágensek cselekedeteivel és azzal, hogy a többi ágens cselekedet hogyan befolyásolják az ő jólétét. A többágenses környezet lehet kooperatív és kompetitív.
A kétszemélyes játék olyan két ágenst tartalmazó versenykörnyezet, ahol az ágensek céljai konfliktusban vannak.
Kétszemélyes teljes információjú játékok tulajdonságai:
* Két játékos lép felváltva egymás után a megadott szabályok szerint.
* Mindkét játékos birtokában van a játékkal kapcsolatos összes információnak.
* Nincs szerepe a véletlennek, szerencsének.
* A játékban minden egyes állásában véges számú szabályos lépések közül lehet választani.
* A játék szabályai olyanok, hogy végtelen játszmák nem fordulhatnak elő.
* A játszmák végén az egyik játékos nyer, míg a másik veszít, ill. bizonyos esetekben döntetlen eredmény is elképzelhető.
* A játék végén a hasznosságértékek mindig azonosak, csak ellentétes előjelűek vagy döntetlenek.
Minimax algoritmus
Egy lehetséges lejátszás: célállapothoz vezető lépések szekvenciája.
Cél: a játékfát a legjobb lépés felhasználására felhasználni.
A gyökér csomópont MINIMAX értéke: a csomópont hasznossága MAX szemszögéből, feltéve, hogy MAX lép először. A nagy érték MAX-nak jó, a kisebb érték MIN-nek jó.
Algoritmusa:
1. A játékfa adott mélységű generálása.
2. Leveleknek megfelelő állások pontértékeinek meghatározása.
3. Maximális ill. minimális értékek visszaadása a fában, egészen a gyökérig.
4. Választás a gyökér értékével megegyező utódokba vezető lépések között.
Alfa-béta vágás algoritmus
Alapötlet: lehetséges a korrekt minimax döntés kiszámítása anélkül, hogy a játékfában minden csomópontra rá kelljen nézni.
Új paraméterek:
* Alfa: biztos, hogy MAX ki tudja kényszeríteni: az a minimális érték, amit MAX már biztosított magának.
* Béta: biztos, hogy MIN ki tudja kényszeríteni: az a maximális érték, amit MIN már biztosított magának.
Az alfa értékek csak növekedhetnek, a min értékek csak csökkenhetnek a kiértékelés során.
Alfa értéke: ha ismerjük egy MAX szinten lévő csúcs egyik utódjának értékét, akkor ez alsó korlátja az adott csúcs értékének. Ezt az alsó korlátot nevezzük alfa értékének.
Béta értéke: ha ismerjük egy MIN szinten lévő csúcs egyik utódjának értékét, akkor ez felső korlátja az adott csúcs értékének. Ezt az alsó korlátot nevezzük béta értékének.
Alfa vágás: egy MIN csúcs alatti kiértékelést nem kell folytatni, ha a hozzá tartozó béta érték kisebb vagy egyenlő, mint ezen csúcs valamelyik MAX őséhez tartozó alfa érték.
Béta vágás: egy MAX csúcs alatti kiértékelést nem kell folytatni, ha a hozzá tartozó alfa érték nagyobb vagy egyenlő, mint ezen csúcs valamelyik MIN őséhez tartozó béta érték.
