Intelligens Rendszerek I. Problémamegoldás kereséssel: informált kereső eljárások (Heurisztikus keresés)

Intelligens Rendszerek I. Problémamegoldás kereséssel: informált kereső eljárások (Heurisztikus keresés) 2007/2008. tanév, I. félév Dr. Kovács Szilveszter E-mail: [email protected] Miskolci Egyetem Informatikai Intézet 106. sz. szoba Tel: (46) 565-111 / 21-06 mellék

Célorientált ágens - Problémamegoldó ágens • A célorientált ágens egy típusa (problem solving agent) • A probléma: – A cél és azon eszközök halmaza, amelyekkel a célt elérjük • A probléma megoldása: – Keresés: Olyan cselekvéssorozatokat keresnek, melyek a kívánt (cél) állapotba vezetnek. • Végrehajtási fázis (execution): – a talált cselekvéssorozat végrehajtása. Dr. Kovács Szilveszter ©

M.I. 5. / 2.

Problémamegoldás kereséssel Keresés (search): • Több különböző lehetséges cselekvéssorozat közül, melyek ismert értékű állapotba vezetnek, a lehető legjobb kiválasztása. • A keresési algoritmus bemenete egy probléma, a kimenete pedig cselekvéssorozat: megoldás. probléma

keresési algoritmus Dr. Kovács Szilveszter ©

megoldás M.I. 5. / 3.

Problémamegoldás kereséssel Célmegfogalmazás (goal formulation): • A cél a világ állapotainak olyan halmaza, amelyben a cél teljesül. Cselekvések (action): • Tevékenységek, melyek hatására a világ állapotai között állapotátmenetek mennek végbe. Problémamegfogalmazás (problem formulation): • A cél megfogalmazását követően meghatározzuk, hogy mely cselekvéseket és állapotokat vegyük figyelembe (absztrakció) • Gond: az ágens nem biztos, hogy ismeri állapotait és cselekvései eredményeit Dr. Kovács Szilveszter ©

M.I. 5. / 4.

Problématípusok

Az ágens és a környezetének kapcsolata alapján: • Egyállapotú (single-state) (hozzáférhető környezet) • Többállapotú (multiple-state) – Ismeri a cselekvéseinek hatását, de csak korlátozottan fér hozzá a világ állapotához

• Eshetőségi (contingency) – Ha a környezet nem determinisztikus

• Felderítési (exploration) – Ha nincs semmilyen információja cselekvései hatásáról és a létező állapotokról – „kísérleteznie” kell: a valós világban, nem pedig a modellben keres Dr. Kovács Szilveszter ©

M.I. 5. / 5.

Probléma megfogalmazás formálisan (egyállapotú probléma esetén) • A kiinduló állapot (initial state) meghatározása (ebből indul) • A lehetséges cselekvések halmazának meghatározása Operátorok: egy adott állapotból egy cselekvés hatására az ágens mely állapotba kerül S(x) következő állapotfüggvény: egy adott x állapot esetén az egyetlen cselekvés végrehajtásával elérhető állapotok halmaza • Állapottér: azon állapotok halmaza, amely a kiinduló állapotból valamilyen cselekvéssorozattal elérhetők • Az állapottér egy útja: egy állapotból a másikba vezető cselekvéssorozat Dr. Kovács Szilveszter ©

M.I. 5. / 6.

Probléma megfogalmazás formálisan (egyállapotú probléma esetén) • Célteszt: amely alapján egy állapotról az ágens el tudja dönteni, hogy az célállapot-e – egyszerű eset: a jelenlegi állapot eleme-e a célállapotok halmazának? – bonyolult eset: a cél egy absztrakt tulajdonság pl. „sakk – matt”

• Útköltség: függvény, amely egy úthoz hozzárendel egy költséget – Pl. az utat alkotó cselekvések költségeinek összege

• Megoldás: a kiinduló állapotból egy olyan állapotba vezető út, ami teljesíti a céltesztet

Dr. Kovács Szilveszter ©

M.I. 5. / 7.

Pl: Utazás Aradról Bukarestbe Pl: ágensünk nyer egy kéthetes all-inclusive nyaralást a romániai Bukarestben, az egyetlen feltétel az, hogy másnap délre odaérjen, de este 10 előtt nem tud elindulni, és ágensünk kell vezesse az autót. • Kiindulási állapot: Aradról indul • Cél: Bukarestbe eljutni • Minden olyan cselekvést, ami nem ezt eredményezi el kell dobni


M.I. 5. / 8.

Utazási példa: Románia – a probléma megfogalmazása • • • • • •

kiinduló állapot: Arad célteszt: ez a város Bukarest? állapottér: a városok (állapot: város ahol vagyok) operátorok: városok közötti utakon történő vezetés útköltség függvény: városok távolsága km-ben megoldás: egy útvonal Aradról Bukarestbe


M.I. 5. / 9.

Utazási példa: Románia - állapottér


M.I. 5. / 10.

Állapottér – Keresési fa Az egyes állapotok a keresési fa csomópontjai

• Fa, melynek csúcsa a kiinduló állapot, valamelyik levele a célállapot, ha létezik megoldás • Állapot kifejtése: valamely állapotból egyetlen lépéssel elérhető állapotok meghatározása. • Perem (fringe), vagy hullámfront (frontier): a kifejtésre váró csomópontok (állapotok) halmaza • A keresési módszer nem más mint a kifejtésre váró csomópontok kifejtési sorrendjének meghatározása Dr. Kovács Szilveszter ©

M.I. 5. / 11.

A keresés é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 (Time complexity) • Tárigény: mennyi memóriára van szükség a megoldás megkereséséhez (Space complexity)


M.I. 5. / 12.

Nem informált keresési módszerek • A nem informált keresési módszerek csak a probléma definícióban megfogalmazott információra támaszkodhatnak. • Az egyes keresési módszerek csak a kifejtésre váró csomópontok kifejtési sorrendjében térnek el egymástól: – – – – – –

Szélességi, (Breadth-first search) egyenletes költségű, (Uniform-cost search) mélységi, (Depth-first search) mélységkorlátozott, (Depth-limited search) iteratívan mélyülő, (Iterative deepening search) kétirányú keresés (Bidirectional search). Dr. Kovács Szilveszter ©

M.I. 5. / 13.

A szélességi keresés tulajdonságai • Mindig a legsekélyebben fekvő (legkevesebb lépéssel elérhető) megoldást találja meg • Teljesség? Igen (ha b véges) • Időigény? 1+b+b2+b3+… +bd = O(bd) (minden csomópontból b darab irányba mehetünk tovább (elágazási tényező) és a célig d lépést kell megtenni) • Tárigény? O(bd) (Minden csomópontot a memóriában tart) • Optimalitás? Igen Feltéve, hogy az útiköltség a csomópontszám költségnek nem csökkenő függvénye (mélyebben csak drágábbak lehetnek) (e.g. if cost = 1 per step) • A tárigény a nagyobb probléma (mint az időigény) Dr. Kovács Szilveszter ©

M.I. 5. / 14.

Az egyenletes költségű keresés tulajdonságai • A hullámfront legkisebb költségű – ahova a legolcsóbban lehet eljutni - csomópontját fejti ki először • Azonos a szélességi kereséssel, a lépésköltségek mind azonosak • Teljesség? Igen, ha a lépésköltség ≥ ε • Időigény? # of nodes with g ≤ cost of optimal solution, O(b(C*/ ε)) ahol C* az optimális megoldás útiköltsége • Tárigény? # of nodes with g ≤ cost of optimal solution, O(b(C*/ ε)) • Optimalitás? Igen – ha az útköltség g(n) egy út bejárása során soha sem csökkenhet Dr. Kovács Szilveszter ©

M.I. 5. / 15.

Mélységi keresés • Mindig a keresési fa legmélyebben fekvő csomópontjainak egyikét fejti ki • A keresés csak akkor lép vissza és fejt ki magasabb szinten lévő csomópontokat, ha zsákutcába fut • Az első találatig megy (az útköltséget nem veszi figyelembe a döntéseknél)


M.I. 5. / 16.

Mélységi keresés tulajdonságai • Teljesség? Nem: fails in infinite-depth spaces, spaces with loops – Modify to avoid repeated states along path Æ complete in finite spaces

a keresési fa mélysége a megoldás mélysége

• Időigény? O(bm): terrible if m is much larger than d – but if solutions are dense, may be much faster than breadthfirst

• Tárigény? O(bm), azaz, lineáris a hely komplexitás! m a fa maximális mélysége és csak a levélcsomópontig vezető utat és az útközben kifejtetlen csomópontokat kell eltárolni. • Optimalitás? Nem • Ha vannak végtelen mély ágak, akkor nem teljes és nem optimális. Dr. Kovács Szilveszter ©

M.I. 5. / 17.

Mélységkorlátozott keresés tulajdonságai • Mélységi keresés, de egy adott mélységnél l nem mehetünk tovább a keresési fában • Megoldódik a „végtelen mélységű út” probléma. • Teljesség? Nem teljes ha l < d (Csak akkor lenne teljes, ha előre tudnánk a megoldás maximális mélységét) • Optimalitás? Nem optimális pl. ha l > d (lehet, hogy mélyebben talál egy megoldást) • Idő? Időigény bl-el arányos: O(bl) • Hely? Tárigény b*l-el arányos: O(bl) • Ahol l a mélységi korlát Dr. Kovács Szilveszter ©

M.I. 5. / 18.

Az iteratívan mélyülő keresés tulajdonságai • A legjobb mélységkorlát iteratív meghatározása • Az összes lehetséges mélységkorlát kipróbálása • Exponenciális keresési fa esetén viszonylag kis többletmunka • Teljesség? Igen • Időigény? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd) • Tárigény? O(bd) • Optimalitás? Igen, feltéve, hogy az útiköltség a csomópont költségnek nem csökkenő függvénye (a mélyebben lévők csak drágábbak lehetnek) (e.g. if cost = 1 per step) Dr. Kovács Szilveszter ©

M.I. 5. / 19.

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


M.I. 5. / 20.

Kétirányú keresés

• • • • • •

Keresés indítása egyszerre a kiinduló állapotból és a célállapotból Leállás: a két keresés találkozásánál Motivation: b d / 2 + b d / 2 ≠ b d Space complexity is the most significant weakness. Teljes és optimális, ha mindekét keresés szélességi keresés. The predecessor of each node should be efficiently computable. – When actions are easily reversible Dr. Kovács Szilveszter ©

M.I. 5. / 21.

Nem informált keresési módszerek - összefoglaló Criterion

BreadthFirst

Uniformcost

DepthFirst

Depthlimited

Iterative Bidirectio deepening nal search

Complete ?

YES*

YES*

NO

YES

YES*

Time

bd

bC*/e

bm

YES, if l ≥ d bl

bd

bd/2

Space

bd

bC*/e

bm

bl

bd

bd/2

Optimal?

YES*

YES*

NO

NO

YES

YES

• Gond az alacsony hatékonyság • A nem informált keresési módszerek csak a probléma definícióban megfogalmazott információra támaszkodhatnak – nem sejti, hogy a cél merre lehet Dr. Kovács Szilveszter ©

M.I. 5. / 22.

Informált keresési eljárások • Informált = probléma specifikus információ (tudás) alkalmazása • Azt a csomópontot bontjuk ki először a front állapotai közül, amelyikre vonatkozóan a kiegészítő információk valamilyen előnyt ígérnek – amelyik pl. a legjobbnak tűnik az adott pillanatban • Ezen módszereket heurisztikus keresésnek is nevezzük, mert a problématerületre vonatkozó tapasztalatra épít (ált. növeli a hatékonyságot, de tévedhet is) (görög heuriskein: megtalál, felfedez) Dr. Kovács Szilveszter ©

M.I. 5. / 23.

Informált keresési eljárások A heurisztika lehet: • Globális információ: az állapottér bármely két pontja között származtatható, leggyakrabban az n. állapot és a célállapot között számítjuk és az n. állapothoz rendeljük h(n). (pl. egy pont becsült távolsága a céltól) Globális információ felhasználásával megtalálhatjuk a globális optimumot, az optimális költségű utat is. • Lokális információ: egy állapot és közvetlen szomszédai között számítható (pl. becsült távolságok a szomszédokig) Önmagában lokális információ alkalmazásával csak lokális extrémumot garantálnak az eljárások, gyakran azonban annak közelítésével is megelégszünk. Dr. Kovács Szilveszter ©

M.I. 5. / 24.

Informált keresési eljárások • Globális információra támaszkodó eljárások: Legjobbat először keresés (Best first search) : – mohó keresés (Greedy search) – A* – Iteratívan mélyülő A* (Iterative-deepening A*) – Rekurzív legjobbat először keresés (Recursive bestfirst) – Egyszerűsített memóriakorlátozott A* (Simplified Memory-bounded A*)

• Lokális információra támaszkodó optimálási módszerek: – – – – –

hegymászó keresés (Hill climbing search), szimulált lehűtés (Simulated annealing), Local beam search Genetikus algoritmusok (Genetic algorithms) ... Dr. Kovács Szilveszter © M.I. 5. / 25.

A legjobbat először keresés (Best first search) • A legjobbat először keresés egy kiértékelő függvénnyel (evaluation function: f(n)) becsli az n. állapot kifejtésének a szükségességét a front összes állapotára és abba az állapotba lép, amelyikre ez az érték a legjobb (best first). • Az eljárás végződhet lokális optimum pontban is. • Valójában ez egy a „Legjobbnak tűnőt először keresés” - becsült (nem tényleges!) fontossága egy adott állapot kifejtésének. • (Ha ismert lenne a kifejtések tényleges fontossága, nem kellene keresni, mindig az optimális irányt választhatná.) Dr. Kovács Szilveszter ©

M.I. 5. / 26.

Heurisztikus függvény h(n) • h(n) = az n. állapotból a cél elérésének becsült költsége. • h(n)=0, ha n célállapot. • Heurisztikus függvény: becsült költség (nem tényleges!) egy adott pont és a cél között. (Ha ismert lenne a tényleges költség, nem kellene keresni, mindig az optimális irányt választhatná) • Pl. Az utazási probléma esetén (ahol az útköltség függvény a városok távolsága km-ben), lehet valamely város légvonalban mért távolsága a céltól.


M.I. 5. / 27.

Mohó keresés (Greedy search) • A legjobbat először keresés egy implementációja, ahol f(n)= h(n) • A heurisztikus függvénnyel becsli a kiértékelő függvényt • Mindig annak az állapotnak a kifejtését végzi a fronton, amelynek a céltól való becsült költsége a legalacsonyabb (annak tűnik). • Pl. Az utazási probléma esetén, melynek a céltól mért távolsága légvonalban a legkisebb. Dr. Kovács Szilveszter ©

M.I. 5. / 28.

Romania with step costs in km • hSLD=straight-line distance heuristic. (légvonalban mért távolság) • hSLD NEM számítható ki magából a problémából • Ebben a példában f(n)=h(n) – Mindig azt az állapotot fejtjük ki, amelyik a célhoz a legközelebb van = Greedy best-first search


M.I. 5. / 29.

Romania with step costs in km

0


M.I. 5. / 30.

Greedy search example

Arad (f(n)=h(n)=366)

• Assume that we want to use greedy search to solve the problem of traveling from Arad to Bucharest. • The initial state=Arad Dr. Kovács Szilveszter ©

M.I. 5. / 31.

Greedy search example Arad Zerind(374)

Sibiu(253) Timisoara (329)

• The first expansion step produces: – Sibiu, Timisoara and Zerind

• Greedy best-first will select Sibiu.


M.I. 5. / 32.

Greedy search example Arad Sibiu

Arad (366)

Fagaras (176)

Oradea (380)

Rimnicu Vilcea (193)

• If Sibiu is expanded we get: – Arad, Fagaras, Oradea and Rimnicu Vilcea

• Greedy best-first search will select: Fagaras Dr. Kovács Szilveszter ©

M.I. 5. / 33.

Greedy search example Arad Sibiu

Fagaras Sibiu (253)

Bucharest (0)

• If Fagaras is expanded we get: – Sibiu and Bucharest

• Elérte a célt !! – De nem optimális!

(lásd Arad, Sibiu, Rimnicu Vilcea, Pitesti) Dr. Kovács Szilveszter ©

M.I. 5. / 34.

Greedy search, tulajdonságok • Teljesség: nem teljesül – Pl. állapotok végtelenül ismétlődhetnek – Minimizing h(n) can result in false starts, e.g. Iasi to Fagaras.

Ez távolabb vinne


M.I. 5. / 35.

Greedy search, tulajdonságok • Teljesség: nem teljesül (mint a mélységi keresés) • Idő komplexitás? O(b m ) – Legrosszabb esetben olyan mint a mélységi keresés (with m is maximum depth of search space) – Good heuristic can give dramatic improvement.


M.I. 5. / 36.

Greedy search, tulajdonságok • Teljesség: nem teljesül (mint a mélységi keresés) • Idő komplexitás: O(b m ) • Hely komplexitás: O(b m ) – Valamennyi csomópontot a memóriában tartja

• Nem optimális


M.I. 5. / 37.

A* search • Alapötlet: Ne fejtsük ki azokat a csomópontokat, amikhez az odavezető út már eddig is drága. • Kiértékelő függvény: f(n) = g(n) + h(n) • g(n) = eddigi útiköltség n -ig • h(n) = heurisztikus fv. becsült költség n-ből a célig • f(n) = az n-en keresztül vezető út teljes becsült költsége


M.I. 5. / 38.

Romania with step costs in km

0


M.I. 5. / 39.

A* search example

• Find Bucharest starting at Arad – f(Arad) = g(Arad,Arad)+h(Arad)=0+366=366


M.I. 5. / 40.

A* search example

• Expand Arrad and determine f(n) for each node – f(Sibiu)=g(Arad,Sibiu)+h(Sibiu)=140+253=393 – f(Timisoara)=g(Arad,Timisoara)+h(Timisoara)=118+329=447 – f(Zerind)=g(Arad,Zerind)+h(Zerind)=75+374=449

• Best choice is Sibiu Dr. Kovács Szilveszter ©

M.I. 5. / 41.

A* search example

• Expand Sibiu and determine f(n) for each node – – – –

f(Arad)=g(Sibiu,Arad)+h(Arad)=280+366=646 f(Fagaras)=g(Sibiu,Fagaras)+h(Fagaras)=239+179=415 f(Oradea)=g(Sibiu,Oradea)+h(Oradea)=291+380=671 f(Rimnicu Vilcea)=g(Sibiu,Rimnicu Vilcea)+ h(Rimnicu Vilcea)=220+192=413

• Best choice is Rimnicu Vilcea


M.I. 5. / 42.

A* search example

• Expand Rimnicu Vilcea and determine f(n) for each node – f(Craiova)=g(Rimnicu Vilcea, Craiova)+h(Craiova) =360+160=526 – f(Pitesti)=g(Rimnicu Vilcea, Pitesti)+h(Pitesti)=317+100=417 – f(Sibiu)=g(Rimnicu Vilcea,Sibiu)+h(Sibiu)=300+253=553

• Best choice is Fagaras Dr. Kovács Szilveszter ©

M.I. 5. / 43.

A* search example

• Expand Fagaras and determine f(n) for each node – f(Sibiu)=g(Fagaras, Sibiu)+h(Sibiu)=338+253=591 – f(Bucharest)=g(Fagaras,Bucharest)+h(Bucharest)=450+0=450

• Best choice is Pitesti !!! Dr. Kovács Szilveszter ©

M.I. 5. / 44.

A* search example

• Expand Pitesti and determine f(n) for each node – f(Bucharest)=g(Pitesti,Bucharest)+h(Bucharest)=418+0=418

• Best choice is Bucharest !!! – Optimal solution (only if h(n) is admissable)

• Note values along optimal path !! Dr. Kovács Szilveszter ©

M.I. 5. / 45.

Elfogadható heurisztika (admissible heuristics) • Egy heurisztika elfogadható, ha a becslés nem ad a valósnál nagyobb értéket („optimista”). • Egy h(n) heurisztika elfogadható ha valamennyi n állapotra h(n) ≤ h*(n), ahol h*(n) a tényleges útikültség az n. Állapot és a cél között. • Egy elfogadható heurisztika sohasem becsli túl a cél elérésének valódi költségét, azaz optimista • Example: hSLD(n) (a légvonalban mért távolság sohasem becsüli túl a valóságos távolságot) • Theorem: Ha h(n) elfogadható heurisztika, akkor az A* keresés optimális.


M.I. 5. / 46.

Optimality of A* (bizonyítás) • Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G. • f(n) = g(n) + h(n)

• • • •

f(G2) = g(G2) g(G2) > g(G) f(G) = g(G) f(G2) > f(G)

since h(G2) = 0 since G2 is suboptimal since h(G) = 0 from above Dr. Kovács Szilveszter ©

M.I. 5. / 47.

Optimality of A* (bizonyítás) • Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G. • f(n) = g(n) + h(n)

• • • •

from above f(G2) > f(G) h(n) ≤ h*(n) since h is admissible (h* a tényleges) f(n) = g(n) + h(n) ≤ g(n) + h*(n) = f(G) f(n) ≤ f(G) → → f(n) < f(G2) ez pedig lehetetlen, mert A* így sohasem választaná G2–t kifejtésre n előtt Dr. Kovács Szilveszter ©

M.I. 5. / 48.

Optimality of A* • A* expands nodes in order of increasing f value • Gradually adds "f-contours" of nodes • Contour i has all nodes with f=fi, where fi < fi+1


M.I. 5. / 49.

Az A* keresés tulajdonságai • Teljesség? Igen (hacsak nincs végtelen sok állapot ahol f ≤ f(G) ) • Időigény? Exponenciális • Tárigény? Valamennyi csomópontot a memóriában tartja – Gond: nagy a tárigény

• Optimális? Igen – – – –

Nem fejti ki fi+1 amíg fi –et be nem fejezte. A* kifejti valamennyi csomópontot ahol f(n)< C* A* kifejt néhány csomópontot ahol f(n)=C* A* egyetlen csomópontot sem fejt ki ahol f(n)>C* Dr. Kovács Szilveszter ©

M.I. 5. / 50.

Elfogadható heurisztika E.g., for the 8-puzzle: • h1(n) = number of misplaced tiles • h2(n) = total Manhattan distance (i.e., no. of squares from desired location of each tile)

• h1(S) = 8 • h2(S) = 3+1+2+2+2+3+3+2 = 18 Dr. Kovács Szilveszter ©

M.I. 5. / 51.

Heurisztikus függvények dominanciája • Ha h2(n) ≥ h1(n) valamennyi n-re (ahol mindkettő elfogadható) • akkor h2 dominálja h1 -t • h2 jobb a keresésre • Minél nagyobb, annál jobb a heurisztika (a h(n)=0 mindig elfogadható) • Tipikus keresési költségek (átlagos kifejtendő csomópont számok): d=12 A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes


M.I. 5. / 52.

Heurisztikus függvény probléma relaxációval • 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 (relaxed problem) nevezzük. • A relaxált probléma optimális megoldásának költsége csak kisebb lehet (nem lehet nagyobb) mint az eredeti probléma megoldásának költsége ezért az elfogadható heurisztika (a megoldás csak könnyebb lehet) • If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h1(n) gives the shortest solution • If the rules are relaxed so that a tile can move to any adjacent square, then h2(n) gives the shortest solution Dr. Kovács Szilveszter ©

M.I. 5. / 53.

Memóriakorlátozott heurisztikus keresés • Néhány megoldás az A* hely-komplexitás problémájára (megtartva a teljességet és az optimalitást) – Iterative-deepening A* (IDA*) • Here cutoff information is the f-cost (g+h) instead of depth

– Recursive best-first search (RBFS) • Recursive algorithm that attempts to mimic standard best-first search with linear space.

– Simplified Memory-bounded A* (SMA*) • Drop the worst-leaf node when memory is full Dr. Kovács Szilveszter ©

M.I. 5. / 54.

Iteratívan mélyülő A* keresés (IDA*) • Cél: memóriaigény csökkentése • Meghatározunk egy f költségkorlátot és kezdetben csak az ezt meg nem haladó heurisztikus függvényértékkel rendelkező csomópontokat vizsgáljuk • Ha nem találtunk útvonalat a célig, akkor növeljük a korlátot • Minden egyes mélységkorlát esetén iteratívan mélyülő keresést alkalmaz

• A hely-komplexitása O(bd). Dr. Kovács Szilveszter ©

M.I. 5. / 55.

Recursive best-first search • Tárolja a rendelkezére á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ó. Dr. Kovács Szilveszter ©

M.I. 5. / 56.

Recursive best-first search, ex.

f-limit

Rosszabb mint az f-limit

• • • •

Path until Rumnicu Vilcea is already expanded Above node; f-limit for every recursive call is shown on top. Below node: f(n) The path is followed until Pitesti which has a f-value worse than the f-limit. Dr. Kovács Szilveszter ©

M.I. 5. / 57.

Recursive best-first search, ex.

f-limit csere A jobbnak tűnő ág kifejtése De valójában ez a rosszabb

• Unwind recursion and store best f-value for current best leaf Pitesti result, f [best] ← RBFS(problem, best, min(f_limit, alternative))

• best is now Fagaras. Call RBFS for new best – best value is now 450 Dr. Kovács Szilveszter ©

M.I. 5. / 58.

Recursive best-first search, példa

f-limit csere

• Unwind recursion and store best f-value for current best leaf Fagaras result, f [best] ← RBFS(problem, best, min(f_limit, alternative))

• best is now Rimnicu Viclea (again). Call RBFS for new best – Subtree is again expanded. – Best alternative subtree is now through Timisoara.

• Solution is found since because 447 > 418. Dr. Kovács Szilveszter ©

M.I. 5. / 59.

RBFS evaluation • RBFS is a bit more efficient than IDA* – Still excessive node generation (mind changes)

• Like A*, optimal if h(n) is admissible • Space complexity is O(bd). – IDA* retains only one single number (the current f-cost limit)

• Time complexity difficult to characterize – Depends on accuracy if h(n) and how often best path changes.

• IDA* and RBFS suffer from too little memory.


M.I. 5. / 60.

Simplified memory-bounded A* • Use all available memory. – I.e. expand best leafs until available memory is full – When full, SMA* drops worst leaf node (highest fvalue) – Like RFBS backup forgotten node to its parent What if all leafs have the same f-value? – Same node could be selected for expansion and deletion. – SMA* solves this by expanding newest best leaf and deleting oldest worst leaf. • SMA* is complete if solution is reachable, optimal if optimal solution is reachable. Dr. Kovács Szilveszter ©

M.I. 5. / 61.

Simplified memory-bounded A* ex.

Ezeket felszabadítja


M.I. 5. / 62.

Simplified memory-bounded A* ex.

f-érték csere a szülőkre menti az elfelejtett f értéket


M.I. 5. / 63.

Ajánlott irodalom • Jelen előadás fóliái részben az alábbi források alapján készültek: Stuart J. Russel – Peter Norvig: Mesterséges Intelligencia modern megközelítésben, PanemPrentice-Hall, Budapest, 2000, ISBN 963 545 241 1


M.I. 5. / 64.

Intelligens Rendszerek I. Problémamegoldás kereséssel: informált kereső eljárások (Heurisztikus keresés)

Recommend Documents