Mesterséges Intelligencia MI

Mesterséges Intelligencia MI Problémamegoldás kereséssel Dobrowiecki Tadeusz Eredics Péter, és mások BME I.E. 437, 463-28-99 [email protected], http://www.mit.bme.hu/general/staff/tade

optimális pályahossz = 7

Fizikai tér

Konfigurációs tér

Absztrakt tér

A reflexszerű ágens tervezője tervezés közben keresett. Reflexszerű ágensnek működés közben már nem kell keresnie. Célorientált ágens tervezője tervezés közben nem keresett. Célorientált ágens működése közben kénytelen maga keresni (kereséssel megoldani a problémáit).

A most kezdődő anyagrész kérdései – Mik a problémamegoldás lépései? – Hogyan lehet problémákat jól definiálni? – Hogyan mérhető a problémamegoldó hatékonyság? – Milyen keresési stratégiák állnak rendelkezésre? – Milyen tanulságok vonhatók le ezek komplexitásából?

– Mivel tudjuk mérsékelni a módszerek komplexitását? – Hogyan terjeszthetők e módszerek nehezebb környezetekre?

Manapság mindenki utazik, gépkocsival, repülővel, … Keressünk pénzt útvonaltervező szoftver fejlesztésével! A (helyettünk intelligens) rendszer kap két helyszínt, tudja a mozgási (utazási) lehetőségeket, dolgozik, … és kiad egy úttervet. Sima ügy. Miért? A probléma nem más, mint egy gráfban – melynek élei súlyozottak - élutat találni két csomópont között. Gráfokat tanultunk, keresést tanultunk, optimális út megkeresését is tanultuk. Pontosabban mit is tanultunk? Előzmények: gráf, csomópont, él, út, fa, útkeresés, keresési fa, mélységi keresés, szélességi keresés, élsúly, optimális út keresése, Dijkstra-algoritmus, komplexitás, időkomplexitás, tárkomplexitás, …

és most innen kezdjünk ...

Dijkstra-algoritmus

Mi a probléma?

Dijkstra

az egy másik

és még egy másik

1.6M csúcs 3.8M él

Teljes USA úthálózat 24M csúcs, 58M él

Problémák: gráfméret - milliós csomópontok, sűrű kiszolgálás

Hatékonyságban különbségek, hogyan mérünk? Komplexitás: idő-, tár- …, pl. mélységi keresés, szélességi keresés, ... Dijkstra mennyi?

Ez sok, vagy kevés? Menni fog?

Bontás kisebb gráfokra, menni fog? Egyedi, nem ismételt feladatnál? És ha a kiszolgálások tömegesek, helyileg előre ismeretlenek? Ha ilyen sok kiszolgálás közben változnak az objektív körülmények (gráf alakja, élsúlyok, …)? Ha a gráf „előre” nem adható meg (csak pici részletben a kiindulás környezetében)? A tanult dolgokhoz képest nagyon sok kérdés, ami a módszerek tényleges használhatóságával kapcsolatos.

Példa: tili-toli (kirakó) játék, szélességi kereséssel a szg. Tianhe-1A (2015), 2.5 Pflops, 260 Tbyte tár, 2 Pbyte diszk (4 MW, 20 m$/év, 200 fős személyzet) legyen 1 csp – 1 flop, 100 byte

Méret

Csomópont (kb.)

Idő

Tár

Lépés

8-as (3 x 3)

105

40 psec

10 Mbyte

< 31

15-ös (4 x 4)

1013

4 msec

100 Tbyte

< 80

24-es (5 x 5)

1025

100 év

1000 Ybyte 152 < < 208

35-ös (6 x 6)

1041

5 Eév

?

T(era) = 1012, P(eta) = 1015, E(xa) = 1018, Z(etta) = 1021, Y(otta) = 1024 (a világűr kora kb. „csak” 14 Gév)

Legrövidebb megoldás megkeresése: NP teljes

?

Absztrakció módja = a „jól definiált” probléma megalkotása Probléma = információk gyűjteménye: (hiedelmi) állapotok + legális cselekvések Formálisan: (1) kiinduló állapot (ágensnek tudnia kell, hogy abban az állapotban van) (2) ágens által rendelkezett lehetséges cselekvések halmaza operátor = egy-egy cselekvés leírása, tipikusan

HA egy ilyen állapotban van, AKKOR majd olyan állapotban lesz a cselekvés alkalmazása után „követő állapot” függvény = egy cselekvés egy adott állapotban való alkalmazásának hatására az ágens mely állapotba kerül? ezek együtt (implicit módon megadva): a probléma állapottere: azon állapotok halmaza, amelyek a kiinduló állapotból valamilyen cselekvés sorozattal elérhetők. (nehézség: az állapottér explicite ritkán adható meg) (sakk) állapottérben út: állapotok között vezető cselekvéssorozat

(3) célteszt: az ágens el tudja dönteni, hogy az egy célállapot-e. a. a lehetséges célállapotok egy explicit halmaza - egyszerűen megnézi, hogy az ágens elérte-e ezek egyikét b. a cél valamilyen absztrakt tulajdonsággal van definiálva, pl. a sakkban az ún. „sakk-matt” helyzet (4) útköltség függvény: az úthoz hozzárendel egy költséget A keresési algoritmus kimenete - egy megoldás: a kiinduló állapotból egy olyan állapotba vezető út, amely teljesíti a cél tesztet.

A problémamegoldó hatékonyság mérése Keresés: 1. Egyáltalán talál-e megoldást. 2. A megtalált megoldás jó-e (egy alacsony útköltségű megoldás-e)? 3. Mi a megoldás megtalálásához szükséges (idő/ tár) keresési költség? A keresés összköltsége: az útköltség + a keresési költség (!) avagy egy racionális ágens számára a probléma megoldásának költsége a probléma megoldásának számítási költsége ÉS a problémamegoldás végrehajtási költsége EGYÜTTESEN

Mi kell? Tárból, időből levenni, de a megoldásra garanciát adni (a menyasszony legyen szép, okos, és gazdag). Felejtsük el! De valamiből mindig le kell adni. Levenni időigényből (időkomplexitásból), levenni tárból, jó lenne levenni mindkettőből = kevesebb átnézett csomópont! Mi is a helyzet a mélységi és a szélességi kereséssel? Garancia és gyorsaság – együtt nem fog menni. Ha garancia nagyon kell, meg kell enni a békát. Garancia nélkül, csak ha jó a tapasztalat, vagy ha nagyon gyors az eszköz, mert ha kudarcba fullad, van még idő megismételni. Szólaltassuk a mérnöki kreativitást!

(1) Büntessük a hátrakeresést. (A*, stb.)

(2) Keressünk mindkét irányból. (kétirányú) (3) Ügyesen alkalmazzuk a mélységi keresést. (iteratív) (4) Alkalmazzuk a gráf előfeldolgozását (problémát alakítsuk át egyszerűbbé, de ennek ára van). (ALT landmarks) (5) Eleve tervezzük be a kicsi memóriát. (EMA*) (6) Teljesen mondjunk le a visszalépésekről. (hegymászás) (7) Engedélyezzük a nem a legjobb lépéseket is. (nyaláb keresés) (8) Engedélyezzünk rossz lépéseket is. (szimulált lehűtés) (9) Tiltsunk egyes potenciálisan rossz lépéseket. (tabú keresés) (10) Folyamatosan profitáljunk az eddigi megoldásokból. (tanuló A*, anytime A*, stb.) (11) Randomizáljuk és ismételjük. (12) Maradjunk keresni az eredeti folytonos térben. ...

Legyen pl. az a probléma, hogy ...

Milyen utat találunk meg? Így?

Milyen utat találunk meg? Vagy úgy?

Formalizált probléma Kezdeti állapot = Arad Célállapot = Bukarest Operátorok: IF (X és (X > Y)) THEN Y Útköltség = k x táv(X,Y) + …

Célállapot teszt: Y = Célállapot? Nehézségek becslése: ? Adatbázis: (Arad > Nagyzerend) táv(Arad,Nagyzerend) = 75 (Arad > Temesvár) táv(Arad,Temesvár) = 118 … ...

Keresési stratégiák – avagy miből gazdálkodhatunk? mire vagyunk képesek? milyen körülöttünk a környezet? Nem informált keresések (un. gyenge, vagy vak keresés) tudjuk: hogy néz ki a célállapot esetleg tudjuk: mibe kerül cselekedni egyáltalán nem: milyen költségű az aktuálisból a célállapotba vezető út (avagy merre van a cél?) Informált keresések = heurisztikus keresések tudjuk: hogy néz ki a célállapot tudjuk: milyen költségű lehet az aktuális állapotból a célállapotba vezető út (avagy merre van a cél) esetleg tudjuk: mibe kerül cselekedni

... útkeresés: Aradból kiindulva 3 cselekvés Szebenbe, Temesvárra és Nagyzerendre vezet nem informált keresés: nincs különbség, merre ... informált, okosabb ágens: Szeben a célállapot irányában fekszik ... A vak keresési stratégiákat a csomópontok kifejtési sorrendje különbözteti meg. Ez a különbség óriási jelentőséggel bírhat.

Mélységi keresés

(Ro-Melysegi-K.pdf)

rohanás előre, egy ág mentén, de a visszalépés lehetőségével

Szélességi keresés

(Ro-SzelessegiK.pdf)

szisztematikus feltárás széles fronton, a visszalépésre nincs szükség (nincs is mihez)

Mélységkorlátozott keresés

(Ro-MelysegKorlatosK.pdf)

az utak maximális mélységére egy vágási korlátot ad. Románia térképe: 20 város. Ha létezik egy megoldás, az maximálisan 19 lépés hosszú lehet! De minden város bármelyik városból legfeljebb 9 lépésben elérhető: az állapottér átmérője = jobb mélységkorlát.

A mélységi levágásnál a keresés visszalép. A megoldást, amennyiben létezik és a mélységkorlátnál sekélyebben fekszik, garantáltan megtaláljuk. De semmi garancia nincs arra, hogy a legrövidebb megoldást találjuk meg. Amennyiben túl kis mélységkorlátot választunk, akkor a mélységkorlátozott keresés még csak teljes sem lesz.

Iteratívan mélyülő keresés

(Ro-IterativMelyulo-K.pdf)

Slate és Atkin (1977): CHESS 4.5 sakkprogram. A legjobb mélységkorlát kiválasztása: - kipróbálni az összest! Először 0, majd 1, 2, stb. - mélységkorláttal végez mélységkorlátozott keresést. Ötvözi a szélességi és mélységi keresés előnyeit: optimális és teljes, de a mélységi keresés kis memória igényével rendelkezik. Tékozló? egy exponenciális keresési fában majdnem az összes csomópont a legmélyebb szinten van, d mélység, b elágazási tényező: szélességi keresés - a kifejtések száma: 1 + b + b2 + ... + bd-2 + bd-1 + bd pl. b =10 és d = 5 esetén ez a szám: 1 + 10 + 100 + ... + 100000 = 111111 az iteratívan mélyülő keresés - a kifejtések száma: (d+1)1 + (d)b + (d -1)b2 + ... + 3bd-2+ 2bd-1 + 1bd b = 10 és d = 5 esetén: 6 + 50 +400 + ... + 100000 = 123456 minél nagyobb a b, annál kisebb a többletmunka (max. b = 2, 200%)

Kétirányú keresés

(Ro-Ketiranyu-K.pdf)

- egyszerre előrefelé a kiinduló állapotból, illetve hátrafelé a cél állapotból - a keresés akkor fejeződik be, ha a két keresés valahol találkozik O(2 x bd/2)=O(bd/2)

b = 10, d = 6: a szélességi keresés = 1111111 csomópont, a kétirányú keresés = 2222 csomópont.

Cél állapotból hátrafelé keresni? Az n csomópont előd csomópontjai azon csomópontok, amelyek követő csomópontja n. Ha az operátorok reverzibilisek, akkor az előd és követő halmazok azonosak. Mi van, ha nagyon sok cél állapot van?

a cél állapotok egy explicit listája a cél állapotok egy leírása (sakk)

Hatékony módszer: egy frissen generált csomópont van-e már a másik fél keresési fájában. El kell tudni dönteni, hogy az egyes félrészekben milyen legyen a keresés. Hogy a keresések találkozzanak, legalább az egyik keresés összes csomópontját memóriában kell tartani = tár O(bd/2). O(bd/2) komplexitás feltételezi, hogy a két hullámfront metszésének megállapítása konstans idő alatt elvégezhető(?)

Egyenletes költségű keresés (Dijkstra) (Ro-EgyenletesKoltsegu-DK.pdf)

szélességi keresés módosítása: a hullámfront g(n) útköltség függvénnyel mért legkisebb költségű csomópontját fejti ki először, nem pedig a legkisebb mélységű csomópontot.

szélességi keresés is egyenletes költségű keresés, amelyben: g(n) = Mélység(n), vagyis a csomópont mélysége. Az egyenletes költségű keresés a legolcsóbb megoldást találja meg, feltéve ha: az út költség egy út bejárása során nem csökkenhet: g(Követő(n))  g(n) minden egyes n csomópontra.

A neminformált keresési stratégiák összehasonlítása b - elágazási tényező, d - a megoldás mélysége, m - a keresési fa maximális mélysége, l - a mélység korlát.

Krit.

SzK

EgyKK

MK

MKK

IMK

KK

Idő igény

bd

bd

bm

bl

bd

bd/2

Tár igény

bd

bd

bm

bl

bd

bd/2

Opt.?

Igen

Igen

Nem

Nem

Igen

Igen

Teljes?

Igen

Igen

Nem

Igen, ha l  d

Igen

Igen

tárkomplexitás =< időkomplexitás

Büntessük a hátrakeresést! De ugyanaz és könnyebb díjazni az előrekeresést a célállapot irányába. Ehhez kell valami elképzelés, hogy a cél: – merrefelé van és, – nagyjából milyen messzire fekszik. Ez az információ az un. heurisztika, heurisztikus függvény h(n), amit: – a probléma minden állapotára tudni kell kiszámítani – kifejezi az előrehaladás becsült költségét – ha pontos, akkor elvben fölöslegessé teszi a keresést (ha nagyon pontatlan, akkor semmit sem segít) Ilyen keresés az un. heurisztikus, másképpen informált keresés.

Legyen a heurisztikus függvény a légvonalban mért távolság (hLMT) Az igényeket teljesíti? Mi mondható a hibájáról?

A célhoz legközelebbinek tűnő csomópont először - a legjobbat-először, avagy a mohó keresés (Ro-MohoK.pdf) Stratégia: a következő lépésben azt a csp-t fejti ki, amelyhez rendelt probléma-állapotot a legközelebbinek ítéli a célállapothoz. A ítélethez kell tehát egy becslő heurisztikus függvény h(n) (1) az n csp-ból egy cél-állapotba vezető legolcsóbb út becsült költsége (2) a célállapotban h(n)= 0, jó célállapottesztnek is (3) lehet hibája (a tényleges költséghez képest) és elvárjuk, hogy minél kisebb hibának minél ügyesebb keresés feleljen meg.

ezt kaptuk ezt kellene kapni

Mohó algoritmus általában gyorsan megtalálja a megoldást, de nem mindig az optimális megoldást találja meg. A mohó keresés érzékeny a hibás kezdő lépésekre is.

Mohó keresés: mélységi keresésre hasonlít, egyetlen út végigkövetését preferálja a célig: de zsákutcából visszalép Ua. a problémák, mint a mélységi keresésnél: nem optimális, nem teljes (elindul egy végtelen úton és nem tér vissza új lehetőséget kipróbálni) (worst-case) időigény: O(bm) Az összes csomópontot a memóriában tartja:

tárigény = időigény

Jó heurisztikus függvénnyel a tár- és időigény jelentősen csökkenthető, a csökkentés az adott problémától és a h függvény minőségétől függ. Tökéletes információ = előretartás elágazások nélkül = lineáris tár = lineáris idő!

Szóval a mohó keresés ígéretes, de mégsem jó.

A teljes útköltség minimalizálása - A* keresés (Ro-AcsillagK.pdf) mohó: min {h(n)} a célhoz vezető útköltség becslőjét minimalizálja nem teljes (nem optimális) egyenletes költségű: min {g(n)} a megtett út költségét minimalizálja optimális (egyben teljes is), de nagyon rossz hatékonyságú a két stratégia ötvözése: min {f(n) = h(n) + g(n)}  g(n): a kiinduló cs-ponttól az n cs-pontig számított út tényleges költsége h(n): az n cs-ponttól a célba vezető legolcsóbb költségű út becsült értéke f(n): a kiinduló csp-tól az adott n csp-on át a célba vezető legolcsóbb költségű út becsült értéke (de facto standard az útkeresésben)

Ha a h függvény soha ne becsüli felül a cél eléréséhez szükséges költséget = elfogadható heurisztika (optimista, a cél közelebbinek tűnik, mint amilyen) Ha h elfogadható, akkor f(n) soha sem becsüli túl az n csomóponton át vezető legjobb megoldás valódi költségét A* keresés: az f függvényt alkalmazó olyan mohó keresés, ahol h elfogadható (olyan Dijkstra-keresés, ahol a csomópontokra cél-felé egy p(n) csökkenő potenciálmezőt értelmeztük, és a figyelembe vett élsúly a redukált élsúlyR(n1,n2) = élsúly(n1,n2) – p(n1) + p(n2) ) Ha a gyökérből nézve egyetlen út f értéke nem csökken – a heurisztika monoton. Egy heurisztikus függvény aka. monoton, ha teljesíti a háromszög egyenlőtlenséget (konzisztens heurisztika, hLMT ilyen). trükk: maximális-út egyenlőség (n-ből n’-be): f(n') = max( f(n), g(n') + h(n') )

ha f a gyökérből kiinduló utak mentén soha sem csökken  határvonalak

Egyenletes költségű (A* keresés h = 0 mellett) a csp-sávok a kiinduló csp köré húzott többé-kevésbé koncentrikus „körök”. Koncentrikusak a szélességi keresés esetében. Egy pontosabb heurisztikus függvény esetén a sávok a cél-állapot felé nyúlnak, rásimulnak az optimális útra.

http://mialmanach.mit.bme.hu/demonstraciok/a_kereses_usa_terkepen_konturkovetessel

Az A* teljes és optimális f(G2) = g(G2 ) > g(G) > f(n) Ha f* az optimális megoldási út költsége, akkor: - A* kifejti az összes f(n) < f* csp-t - ezek után egy cél-csp kiválasztása előtt még kifejthet néhány csp-t a „cél-határvonalon”, amelyekre f(n) = f*

Az ilyen típusú optimális algoritmusok közül az A* keresés bármely adott heurisztikus függvény mellett optimális hatékonyságú. Egyetlen optimális algoritmus sem fejt ki garantáltan kevesebb csomópontot az A* keresés által kifejtett csomópontnál. A* teljessége - pontosan: az A* algoritmus lokálisan véges gráfokon – (véges elágazási tényező) teljes, ha létezik  pozitív konstans, amelynél semelyik operátor költsége sem kisebb. (ki akarjuk kerülni a véges határértékkel rendelkező végtelen számú infinitezimális mennyiségekkel kapcsolatos problémákat, azonban a probléma formalizálása rajtunk múlik, és vessen magára, aki ilyennek formalizálná a problémát)

Az A* algoritmus komplexitása (teljes, optimális és az összes ilyen közül optimálisan hatékony) Buktató: a legtöbb esetben a csp-ok száma a keresési tér cél-határvonalán belül a megoldás hosszának még mindig exponenciális függvénye. Exponenciális - kivéve, ha a heurisztikus függvény hibája legfeljebb az aktuális útköltség logaritmusával nő: h(n) – h*(n)  O(log(h*(n)),

(h*(n) a valódi költség)

Majdnem minden, gyakorlati heurisztikus függvény esetén a hiba legalább arányos az út költséggel - exponenciális növekedés. Egy jól megválasztott heurisztikus függvény ettől függetlenül a nem informált keresési algoritmushoz képest jelentős megtakarítást eredményezhet?! (hogyan?!) A* algoritmus problémája: az összes legenerált csomópontot eltárolja, lényegesen hamarabb felemészti a memóriát, mintsem kifutna az időből.

Heurisztikus függvények létrehozása (legyen sok és jó) 8-as tili-toli: kb. 12 lépés, b ~ 3, kimerítő keresés = 105 állapot Gyorsan a legrövidebb megoldás?

- elfogadható heurisztika kell! h1 = a rossz helyen lévő lapkák száma. elfogadható: minden rossz helyen lévő lapkát legalább egyszer mozgatni kell

h2 = a lapkák céltól mért (vízsz. és függ.) távolságainak összege: háztömb- vagy Manhattan-távolság elfogadható: minden egyes mozgatással egy lapkát csak egy (vízszintes és függőleges) lépéssel lehet közelebb vinni a célhoz. ……… h1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 = 7 Jó lesz pl.: h2 = 2 + 3 + 3 + 2 + 4 + 2 + 0 + 2 = 18 h3 = (h1 + h2)/2 ? h3 = ..... = .... ? stb.

Heurisztikus függvény pontossága és hatékonysága A heurisztikus függvények minősítése: b* effektív elágazási tényező ha A* által kifejtett összes cs-pont száma N, a megoldás mélysége d, akkor b* annak a d mélységű kiegyensúlyozott fának az elágazási tényezője, amely N cs-pontot tartalmaz:

N = 1 + b* + (b*)2 + … + (b*)d (pl. 5 mélységben fekvő megoldás 52 cs-pont kifejtésével: az effektív elágazási tényező 1.91) 52 < 63 = 1 + 2 + 22 + 23 + 24 + 25 Egy adott heurisztikus függvény által generált fa effektív elágazási tényezője általában nagyjából állandó egy adott problémaosztály számos egyedére. A b* kis számú probléma halmazon végzett kísérleti mérése jó becslés. Egy jól megtervezett heurisztikus függvény effektív elágazási tényezője 1 körüli érték (de 1-nél nagyobb!).

h1 és h2 tesztelése: 100 random probléma példány, 2, 4, …, 24 mélységű megoldással, A*, illetve a neminformált iteratívan mélyülő keresés

Heurisztikus függvény: pontosság és hatékonyság h1, h2 heurisztikus függvények tesztelése: vajon a h2 mindig jobb-e, mint a h1? Igen (miért?). minden n csp-ra h2 (n)  h1 (n): h2 dominálja h1–et, domináció = hatékonyság h2-t használó A* kevesebb csp-t fog kifejteni, mint h1–et használó Mindig jobb nagyobb értékeket adó elfogadható(!) heurisztikus függvényeket alkalmazni.

Tényleges Elfogadható, kis hiba Elfogadható, közepes hiba Elfogadható, durva hiba Elfogadható, nagyon durva hiba

(Jó) Heurisztikus függvények kitalálása Egy lapka az A-ról a B-re mozgatható, ha A és B szomszédok és a B mező üres. Egy vagy több feltétel törlésével un. relaxált problémákat hozhatunk létre (a) Egy lapka az A-ról a B-re mozgatható, ha A és B szomszédosak.

(h2)

(b) Egy lapka az A-ról a B-re mozgatható, ha a B mező üres. (c) Egy lapka az A-ról a B-re mozgatható.

(h1) (a) 6 + 3 = 9 lépés (c) 1 + 1 = 2 lépés

15 1 2 3 4 5 6 7 8 9 10 11 13 14 12

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

(Jó) Heurisztikus függvények kitalálása

Relaxált probléma: olyan probléma, amelyben az operátorokra kevesebb megkötést teszünk, mint az eredeti problémában.

Gyakori, hogy a relaxált probléma pontos megoldásának költsége jó heurisztikus függvény az eredeti problémára. Gyakori, hogy a relaxált probléma egyszerűsége miatt, az optimális megoldás analitikusan is meghatározható. A relaxált probléma pontos megoldása mindig egy elfogadható heurisztika a kevésbé relaxált problémára.

(Jó) Heurisztikus függvények kitalálása 14 7 3

h3: (Disjoint) Pattern Database Heuristics 15

h4: Linear Conflict Heuristics

12 11

h5: Gaschnig’s Heuristics

13

7 13 12

Piros lapkák megoldása = 20 lépés Kék lapkák megoldása = 25 lépés

15 11

3 14

3 7 11 12 13 14 15

3 7 11 12 13 14 15

Telljes heurisztika: h3 = 20+25=45 lépés

5 10 14 7 8 3 6 1 15 12 9 2 11 4 13

1 4 5 8 9 12 13

2 6 10 14

3 7 11 15

h1 = 14 h2 = 39 h3 = 45 h2 a h3 egy speciális esete, ha minden pattern egy lapka!

(Jó) Heurisztikus függvények kitalálása h3: (Disjoint) Pattern Database Heuristics h4: Linear Conflict Heuristics h5: Gaschnig’s Heuristics

3

1

1

3

h2 = 2 + 2 = 4 de a lapkák egymással szemben nem tolhatók h4 = h2 + 2 (kikerülés)

h4 = h2 + 2 x (sorbeli lineáris konfliktus, minden sorra + oszlopbeli lineáris konfliktus, minden oszlopra)

(Jó) Heurisztikus függvények kitalálása h3: (Disjoint) Pattern Database Heuristics h4: Linear Conflict Heuristics h5: Gaschnig’s Heuristics

(b) Egy lapka az A-ról a B-re mozgatható, ha a B mező üres. elfogadható, jó becslés

(Jó) Heurisztikus függvények kitalálása Ha egy problémához adottak a h1,...,hm elfogadható heurisztikák és semelyik sem dominálja a másikat, melyiket kellene választanunk? Nem kell választanunk. A lehető legjobb:

h(n) = max{ h1(n),...,hm(n) } mindig azt a függvényt használja, amelyik az adott csomópontra a legpontosabb, elemek mind elfogadhatóak, ezért h is elfogadható, h dominálja az összes heurisztikus függvényt. Probléma: az elemezhetőség, hiszen konkrét h mindig változik?

Heurisztikus függvények megalkotása: - ha a heurisztikus függvény olyan összetett, hogy értékének egy csp-ra történő meghatározása sok időt vesz igénybe, akkor baj van.

Egy jó heurisztikus függvény: pontos és hatékonyan számítható

Memória korlátozott keresés általában az első korlát, amibe beleütközünk, a rendelkezett memória. IMA*: az Iteratívan-Mélyülő-Keresés heurisztikus kiterjesztése. RLEK: Rekurzív Legjobban Először Keresés EMA*: Egyszerűsített véges memóriájú A* mint az A*, de korlátozza a sor méretét, hogy az beférjen a memóriába. stb.

Iteratívan Mélyülő A* keresés (IMA*) Minden iteráció egy mélységi keresés, mélységkorlát helyett egy f-költség korláttal. Minden iteráció kifejti az összes - az adott f-költség határvonalon belül fekvő - csomópontot, átnézve a határvonalon, hogy megtalálja, hol fekszik a következő határvonal. Az IMA* uu. teljes és optimális, mint az A*, de a mélységi keresés jellege miatt csak a leghosszabb felderített út hosszával arányos memóriát igényel. Az IMA* algoritmus időigénye erősen függ attól, hogy a heurisztikus függvény hány különböző értéket vehet fel. Az utolsó iterációja kb. ua. csomópontot fejt ki, mint az A* (időkomplexitás!). Összetettebb problémán nehezebben boldogul (ha sok iteráció kell).

Rekurzív Legjobb Először Keresés

(Ro-RLEK.pdf)

Addig halad Legjobbat Először módon f érték szerint, amíg jobb alternatívára nem lel hátrahagyott elágazásban. Átkapcsol, felszabadít memóriát, de a pillanatnyilag követett út költségét memorizálja.

Rekurzív Legjobb Először Keresés

(Ro-RLEK.pdf)

Addig halad Legjobbat Először módon f érték szerint, amíg jobb alternatívára nem lel hátrahagyott elágazásban. Átkapcsol, felszabadít memóriát, de a pillanatnyilag követett út költségét memorizálja.

Rekurzív Legjobb Először Keresés

(Ro-RLEK.pdf)

Addig halad Legjobbat Először módon f érték szerint, amíg jobb alternatívára nem lel hátrahagyott elágazásban. Átkapcsol, felszabadít memóriát, de a pillanatnyilag követett út költségét memorizálja.

Rúgó tervezése kereséssel

Alak Átmérő Menetszám Anyag Befogás stb.

Hőmérséklet-tartomány Húzószilárdság Ellenállás/ ütközés Megengedett munkastressz Rugalmassági modulus Élettartam Tűrési határok „Végtelen sokszor” alkalmazható stressz Keménység Elektromos vezetés Mágneses tulajdonságok Korrózióvédettség Költség stb. max/ min/ konkrét ...

paraméterek célok

Lokálisan kereső algoritmusok Állapotok jósága: egy hiperfelület az állapotok N-dim paraméterterében. A felület magassága = az adott állapot optimalitása. A felületen a legmagasabb (legalacsonyabb) csúcsot keressük, ami egyben az optimális megoldásnak felel meg. A csúcs helyén a kívánt paramétertekék = a probléma megoldása. Általában csak az aktuális állapot tárolt, és csak a közvetlen környezetében nézünk előre. Tipikus probléma: optimalizálás, optimalizáló tervezés. A keresési tér különleges ... Visszalépés nincs, amiatt a memóriaigény kicsi, fix. Az időigény lineáris. Garancia megoldásra? (teljesség?, optimalitás?) hegymászó (diszkrét gradiens): mindig amerre javít az aktuális állapoton szimulált lehűtés: néha megenged rossz lépéseket is lokális nyaláb keresés: mindig k csomópontot tart számon véletlen indítású … … genetikus algoritmusok:mint a lokális nyaláb, speciális (genetikus) lépésoperátorokkal … ...

Hegymászó keresés

(Ro-HegyMaszo-K.pdf)

- ciklikusan lép fel mindig a javuló értékek felé - nem tart nyilván keresési fát - ha egynél több legjobb követő csomópont merül fel, véletlenszerűen bármelyiket kiválaszthatja. 3 fő probléma: lokális maximum: ha egy lokális maximumba ér, akkor ott megáll fennsík: ott a kiértékelő függvény lapos, véletlen irányválasztás hegygerinc: egy hegygerinc oldalai meredekek, a keresés könnyen eljut a gerincre, de előfordulhat, hogy a gerinc maga csak finoman emelkedik a csúcs felé (Sok lépés „kifárasztja” a rendszert).

Lokális szélsőérték f′(x) = 0

Ha több, melyik a globális?

Véletlen újraindítású hegymászás (és sok más változat): véletlenül generált kiinduló állapotokból hegymászó keresés, amíg nem jár le az idő, vagy már nincs észrevehető előrelépés a hegymászás sikere: az állapottér „felszínének” alakja

- ha csak néhány lokális maximum: gyors megoldás. - egy valódi probléma = egy „sündisznó” felszín. Ha a probléma NP-teljes, akkor az exponenciális időigénynél jobb nem lesz = exponenciálisan sok lokális maximum. Általában kisszámú iteráció után már elfogadhatóan jó megoldást lehet találni.

A dimenzió átka

Szimulált lehűtés Véletlen újraindítás helyett, ha a keresés egy lokális maximumban beragad, megengedhetjük, hogy néhány lefelé vezető lépést tegyen, hogy kimeneküljön a lokális maximumból. A szimulált lehűtés ciklusa: - a legjobb lépés megtétele helyett egy véletlen lépést tesz. - ha a lépés javít, akkor az mindig végrehajtásra kerül. - ellenkező esetben az algoritmus a lépést csak valamilyen, 1-nél kisebb valószínűséggel teszi meg (Boltzmann-eloszlás). P  exp(- E / T) A valószínűség exponenciálisan csökken a lépés "rontó" képességével – azzal a E mennyiséggel, amivel a kiértékelő függvény romlott, és az idővel, a hűtés függvényében.

Szimulált lehűtés T(idő) - hűtési karakterisztika - magas T-nél a "rossz" lépések nagy valószínűséggel fordulnak elő, - ahogy T tart nullához, a rossz lépések egyre kevésbé valószínűek, az algoritmus többé-kevésbé egy hegymászó algoritmusként viselkedik. Hűtési karakterisztika - a hőmérséklet csökkentésének mértéke

Az egyedi lépések - termikus zaj okozta véletlen fluktuáció. Ha a hőmérsékletet kellően lassan csökkentjük, akkor az anyag a legkisebb energiájú állapotba jut. Ha a hűtési karakterisztika T-t kellően lassan csökkentjük, az algoritmus egy globális minimumot fog találni.

http://en.wikipedia.org/wiki/Simulated_annealing

Nyaláb-keresés Lokális nyaláb keresés - k állapotot követ nyomon Indulás: k véletlen módon generált állapot Minden lépésben a k állapot mindegyikének összes követőit kifejti Ha ezek valamelyike egy cél, az algoritmus leáll Különben a teljes listából kiválasztja a legjobb k követőt, és ezt az eljárást ismétli. Megnövelt tár - … - megnövelt esély a „jó” extrémumra.

Genetikus algoritmusok Indulás: k véletlen módon generált állapot = populáció Minden állapot vagy egyed = egy véges ábécé fölött értelmezett, leggyakrabban egy, a 0-kból és 1-ekből álló füzér (a probléma kódolása) - populáció - fitnesz-függvény - keresztezés (kiválasztás, párosítás) fitnesz függvényében - mutáció - elitizmus - Darwin-/ Lamarck-féle öröklődés - új populáció kialakítása

Mint a hegymászó, ill. a nyaláb-keresés (ivartalan/ ivaros szaporodás)

Genetikus algoritmusok A 8-királynő probléma állapotai =

pl. 8 számjegyes füzérek (1.oszlop poz., 2. oszlop poz., …, 8. oszlop poz.) fitnesz = 28 - n

darwini, lamarcki?

2006 NASA ST5 spacecraft antenna https://en.wikipedia.org/wiki/Evolved_antenna

És még sok-sok egyéb keresési algoritmus ... a. Minden keresési algoritmusnak számos változata van b. Új algoritmusok kitalálása az MI mindig aktív területe c. Folytonos terekben a kereséshez gradiens alapú eljárások szolgálnak x  x -  f(x) x  x -  H-1(x) f(x) relaxációs módszer gradiens fix lépéshosszal gradiens optimalizált lépéshosszal Newton-módszer és sok más

d. (Alagutas hegymászás (minimization + tunnelling) ...) e. Hiányos információ mellett (felfedezési problémák) az un. on-line változatok használatosak (pl. tanuló valós-idejű A*, ld. jegyzet)

Kis HF8 Válasszon egy kb. 20 lépésből álló sakkjátszma leírását. A játszma minden állásában mérje fel az akkor a lépésnél lévő játékos részére rendelkezésre álló legális lépések számát (indulásnál a fehérnek 20 legális lépése van). Számítsa ki e legális lépések középértékét és egy egészre kerekítse le. Keresse ki, hogy 2016-ban milyenek a kurrens legjobb szuper szg. tár és sebesség adatai (wiki). Vegye fel az állás eltárolására és a lépés kiszámítására alkalmas (fiktív) tár és idő adatot. Képzelje el, hogy e gép használatával fel kell építenie és eltárolnia a kikeresett sakkjátszmához tartozó keresési fát (amelynek mélysége és elágazási tényezője adott). Számítsa ki, hogy tárban és időben mérve hogyan néz ki a fa növekedése a játszma lépésszám függvényével (azaz a mélység növekedésével)! (minden színten a kapott átlagos elágazási tényezővel számoljon!) (értelmes közelítésekkel éljen!)