Intelligens Rendszerek I. Problémamegoldás kereséssel: nem informált keresés (blind search)

Intelligens Rendszerek I. Problémamegoldás kereséssel: nem informált keresés (blind search) 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

Ágens Az ágens olyan rendszer, amely • környezetbe ágyazott, • reaktív: érzékel és reagál, • racionális: helyesen cselekszik. • Lehet autonóm: saját tapasztalatai alapján, emberi beavatkozás nélkül működik.

Ágenstípusok • • • •

Egyszerű reflexszerű ágensek A világot nyomon követő ágensek Célorientált ágensek Hasznosságorientált ágensek Dr. Kovács Szilveszter ©

M.I. 4. / 2.

Egyszerű reflexszerű ágens • feltétel-cselekvés szabály (condition-action rule) (produkciós szabályok)

Működése • • • •

észleli a jelenlegi állapotot keres egy ehhez illeszkedő szabályt végrehajtja a szabályhoz illeszkedő cselekvést Nem „gondolkodik” előre, nem tud tervezni! Dr. Kovács Szilveszter ©

M.I. 4. / 3.

Célorientált ágens • A környezet pillanatnyi állapotának ismerete nem mindig elegendő a cselekvés meghatározásához

• A cél (goal) alapján történő döntés magába foglalja a jövő figyelembevételét • A lehetséges cselekvések által elérhető új állapotok becslése alapján cselekvési tervet készít

Dr. Kovács Szilveszter ©

M.I. 4. / 4.

A célorientált ágens struktúrája Érzékelők

Hogyan változik a világ?

Hogyan néz ki most a világ? (becsült állapot)

A cselekvések hatása

Hogyan fog kinézni, ha az A cselekvést hajtom végre?

Célok Ágens

Környzet

Korábbi állapot

Cselekvés kiválasztás Beavatkozók Dr. Kovács Szilveszter ©

M.I. 4. / 5.

Célorientált ágens • Az ágens célját elérő cselekvéssorozat: – keresés a jövő figyelembevétele – tervkészítés • (új cél → új viselkedés)


M.I. 4. / 6.

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. 4. / 7.

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. 4. / 8.

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. 4. / 9.

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. 4. / 10.

A kereséssel történő problémamegoldás lépései • A probléma megfogalmazása: A probléma ismeretek gyűjteménye, amit az ágens annak a meghatározására használ, hogy mit tegyen a cél elérésének érdekében (célok, állapotok, cselekvések) • A probléma megoldása: Kereső eljárás alkalmazása, a célállapotot elérő cselekvéssorozatok keresése • Végrehajtás


M.I. 4. / 11.

Probléma megfogalmazás Milyen szinten vegyük figyelembe a cselekvéseket és az állapotokat? – Teljes részletességgel: a kormánykereket hat fokkal tekerd balra —> a feladat megoldhatatlan – A feladat lényegét kiemelve: (absztrakció) melyik útvonalat válassza? —> a feladat megoldható


M.I. 4. / 12.

Probléma megfogalmazás • Erősen befolyásolja a keresés hatékonyságát, hogy mit értünk lehetséges állapotokon cselekvéseken • pl. 20*20-as amőba játék. – Lehetséges lépésként az összes mezőt vizsgáljuk: az első lépéseknél 100-as nagyságrend, nagyon nagy elágazási tényezőjű (b: branching factor) fagráf (kombinatorikus robbanás) – Csak az első lépés környezetében levő üres helyeket vizsgáljuk egy 9*9-es mezőben, mivel az utolsónak lerakott jel csak ebben a részben alkothat nyerő ötöst b:max. 80 – Csak az előző lépésre illesztett csillag alakzat üres helyeire végezzük a vizsgálatot b:max. 32 Dr. Kovács Szilveszter ©

M.I. 4. / 13.

Pl. amőba játék, állapot reprezentációk

X X X O X X O O O O X O


M.I. 4. / 14.

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: cselekvések, melyek hatására az ágens egy adott állapotból egy másik állapotba kerül – S(x) következő állapotfüggvény: egy adott x állapotban valamely 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. 4. / 15.

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. 4. / 16.

Pl: Amőba játék • Állapotok: lehetséges lépésekkel kialakuló helyzetek • Operátorok: lépések • Célteszt: öt egyforma jel folyamatosan egy sorban, egy oszlopban vagy átlósan • Útköltség: nulla • Megoldás: egy út (lépés sorozat) a kiinduló és a céltesztet teljesítő állapot között Dr. Kovács Szilveszter ©

M.I. 4. / 17.

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. 4. / 18.

Utazási példa: Románia térkép


M.I. 4. / 19.

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, ahova Aradról el lehet jutni (á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. 4. / 20.

Keresés • Térkép - állapotok, ahova az ágens eljuthat - végrehajtható cselekvések • Ágens - megvizsgálja a lehetséges cselekvés sorozatokat, amelyek a célhoz vezetnek - kiválasztja a legjobbat (útiköltség) valamely keresési stratégiával

Végrehajtás • A megtalált cselekvéssorozat megvalósítása Dr. Kovács Szilveszter ©

M.I. 4. / 21.

Példa: porszívóvilág Operátorok: – balra – jobbra – porszívás

Cél: az összes szemét eltakarítása célállapot: {7,8} Útköltség: minden cselekvés költsége: 1, additív


M.I. 4. / 22.

Porszívóvilág: mint egyállapotú probléma • Az érzékelők megadják, hogy melyik állapotban van (melyik négyzet, szemetes-e a padló?) • Pontosan tudja, hogy cselekvései mit eredményeznek • pl. kiinduló állapot {5} • megoldás: [jobb, porszívás]


M.I. 4. / 23.

Vacuum world state space graph (állapottér gráf)

• • • •

states? integer dirt and robot location actions? Left, Right, Suck goal test? no dirt at all locations path cost? 1 per action Dr. Kovács Szilveszter ©

M.I. 4. / 24.

Porszívóvilág: mint többállapotú probléma • Nem tudja, hogy melyik állapotban van (melyik négyzet, ott szemetes-e a padló?) • Pontosan tudja, hogy cselekvései mit eredményeznek (ha a falnak ütközne, akkor a cselekvés nem hajtódik végre) • Következtetés állapothalmazokkal • Kiinduló állapot: {1,2,3,4,5,6,7,8} • Megoldás: pl: [jobb, porszívás, bal, porszívás] Dr. Kovács Szilveszter ©

M.I. 4. / 25.

Porszívóvilág: mint többállapotú probléma

Következtetés állapothalmazokkal Dr. Kovács Szilveszter ©

M.I. 4. / 26.

Porszívóvilág: mint eshetőségi probléma • Módosítás: tiszta szoba esetén a porszívózás koszt csinál (Murphy) • Tudja, hogy melyik négyzetben van pl. {1,3} kiinduló állapot • De nem tudja, hogy szemetes-e a szomszéd négyzet • Nem létezik rögzített cselekvéssorozat, ami garantálja a megoldást Megoldás: • Érzékelésre van szükség a végrehajtási fázisban (ettől többállapotú probléma lesz) • Pl. érzékeli az adott négyzeten belül a szemetet • [porszívás, jobbra, ?] csak akkor takarít, ha koszos a szőnyeg Dr. Kovács Szilveszter ©

M.I. 4. / 27.

Felderítési probléma • Az ágens nem ismeri előre cselekvései hatását és a létező állapotokat • Kísérletezés: cselekvései hatásainak, és létező állapotok fokozatos feltérképezése • A valós világban, nem pedig a modellben keres • Tanulás tapasztalatok útján • pl. Újszülött


M.I. 4. / 28.

Játék problémák • • • • •

nyolcas kirakójáték 8 királynő probléma betűaritmetika porszívóvilág hittérítők és kannibálok


M.I. 4. / 29.

Példa: nyolcas kirakójáték (8-puzzle)

• • • •

states? locations of tiles actions? move blank left, right, up, down goal test? = goal state (given) path cost? 1 per move

[Note: optimal solution of n-Puzzle family is NP-hard]


M.I. 4. / 30.

Példa: 8 királynő probléma

Állapotok: 8 királynő a táblán, minden oszlopban egy-egy Operátorok: minden támadott királynőt a saját oszlopában mozgasd Célteszt: támadják-e egymást? Útköltség: 0 Dr. Kovács Szilveszter ©

M.I. 4. / 31.

Betűaritmetika FORTY TEN TEN _______ SIXTY

29786 850 850 _____ 31486

F=2 O=9 R=7 stb.

Állapotok: betűaritmetikai feladvány, néhány betűt már szám helyettesíthet Operátorok: egy betű minden előfordulását cseréld le Célteszt: csak számok, helyes Útköltség: 0, minden megoldás jó Dr. Kovács Szilveszter ©

M.I. 4. / 32.

Hittérítők és kannibálok 3H+3K+1 csónak Feladat: Átkelési mód úgy, hogy a kannibálok sehol ne legyenek túlsúlyban. A csónakba max. 2 személy fér, a csónak nem kellhet át üresen Állapotok: (H,K,Cs) az indulási oldalon oldalon; kiinduló: (3,3,1) Operátor: vigyük át a csónakban Célteszt: (0,0,0) Útköltség: átkelések száma


M.I. 4. / 33.

Jól definiált problémák • Játék problémák: – különböző problémamegoldó módszereket illusztrálnak vagy gyakoroltatnak – tömör és pontos leírás

• Valósvilágbeli problémák: – nehezen kezelhető – nem létezik egységes, elfogadott leírás


M.I. 4. / 34.

Valósvilágbeli problémák • útkeresés:

pl. számítógép hálózatok, légi útvonal keresés • utazó ügynök: minden városba legalább egyszer, vagy csak egyszer furatok készítésénél automatikus fúrómozgás • chip tervezés cellaelrendezés, huzalozás cél: felület és összeköttetéskor minimalizálás • alkatrészek összeszerelési sorrendjének megkeresése


M.I. 4. / 35.

Example: robotic assembly

• states?: real-valued coordinates of robot joint angles parts of the object to be assembled • actions?: continuous motions of robot joints • goal test?: complete assembly • path cost?: time to execute


M.I. 4. / 36.

Megoldások keresése • Cselekvéssorozatok generálása • Keresési fa (search tree) adatszerkezete • Keresési stratégiák


M.I. 4. / 37.

Utazási példa: Románia


M.I. 4. / 38.

Keresési fa


M.I. 4. / 39.

Keresési fa


M.I. 4. / 40.

Keresési fa


M.I. 4. / 41.

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

A 1

S 15

5

B 5 C

0. szint

S 10 G 5

A

B 5

C 15

1. szint

G

G

G

2. szint

1

11 Dr. Kovács Szilveszter ©

10

20

M.I. 4. / 42.

Keresési fa - terminológia • 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. 4. / 43.

Keresési fa - terminológia • Elágazási tényező (branching factor: b): egy állapot kifejtésekor keletkező új állapotok maximális száma • A keresési fa mélysége (m): a fa gyökerétől a legtávolabbi levélig vezető út csomópontjainak száma • A megoldás mélysége (depth: d): a fa gyökerétől a legközelebbi megoldásig vezető út csomópontjainak száma • Mélységi korlát (l): a leghosszabb kifejtett utak csomópontjainak száma • Az n. állapotba vezető út költsége g(n) Dr. Kovács Szilveszter ©

M.I. 4. / 44.

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 (a 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 Dr. Kovács Szilveszter ©

M.I. 4. / 45.

Keresési költség • Statikus környezetben: nulla • Szemidinamikus környezetben (pl., ha sürgős az utazás) függhet a számítási időtől • Dinamikus környezet: egyértelmű függés az időtől - a pontos kapcsolat problémafüggő


M.I. 4. / 46.

Keresési módszerek • Nem informált (non informed, blind (vak) search): – – – – – –

szélességi, egyenletes költségű, mélységi, mélységkorlátozott, iteratívan mélyülő, kétirányú keresés

• Informált (heurisztikus keresés): – globális információra (heurisztikára) támaszkodó eljárások: legjobbat először, A, A*, iteratív A* – lokális információra támaszkodó eljárások: hegymászó keresés, szimulált lehűtés, tabu keresés Dr. Kovács Szilveszter ©

M.I. 4. / 47.

Példák kereséssel megoldható feladatokra • útkeresés két város között • bűvös kocka • hogyan lehet 31 dominóval lefedni egy, az átellenes sarkain csonka sakktáblát? • hittérítők és kannibálok • nyolcas kirakójáték


M.I. 4. / 48.

Nyolcas kirakójáték


M.I. 4. / 49.

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. 4. / 50.

Szélességi keresés • Mindig a legsekélyebben fekvő kifejtésre váró csomópontot fejti ki először • Implementation: – fringe is a FIFO queue, i.e., new successors go at end


M.I. 4. / 51.



M.I. 4. / 52.



M.I. 4. / 53.



M.I. 4. / 54.

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ő? 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) • Hely? O(bd) (keeps every node in memory) • 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 helyigény a nagyobb probléma, nem az időigény Dr. Kovács Szilveszter ©

M.I. 4. / 55.

Bonyolultságanalízis – O( ) Aszimptotikus elemzés (asymptotik analysis): T(n): O(f(n)) mértékű, ha T(n)≤ k.f(n)) valamilyen k-ra, minden n>n0 esetén. Pl. Ha n aszimptotikusan tart a végtelenhez, egy O(n) algoritmus jobb mint egy O(n2), vagy egy O(mn). (Hosszú távon rosszabb, pl. ha műveletszám, akkor van olyan n, amitől kezdve többet kell számolni) O( ) jó az algoritmusok számítási komplexitásának (pl. műveletszám) összevetésére, mert független a műveletek egzakt számától (k) és a bemenetek egzakt tartalmától (csupán n nagyságát figyelembe véve absztrahál). Dr. Kovács Szilveszter ©

M.I. 4. / 56.

Breadth-first search; evaluation • Two lessons: – Memory requirements are a bigger problem than its execution time. – Exponential complexity search problems cannot be solved by uninformed search methods for any but the smallest instances. DEPTH2

NODES

TIME

MEMORY

2

1100

0.11 seconds

1 megabyte

4

111100

11 seconds

106 megabytes

6

107

19 minutes

10 gigabytes

8

109

31 hours

1 terabyte

10

1011

129 days

101 terabytes

12

1013

35 years

10 petabytes

14

1015

3523 years

1 exabyte


M.I. 4. / 57.

Egyenletes költségű keresés • A hullámfront legkisebb költségű – ahova a legolcsóbban lehet eljutni - csomópontját fejti ki először • Addig folytatja, míg a hullámfront nem tartalmaz a talált megoldásnál kisebb értéket. • Megtalálja a legolcsóbb megoldást, ha az útköltség egy út bejárása során soha sem csökkenhet A (nincs negatív részköltség) 1 10 S

5

15 Dr. Kovács Szilveszter ©

B 5

C

G 5 M.I. 4. / 58.

Példa az egyenletes költségű keresésre S

S

S

S

0 A

B 1

C 5

15

B

A

C 5

15

G1 11

A G1 11

B

C

15

G2 10

A 1

S 15

5

B 5 C

10 G 5 Dr. Kovács Szilveszter ©

M.I. 4. / 59.

Az egyenletes költségű keresés tulajdonságai • Expand least-cost unexpanded node • Implementation: – fringe = queue ordered by path cost

• Amennyiben a lépésköltségek egyenlők, azonos a szélességi kereséssel. • Teljesség? Igen, ha step cost ≥ ε (∃ε > 0) • Idő? # of nodes with g ≤ cost of optimal solution, O(b(C*/ ε)) where C* is the cost of the optimal solution • Hely? # of nodes with g ≤ cost of optimal solution, O(b(C*/ ε)) • Optimalitás? Igen – nodes expanded in increasing order of g(n) Dr. Kovács Szilveszter ©

M.I. 4. / 60.

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 (olyan csomópont, melynek üres halmaz a kifejtése és amely nem cél csomópont) • A frissen generált csomópontok mindig a sor elejére kerülnek (LIFO – Last in First Out) • Az első találatig megy (az útköltséget nem veszi figyelembe a döntéseknél) Dr. Kovács Szilveszter ©

M.I. 4. / 61.

Mélységi keresés • Mindig a keresési fa legmélyebben fekvő csomópontjainak egyikét fejti ki • Implementation: – fringe = LIFO queue, i.e., put successors at front


M.I. 4. / 62.



M.I. 4. / 63.



M.I. 4. / 64.



M.I. 4. / 65.



M.I. 4. / 66.



M.I. 4. / 67.



M.I. 4. / 68.



M.I. 4. / 69.



M.I. 4. / 70.



M.I. 4. / 71.



M.I. 4. / 72.



M.I. 4. / 73.

Mélységi keresés tulajdonságai • Teljesség? Nem: elvész a végtelen mélységekben és hurkokban – El kell kerülni az út mentén ismétlődő állapotokat Æ véges fa esetén teljes!

a keresési fa mélysége

a megoldás mélysége

• Idő? O(bm): nagyon rossz, ha m sokkal nagyobb mint d – ha sűrűn vannak a megoldások, akkor sokkal gyorsabb is lehet mint a szélességi keresés

• Hely? 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. 4. / 74.

Mélységkorlátozott keresés • Mélységi keresés, de egy adott mélységnél nem mehetünk tovább a keresési fában. • A legelső talált megoldásnál megáll. • pl. Kecskemét Poreč övezetben n (n=29) város található - ha a lépések száma eléri az n-t, és nem értünk célba, akkor nincs értelme a folytatásnak.


M.I. 4. / 75.

Mélységkorlátozott keresés tulajdonságai • 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


M.I. 4. / 76.

Iteratívan mélyülő keresés • 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


M.I. 4. / 77.

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


M.I. 4. / 78.



M.I. 4. / 79.



M.I. 4. / 80.



M.I. 4. / 81.

Az iteratívan mélyülő keresés tulajdonságai • Number of nodes generated in a depth-limited search to depth d with branching factor b: NDLS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd • Number of nodes generated in an iterative deepening search to depth d with branching factor b: NIDS = (d+1)b0 + d b1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd • For b = 10, d = 5, – NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111 – NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

• Overhead = (123,456 - 111,111)/111,111 = 11% • A legtöbb csomópont a „fa alján” van Dr. Kovács Szilveszter ©

M.I. 4. / 82.

Az iteratívan mélyülő keresés tulajdonságai • • • •

Teljesség? Igen Idő? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd) Hely? O(bd) 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)


M.I. 4. / 83.

Szakirodalmi ajánlás Nagy keresési térrel rendelkező problémák esetén, és ha a megoldás mélysége nem ismert, az iteratívan mélyülő keresés alkalmazását javasolja.


M.I. 4. / 84.

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


M.I. 4. / 85.

Bidirectional search

• Két egyidejű keresés, egy a kiindulási, egy a célállapotból. – Motiváció:

b

d /2

+b

d /2

≠b

d

• Check whether the node belongs to the other fringe before expansion. • Space complexity is the most significant weakness. • Teljes és optimális, ha mindkét keresés szélességi keresés. Dr. Kovács Szilveszter ©

M.I. 4. / 86.

How to search backwards?

• The predecessor of each node should be efficiently computable. – When actions are easily reversible. Dr. Kovács Szilveszter ©

M.I. 4. / 87.

Summary of algorithms Criterion

BreadthFirst

Uniformcost

DepthFirst

Depthlimited

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


Iterative Bidirectio deepening nal search

M.I. 4. / 88.

Ismételt állapotok elkerülése Failure to detect repeated states can turn a solvable problems into unsolvable ones. Módszerek: • Ne térjen vissza a megelőző állapotba • Ne hozz létre kört tartalmazó utat • Ne generálj már korábban legenerált állapotot (valamennyi korábbi állapot tárolása – O(bd) tárigény)


M.I. 4. / 89.

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 Dr. Dudás László: Mesterséges Intelligencia Módszerek, Miskolci Egyetem, Alkalmazott Informatikai Tanszék, http://www.ait.iit.uni-miskolc.hu/~dudas/MIEAok Dr. Kovács Szilveszter ©

M.I. 4. / 90.

Intelligens Rendszerek I. Problémamegoldás kereséssel: nem informált keresés (blind search)

Recommend Documents