Syst´ emy s umˇ elou inteligenc´ı 1. Stavov´ y prostor a ˇreˇsen´ı u ´loh prohled´ av´ an´ım Jiˇr´ı Kubal´ık ˇ Katedra kybernetiky, CVUT-FEL
http://cw.felk.cvut.cz/doku.php/courses/A7B33SUI/start
pN´ aplˇ n pˇredmˇ etu
1. C´ıle umˇel´e inteligence. Stavov´y prostor a ˇreˇsen´ı u´loh prohled´av´an´ım 2. Neinformovan´e a informovan´e metody prohled´av´an´ı stavov´eho prostoru 3. Evoluˇcn´ı algoritmy 4. Umˇel´y ˇzivot a jeho aplikace 5. Znalosti, jejich z´ısk´av´an´ı a reprezentace, znalostn´ı inˇzen´yrstv´ı a management znalost´ı 6. Pˇrehled znalostn´ıch syst´em˚ u, zp˚ usoby reprezentace neurˇcitosti, pravdˇepodobnostn´ı rep. 7. Fuzzy logika, bayesovsk´e s´ıtˇe 8. Posibilistick´a teorie, Dempster-Shaferova teorie 9. S´emantick´e s´ıtˇe a r´amce, ontologie, Topic Maps, konceptu´aln´ı grafy, s´em. anotace e-zdroj˚ u 10. Deskripˇcn´ı logika, inference. S´emantick´y web - XML, RDF, OWL, SWRL a dalˇs´ı 11.
Velikonoce
12. Adaptivn´ı a uˇc´ıc´ı se syst´emy 13. Uˇcen´ı z pˇr´ıklad˚ u - z´akladn´ı metody 14. Logika, logick´e programov´an´ı a Prolog, rezoluˇcn´ı metoda
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pUmˇ el´ a inteligence Definice ”The exciting new effort to make computers think ... machines with minds, in the full and literal sense” (Haugeland, 1985) ”[The automation of] activities that we associate with human thinking, activities such as decision-making, problem solving, learning ...” (Bellman, 1978) ”The art of creating machines that perform functions that require intelligence when performed by people” (Kurzweil, 1990) ”The study of how to make computers do thinks at which, at the moment, people are better” (Rich and Knight, 1991)
”The study of mental faculties through the use of computational models” (Charniak and McDermott, 1985) ”The study of the computations that make it possible to perceive, reason, and act” (Winston, 1992) ”A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes” (Schalkoff, 1990) ”The branch of computer science that is concerned with the automation of intelligent behavior” (Luger and Stubblefield, 1993)
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pUmˇ el´ a inteligence Definice ”The exciting new effort to make computers think ... machines with minds, in the full and literal sense” (Haugeland, 1985) ”[The automation of] activities that we associate with human thinking, activities such as decision-making, problem solving, learning ...” (Bellman, 1978) ”The art of creating machines that perform functions that require intelligence when performed by people” (Kurzweil, 1990) ”The study of how to make computers do thinks at which, at the moment, people are better” (Rich and Knight, 1991)
”The study of mental faculties through the use of computational models” (Charniak and McDermott, 1985) ”The study of the computations that make it possible to perceive, reason, and act” (Winston, 1992) ”A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes” (Schalkoff, 1990) ”The branch of computer science that is concerned with the automation of intelligent behavior” (Luger and Stubblefield, 1993)
ˇ ri kategorie Ctyˇ Syst´emy, kter´e mysl´ı jako ˇclovˇek Syst´emy, kter´e jednaj´ı jako ˇclovˇek
Syst´emy, kter´e mysl´ı racion´alnˇe Syst´emy, kter´e jednaj´ı racion´alnˇe
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pTuring˚ uv test
:: Alan Turing: ”Computing machinery and intelligence”, 1950 Bude-li stroj reagovat na podnˇ ety lidsk´eho partnera takov´ym zp˚ usobem, ˇze ˇclovˇek nen´ı schopen rozeznat, zda jedn´a se strojem ˇci s jinou osobou prostˇrednictv´ım termin´alu, lze povaˇzovat stroj za inteligentn´ı.
Identifikoval hlavn´ı souˇc´asti umˇel´e inteligence – znalost a jej´ı reprezentace, uvaˇzov´an´ı, porozumˇen´ı pˇrirozen´emu jazyku, uˇcen´ı.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pArgument proti Turingovu testu
:: Argument ˇ c´ınsk´ eho pokoje (John Searl, 1980) – samotn´a schopnost smysluplnˇe odpov´ıdat na poloˇzen´e ot´azky nen´ı dostateˇcnou pro prok´az´an´ı schopnosti porozumˇen´ı, coˇz je to nejduleˇzitejˇs´ı, co oˇcek´av´ame od tzv. siln´e umˇel´e inteligence.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pCo vˇsechno patˇr´ı do umˇ el´ e inteligence
Rozpozn´av´an´ı,
Reprezentace znalost´ı,
Expertn´ı a znalostn´ı syst´emy, ˇ sen´ı u´loh, Reˇ
Kvalitativn´ı modelov´an´ı,
Strojov´e uˇcen´ı, neuronov´e s´ıtˇe,
Pl´anov´an´ı a rozvrhov´an´ı,
Zpracov´an´ı pˇrirozen´eho jazyka,
Automatick´e uvaˇzov´an´ı, dokazov´an´ı,
Robotika,
Distribuovan´a UI a Multi-Agentn´ı Syst´emy, . . .
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı stavov´ eho prostoru: Motivaˇ cn´ı pˇr´ıklady ˇ sen´ı mnoha probl´em˚ :: Reˇ u vede na probl´em hled´an´ı sekvence akc´ı, kter´e vedou do poˇzadovan´eho stavu. :: Pˇr´ıklady takov´ych probl´em˚ u:
ˇ Skoln´ ı pˇr´ıklady - hry − Liˇs´ak (8-puzzle) - naj´ıt posloupnost tah˚ u, vedouc´ı k poˇzadovan´e c´ılov´e konfiguraci − 8 dam na ˇsachovnici - naj´ıt postaven´ı 8 dam na ˇsachovnici tak, aby se vz´ajemnˇe neohroˇzovaly − Kryptogramy - naj´ıt pˇriˇrazen´ı ˇc´ıslic p´ısmen˚ um tak, aby aritmetick´y v´yraz byl spr´avnˇe − ...
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı stavov´ eho prostoru: Motivaˇ cn´ı pˇr´ıklady ˇ sen´ı mnoha probl´em˚ :: Reˇ u vede na probl´em hled´an´ı sekvence akc´ı, kter´e vedou do poˇzadovan´eho stavu. :: Pˇr´ıklady takov´ych probl´em˚ u:
ˇ Skoln´ ı pˇr´ıklady - hry − Liˇs´ak (8-puzzle) - naj´ıt posloupnost tah˚ u, vedouc´ı k poˇzadovan´e c´ılov´e konfiguraci − 8 dam na ˇsachovnici - naj´ıt postaven´ı 8 dam na ˇsachovnici tak, aby se vz´ajemnˇe neohroˇzovaly − Kryptogramy - naj´ıt pˇriˇrazen´ı ˇc´ıslic p´ısmen˚ um tak, aby aritmetick´y v´yraz byl spr´avnˇe − ...
Re´ aln´ e probl´ emy − Smˇerov´an´ı v s´ıti (routing problem) - naj´ıt (optim´aln´ı) cestu ze zdrojov´eho uzlu k c´ılov´emu − VLSI n´avrh - nal´ezt optim´aln´ı rozloˇzen´ı hradel a jejich propojen´ı na ˇcipu (cell layout - chanel routing). − pl´anov´an´ı (v´yrobn´ı linky) - nal´ezt posloupnost akc´ı tak, aby vˇsechny poˇzadovan´e v´yrobky byly sestaveny v nejkratˇs´ım ˇcase.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pFormulace probl´ emu
:: Pˇredpoklad´ame, ˇze um´ıme v kaˇzd´em okamˇziku rozhodnout v kter´em stavu se nach´az´ıme a tak´e um´ıme rozhodnout, do kter´eho stavu se dostaneme po proveden´ı jak´ekoliv sekvence akc´ı. Formulace probl´ emu se skl´ad´a z n´asleduj´ıc´ıch bod˚ u: Stavy - obecn´ y popis stavu ˇreˇsen´eho probl´emu. Poˇ c´ ateˇ cn´ı stav - definice poˇc´ateˇcn´ıho stavu.
Prostor stav˚ u - mnoˇzina vˇsech stav˚ u dosaˇziteln´ych z poˇc´ateˇcn´ıho stavu.
C´ılov´ y test - ovˇeˇren´ı, zda dan´y stav splˇnuje podm´ınky na c´ılov´y stav.
Cesta - posloupnost akc´ı, kter´ymi se dostaneme z jednoho stavu do druh´eho.
Oper´ atory - mnoˇzina pouˇziteln´ych akc´ı (funkce n´asledn´ık stavu S(x)), definuj´ıc´ı, jak se zmˇen´ı dan´y stav po aplikaci oper´atoru.
Cena cesty - souˇcet cen akc´ı proveden´ych na dan´e cestˇe. ˇ sen´ı - cesta z poˇc´ateˇcn´ıho stavu do stavu, kter´y splˇnuje c´ılov´y test. Reˇ
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pFormulace probl´ emu: Liˇs´ ak
Stavy - stavov´y popis specifikuje postaven´ı vˇsech kamen˚ u (vˇcetnˇe pr´azdn´eho pole) na desce.
Oper´ atory - pr´azdn´e pol´ıˇcko se posune nahoru, dol˚ u, doprava nebo doleva.
Poˇ c´ ateˇ cn´ı stav - stav odpov´ıd´a konfiguraci ”Start State” z obr´azku.
C´ılov´ y test - stav odpov´ıd´a konfiguraci ”Goal State” z obr´azku.
Cena cesty - kaˇzd´y tah stoj´ı 1; cena cesty je jej´ı d´elka.
c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pFormulace probl´ emu: Kryptogram
Stavy - v´yraz sloˇzen´y z p´ısmen a ˇc´ıslic. Oper´ atory - nahradˇ vˇsechny v´yskyty jednoho p´ısmene ˇc´ıslic´ı, kter´a se jeˇstˇe nevyskytuje ve v´yrazu.
C´ılov´ y test - v´yraz obsahuje pouze ˇc´ıslice a je aritmeticky spr´avnˇe.
Cena cesty - cena cesty je e, vˇsechna ˇreˇsen´ı jsou ekvivalentn´ı.
Pˇr´ıklad:
FORTY ˇreˇsen´ı: 29786 F=2, O=9, R=7, atd. + TEN 850 + TEN 850 ——— ——— SIXTY 31486
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ avac´ı strom :: Prohled´ avan´ y prostor je reprezentov´an grafem (stromem), kde uzly odpov´ıdaj´ı rozpracovan´ym ˇreˇsen´ım dan´eho probl´emu (konfigurace hry Liˇs´ak) a hrany odpov´ıdaj´ı akc´ım, kter´e se na stavy mohou aplikovat (pˇr´ıpustn´e tahy).
Koˇren - uzel odpov´ıdaj´ıc´ı poˇc´ateˇcn´ımu stavu.
Listy - odpov´ıdaj´ı stav˚ um, kter´e uˇz nemaj´ı ˇz´adn´e n´asledovn´ıky.
Expanze uzlu - vygenerov´an´ı vˇsech n´asledovn´ık˚ u dan´eho uzlu.
Vˇ etvic´ı faktor b (branching f.) - poˇcet nov´ych stav˚ u, generovan´ych expanz´ı kaˇzd´eho stavu.
Prohled´ avac´ı strategie - urˇcuje, kter´y uzel bude expandov´an jako prvn´ı.
:: Seznamy uzl˚ u, pouˇz´ıvan´e pro sledov´an´ı pr˚ ubˇehu prohled´av´an´ı stavov´eho stromu
open - vygenerovan´e, ale jeˇstˇe nezpracovan´e (neexpandovan´e) uzly. Poˇrad´ı vyb´ır´an´ı uzl˚ u ze seznamu open je urˇceno prohled´avac´ı strategi´ı. closed - jiˇz vyˇsetˇren´e uzly.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ avac´ı strategie
:: Z´akladn´ı krit´eria pro posuzov´an´ı prohled´avac´ıch strategi´ı: ´ Uplnost (completeness) - zaruˇcuje strategie nalezen´ı ˇreˇsen´ı, pokud existuje? ˇ Casov´ a sloˇ zitost (time complexity) - jak dlouho trv´a nalezen´ı ˇreˇsen´ı?
Pamˇ eˇtov´ a sloˇ zitost (space complexity) - kolik pamˇeti dan´a strategie vyˇzaduje?
Optimalita - nach´az´ı dan´a strategie optim´aln´ı ˇreˇsen´ı, v pˇr´ıpadˇe ˇze moˇzn´ych ˇreˇsen´ı je v´ıce?
:: Z´akladn´ı ˇclenˇen´ı prohled´avac´ıch strategi´ı: Neinformovan´ e (slep´e) - nepracuj´ı s informac´ı o cenˇe cesty z aktu´aln´ıho stavu do c´ılov´eho stavu. Neefektivn´ı, ale ˇcasto jedin´e moˇzn´e.
Informovan´ e (heuristick´e) - z aktu´aln´ıho stavu se pokraˇcuje do jeho n´asledn´ıka s nejpˇr´ıznivˇejˇs´ım odhadem ceny cesty do c´ılov´eho stavu.
:: Veliˇciny pouˇz´ıvan´e pˇri anal´yze ˇcasov´e a pamˇeˇtov´e sloˇzitosti algotitm˚ u: b - vˇ etvic´ı faktor prohled´avan´eho stromu; poˇcet n´asledn´ık˚ u kaˇzd´eho uzlu.
d - hloubka ˇreˇsen´ı s nejmenˇs´ı cenou.
m - maxim´aln´ı hloubka stromu.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı do ˇs´ıˇrky
c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
:: Uzly stromu jsou prozkoum´ av´ any po u ´rovn´ıch – nejprve vˇsechny uzly prvn´ı u´rovnˇe, potom vˇsechny uzly druh´e u´rovnˇe, atd. Z toho plyne:
pokud ˇreˇsen´ı existuje, tak bude zaruˇcenˇe nalezeno, a pokud je ˇreˇsen´ı v´ıce, tak bude vˇzdy nalezeno ˇreˇsen´ı s nejmenˇs´ı hloubkou od koˇrenov´eho uzlu (v´ychoz´ıho stavu), a toto ˇreˇsen´ı je z´aroveˇn optim´aln´ı, pokud vˇsechny oper´atory maj´ı stejnou a kladnou cenu.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı do ˇs´ıˇrky
c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
:: Uzly stromu jsou prozkoum´ av´ any po u ´rovn´ıch – nejprve vˇsechny uzly prvn´ı u´rovnˇe, potom vˇsechny uzly druh´e u´rovnˇe, atd. Z toho plyne:
pokud ˇreˇsen´ı existuje, tak bude zaruˇcenˇe nalezeno, a pokud je ˇreˇsen´ı v´ıce, tak bude vˇzdy nalezeno ˇreˇsen´ı s nejmenˇs´ı hloubkou od koˇrenov´eho uzlu (v´ychoz´ıho stavu), a toto ˇreˇsen´ı je z´aroveˇn optim´aln´ı, pokud vˇsechny oper´atory maj´ı stejnou a kladnou cenu. Co kdyby mˇ ely oper´ atory r˚ uzn´ e ceny?
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pAlgoritmus prohled´ av´ an´ı do ˇs´ıˇrky open := [Start]; closed := []; while open 6= [] do odstraˇn prvn´ı uzel x ze seznamu open; if(x = goal) return ”ˇreˇsen´ı nalezeno”; else generuj potomky [xi] uzlu x; pˇridej x do closed; pˇridej vˇsechny xi, kteˇr´ı nejsou v open ani closed na konec open; return ”ˇreˇsen´ı nenalezeno”;
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pAlgoritmus prohled´ av´ an´ı do ˇs´ıˇrky open := [Start]; closed := []; while open 6= [] do odstraˇn prvn´ı uzel x ze seznamu open; if(x = goal) return ”ˇreˇsen´ı nalezeno”; else generuj potomky [xi] uzlu x; pˇridej x do closed; pˇridej vˇsechny xi, kteˇr´ı nejsou v open ani closed na konec open; return ”ˇreˇsen´ı nenalezeno”; Ot´ azka: Jak zrekonstruujeme cestu k ˇreˇsen´ı?
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı do ˇs´ıˇrky: Pamˇ eˇtov´ aaˇ casov´ a sloˇ zitost
:: Pˇredpokl´adejme, ˇze pro dan´y probl´em s vˇetvic´ım faktorem b = 10, leˇz´ı ˇreˇsen´ı v hloubce d, 1000 uzl˚ u m˚ uˇze b´yt ovˇeˇreno na c´ılov´y test za 1s a kaˇzd´y uzel zabere 100B pamˇeti. Potom
maxim´aln´ı poˇcet vyˇsetˇren´ych uzl˚ u je 1 + b + b2 + b3 + · · · + bd,
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı do ˇs´ıˇrky: Pamˇ eˇtov´ aaˇ casov´ a sloˇ zitost
:: Pˇredpokl´adejme, ˇze pro dan´y probl´em s vˇetvic´ım faktorem b = 10, leˇz´ı ˇreˇsen´ı v hloubce d, 1000 uzl˚ u m˚ uˇze b´yt ovˇeˇreno na c´ılov´y test za 1s a kaˇzd´y uzel zabere 100B pamˇeti. Potom
maxim´aln´ı poˇcet vyˇsetˇren´ych uzl˚ u je 1 + b + b2 + b3 + · · · + bd,
c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
coˇz znamen´a pˇr´ıliˇs mnoho ˇcasu a jeˇstˇe v´ıce pamˇeti pro probl´emy s d = 6 a v´ıc, takˇze pouze mal´e probl´emy mohou b´yt ˇreˇseny v rozumn´em ˇcase s rozumn´ymi pamˇeˇtov´ymi n´aroky.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı s jednotnou cenou (Uniform cost search) :: V kaˇzd´em kroku se expanduje uzel s nejniˇzˇs´ı cenou cesty g(n) z koˇrenov´eho uzlu do n
pokud je splnˇena podm´ınka na neklesaj´ıc´ı g(n) pod´el cesty, tj. g(SU CCESOR(n)) ≥ g(n), je prvn´ı nalezn´e ˇreˇsen´ı rovnˇeˇz optim´aln´ım ˇreˇsen´ım (vˇsechny oper´atory maj´ı nez´apornou cenu), ˇreˇsen´ı je nalezeno tehdy, kdyˇz je nalezen uzel splˇnuj´ıc´ı c´ılov´y test a z´aroveˇn neexistuje v seznamu Open uzel s niˇzˇs´ı hodnotou g(n). prohled´av´an´ı do ˇs´ıˇrky je prohled´av´an´ı s jednotnou cenou s g(n) = depth(n).
c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı do hloubky
:: Prohled´ av´ an´ı se zanoˇruje do hloubky, dokud to jde. Pokud uzel nesplˇnuje c´ılov´y test a nelze jej d´ale expandovat → backtracking.
c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı do hloubky
:: Prohled´ av´ an´ı se zanoˇruje do hloubky, dokud to jde. Pokud uzel nesplˇnuje c´ılov´y test a nelze jej d´ale expandovat → backtracking.
c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
ˇ ım se bude liˇsit algoritmus prohl. do hloubky od algoritmu prohl. do Ot´ azka: C´ ˇs´ıˇrky?
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pAlgoritmus prohled´ av´ an´ı do hloubky open := [Start]; closed := []; while open 6= [] do odstraˇn prvn´ı uzel x ze seznamu open; if(x = goal) return ”ˇreˇsen´ı nalezeno”; else generuj potomky [xi] uzlu x; pˇridej x do closed; pˇridej vˇsechny xi, kteˇr´ı nejsou v open ani closed na zaˇ c´ atek open; return ”ˇreˇsen´ı nenalezeno”;
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı do hloubky 2
:: Pamˇ eˇtov´ a n´ aroˇ cnost
uchov´av´ame pouze uzly pod´el aktu´aln´ı cesty spolu se vˇsemi neexpandovan´ymi sousedn´ımi uzly uzl˚ u pod´el cesty (bm vs. bd),
kde m je maxim´aln´ı hloubka prohled´avac´ıho stromu,
pro b = m = 12: 111 TB (do ˇs´ıˇrky) vs. 12 kB(do hloubky).
ˇ :: Casov´ a sloˇ zitost
v nejhorˇs´ım pˇr´ıpadˇe je O(bm) podobnˇe jako u prohled´av´an´ı do ˇs´ıˇrky O(bd),
ovˇsem pro probl´emy s mnoha ˇreˇsen´ımi m˚ uˇze b´yt v´yraznˇe efektivnˇejˇs´ı neˇz prohled´av´an´ı do ˇs´ıˇrky.
:: Vlastnosti
nen´ı u´pln´e,
nen´ı optim´aln´ı.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı do hloubky s omezenou hloubkou
:: Nev´ yhoda prohled´av´an´ı do hloubky spoˇc´ıv´a v tom, ˇze se m˚ uˇze nekoneˇcnˇe zanoˇrovat slepou vˇetv´ı a minout ˇreˇsen´ı, kter´e je pomˇernˇe mˇelk´e ovˇsem v jin´e vˇetvi (strategie nen´ı u´pln´a – nezaruˇcuje nalezen´ı ˇreˇsen´ı) → Prohled´ av´ an´ı s omezenou hloubkou
pˇri nastaven´ı dostateˇcnˇe velk´eho limitu je strategie u´pln´a, ovˇsem nezaruˇcuje nalezen´ı ˇreˇsen´ı s nejkratˇs´ı cestou. pˇri nastaven´ı nedostateˇcnˇe mal´eho limitu nenajdeme ˇreˇsen´ı, nˇekdy lze urˇcit tzv. polomˇer prohled´avac´ıho prostoru – nejdelˇs´ı cesta mezi dvˇema stavy stavov´eho prostoru – kter´y lze vyuˇz´ıt pro vhodn´e nastaven´ı limitu (napˇr. routing problem).
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı s iterativn´ım prohlubov´ an´ım :: Nev´ıˇs, jak spr´avnˇe nastavit limit na max. hloubku prohled´av´an´ı? ⇒ zkouˇsej postupnˇe 0, 1, 2, . . .
tato strategie vz´ajemnˇe kombinuje dobr´e vlastnosti prohled´av´an´ı do ˇs´ıˇrky (je optim´ aln´ı a u ´pln´ a) a do hloubky (n´ızk´e pamˇeˇtov´e n´aroky). uzly jsou expandov´any v poˇrad´ı stejn´em jako u prohl. do ˇs´ıˇrky, ale nˇekter´e jsou expandov´any opakovanˇe.
c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı s iterativn´ım prohlubov´ an´ım: Anal´ yza
:: Ale co ty opakovan´ e expanze, to se pˇrece nem˚ uˇze vyplatit?
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı s iterativn´ım prohlubov´ an´ım: Anal´ yza
:: Ale co ty opakovan´ e expanze, to se pˇrece nem˚ uˇze vyplatit?
poˇcet vyˇsetˇren´ych uzl˚ u u prohled´av´an´ı do hloubky s omezenou hloubkou d a vˇetvic´ım faktorem b je 1 + b + b2 + · · · + bd−1 + bd; pro b = 10 a d = 5 to dˇel´a 1 + 10 + 100 + 1.000 + 10.000 + 100.000 =111.111,
u iterativn´ıho prohled´av´an´ı jsou uzly s hloubkou d expandov´any jednou, uzly o u´roveˇn v´yˇs dvakr´at, a tak d´ale aˇz koneˇcnˇe koˇrenov´y uzel je expandov´an (d + 1)-kr´at. Celkov´y poˇcet expanz´ı je (d + 1)1 + (d)b + (d − 1)b2 + · · · + 2bd−1 + 1bd; takˇze pro b = 10 a d = 5 to dˇel´a 6 + 50 + 400 + 3.000 + 20.000 + 100.000 =123.456.
iterativn´ı prohlubov´an´ı v tomto pˇr´ıpadˇe provede pouze o 11% v´ıce expanz´ı neˇz prohled´av´an´ı do hloubky s limitem. obecnˇe plat´ı, ˇc´ım vˇetˇs´ı je vˇetvic´ı faktor, t´ım menˇs´ı je pod´ıl opakovanˇe expandovan´ych uzl˚ uv celkov´em poˇctu expanz´ı.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ av´ an´ı s iterativn´ım prohlubov´ an´ım: Anal´ yza
:: Ale co ty opakovan´ e expanze, to se pˇrece nem˚ uˇze vyplatit?
poˇcet vyˇsetˇren´ych uzl˚ u u prohled´av´an´ı do hloubky s omezenou hloubkou d a vˇetvic´ım faktorem b je 1 + b + b2 + · · · + bd−1 + bd; pro b = 10 a d = 5 to dˇel´a 1 + 10 + 100 + 1.000 + 10.000 + 100.000 =111.111,
u iterativn´ıho prohled´av´an´ı jsou uzly s hloubkou d expandov´any jednou, uzly o u´roveˇn v´yˇs dvakr´at, a tak d´ale aˇz koneˇcnˇe koˇrenov´y uzel je expandov´an (d + 1)-kr´at. Celkov´y poˇcet expanz´ı je (d + 1)1 + (d)b + (d − 1)b2 + · · · + 2bd−1 + 1bd; takˇze pro b = 10 a d = 5 to dˇel´a 6 + 50 + 400 + 3.000 + 20.000 + 100.000 =123.456.
iterativn´ı prohlubov´an´ı v tomto pˇr´ıpadˇe provede pouze o 11% v´ıce expanz´ı neˇz prohled´av´an´ı do hloubky s limitem. obecnˇe plat´ı, ˇc´ım vˇetˇs´ı je vˇetvic´ı faktor, t´ım menˇs´ı je pod´ıl opakovanˇe expandovan´ych uzl˚ uv celkov´em poˇctu expanz´ı.
ˇ :: Z´ avˇ er: Casov´ a sloˇzitost iterativn´ıho prohlubov´an´ı je O(bd) a pamˇeˇtov´a n´aroˇcnost je O(bd).
strategie v´yhodn´a pˇri prohled´av´an´ı velk´ych stavov´ych prostor˚ u, kde nen´ı zn´ama hloubka ˇreˇsen´ı.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pProhled´ avac´ı strategie: Smˇ er prohled´ av´ an´ı
:: Dopˇredn´ e ˇretˇ ezen´ı (data-driven) – hled´a cestu od poˇc´ateˇcn´ıho stavu k c´ılov´emu
expanduje otevˇren´e stavy (generov´an´ı nov´ych stav˚ u),
konˇc´ı v okamˇziku, kdy je vygenerov´an stav splˇnuj´ıc´ı cilov´y test.
:: Zpˇ etn´ e ˇretˇ ezen´ı (goal-driven) – hled´a cestu od c´ılov´eho stavu k poˇc´ateˇcn´ımu
zaˇc´ın´a u c´ılov´eho stavu a vybere oper´atory, kter´ymi m˚ uˇze b´yt tento stav vygenerov´an,
podm´ınky, kter´e mus´ı b´yt splnˇeny pro aplikaci tˇechto oper´ator˚ u pˇredstavuj´ı nov´e podc´ıle,
opˇet hled´ame oper´atory, kter´e mohou generovat podc´ıle, dost´av´ame nov´e podc´ıle, atd.
prohled´av´an´ı konˇc´ı v okamˇziku, kdy nˇekter´y podc´ıl odpov´ıd´a poˇc´ateˇcn´ımu stavu ˇreˇsen´eho probl´emu.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pObousmˇ ern´ e prohled´ av´ an´ı
Prohled´av´an´ı bˇeˇz´ı paralelnˇe v obou smˇerech,
a konˇc´ı v okamˇziku, kdy se vˇetve dopˇredn´eho a zpˇetn´eho ˇretˇezen´ı stˇretnou.
c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pObousmˇ ern´ e prohled´ av´ an´ı: Anal´ yza ˇ :: Casov´ a sloˇ zitost Uvaˇ zujme prohled´avac´ı prostor s vˇetvic´ım faktorem b stejn´ym v obou smˇerech a ˇreˇsen´ım v hloubce d, potom toto ˇreˇsen´ı bude nalezeno nejh˚ uˇre v O(2bd/2) = O(bd/2) poˇctu generovan´ych uzl˚ u.
Pro b = 10 a d = 6: 1.111.111 (prohled´av´an´ı do ˇs´ıˇrky) vs. 2.222 (obousmˇern´e prohled´av´an´ı).
:: Pozn´ amky Nˇ ekdy m˚ uˇze b´yt tˇeˇzk´e definovat pˇredch˚ udce, pokud nem´ame pˇresnou specifikaci c´ılov´eho stavu, ale pouze definic´ı jeho vlastnost´ı (ˇsachy: jak´y je pˇredch˚ udce stavu ”mat”?).
Mus´ıme navrhnout efektivn´ı postup, jak ovˇeˇrit pro kaˇzd´y novˇe vygenerovan´y uzel, jestli se uˇz nenach´az´ı v prohledan´em podstromu opaˇcn´eho smˇeru prohled´av´an´ı. Mus´ıme rozhodnout, jak´e strategie prohled´av´an´ı pouˇz´ıt v kaˇzd´em smˇeru?
:: Pamˇ eˇtov´ a n´ aroˇ cnost
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pObousmˇ ern´ e prohled´ av´ an´ı: Anal´ yza ˇ :: Casov´ a sloˇ zitost Uvaˇ zujme prohled´avac´ı prostor s vˇetvic´ım faktorem b stejn´ym v obou smˇerech a ˇreˇsen´ım v hloubce d, potom toto ˇreˇsen´ı bude nalezeno nejh˚ uˇre v O(2bd/2) = O(bd/2) poˇctu generovan´ych uzl˚ u.
Pro b = 10 a d = 6: 1.111.111 (prohled´av´an´ı do ˇs´ıˇrky) vs. 2.222 (obousmˇern´e prohled´av´an´ı).
:: Pozn´ amky Nˇ ekdy m˚ uˇze b´yt tˇeˇzk´e definovat pˇredch˚ udce, pokud nem´ame pˇresnou specifikaci c´ılov´eho stavu, ale pouze definic´ı jeho vlastnost´ı (ˇsachy: jak´y je pˇredch˚ udce stavu ”mat”?).
Mus´ıme navrhnout efektivn´ı postup, jak ovˇeˇrit pro kaˇzd´y novˇe vygenerovan´y uzel, jestli se uˇz nenach´az´ı v prohledan´em podstromu opaˇcn´eho smˇeru prohled´av´an´ı. Mus´ıme rozhodnout, jak´e strategie prohled´av´an´ı pouˇz´ıt v kaˇzd´em smˇeru?
:: Pamˇ eˇtov´ a n´ aroˇ cnost Deklarovan´ a ˇcasov´a sloˇzitost m˚ uˇze b´yt zaruˇcena pouze za podm´ınky, ˇze algoritmus testov´an´ı pr˚ uniku vygenerovan´ych uzl˚ u v obou smˇerech pracuje v konstantn´ım ˇcase (napˇr. hash tables).
To vyˇzaduje, aby uzly alespoˇn jednoho smˇeru prohled´av´an´ı byly vˇsechny uloˇzeny v pamˇeti, takˇze pamˇeˇtov´a n´aroˇcnost neinformovan´eho obousmˇern´eho prohled´av´an´ı je O(bd/2) (Pouˇz´ıvaj´ı se haˇsovac´ı tabulky).
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pPorovn´ an´ı strategi´ı neinformovan´ eho prohled´ av´ an´ı krit´erium
do ˇs´ıˇrky s jednotnou do hloubky do hloubky iterativn´ı obousmˇern´e cenou s limitem prohlubov´an´ı obousmˇern´e ˇcas bd bd bm bl bd bd/2 pamˇeˇt bd bd bm bl bd bd/2 optim´aln´ı? ANO ANO NE NE ANO ANO u´pln´a ANO ANO NE ANO, if l ≥ d ANO ANO
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pZamezen´ı cyklen´ı
:: Mnoh´e probl´emy vedou na prohled´avac´ı stromy, ve kter´ych je moˇzn´e (nˇekdy pˇr´ımo nevyhnuteln´e) vygenerovat uzel, kter´y jiˇz byl pˇredt´ım vygenerov´an a expandov´an na jin´e cestˇe. Extr´emn´ı pˇr´ıpad:
z kaˇzd´eho uzlu vedou 2 r˚ uzn´e hrany do n´asleduj´ıc´ıho uzlu; stavov´y prostor obsahuje pouze m + 1 stav˚ u, ale 2m cest; c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
Co s t´ım?
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pZamezen´ı cyklen´ı
:: Mnoh´e probl´emy vedou na prohled´avac´ı stromy, ve kter´ych je moˇzn´e (nˇekdy pˇr´ımo nevyhnuteln´e) vygenerovat uzel, kter´y jiˇz byl pˇredt´ım vygenerov´an a expandov´an na jin´e cestˇe. Extr´emn´ı pˇr´ıpad:
z kaˇzd´eho uzlu vedou 2 r˚ uzn´e hrany do n´asleduj´ıc´ıho uzlu; stavov´y prostor obsahuje pouze m + 1 stav˚ u, ale 2m cest; c
Russell, Norvig: Artificial Intelligence: A Modern Approach.
Co s t´ım?
1. Nevracet se do stavu, ze kter´eho jsme do aktu´aln´ıho stavu pr´avˇe pˇriˇsli. Funkce expand nesm´ı vygenerovat n´asledovn´ıka uzlu n, kter´y by byl shodn´y s pˇredch˚ udcem n (tj. successor(n) 6= parent(n)). 2. Negenerovat cestu s cykly. Funkce expand nesm´ı vygenerovat uzel, kter´y uˇz je stejn´y jako nˇekter´y z jeho pˇredch˚ udc˚ u. 3. Negenerovat uzel, kter´y uˇz byl nˇekdy vygenerov´an. To vyˇzaduje, aby vˇsechny uzly, vygenerovan´e bˇehem prohled´av´an´ı, byly uloˇzeny v pamˇeti (Opˇet se pouˇz´ıvaj´ı haˇsovac´ı tabulky).
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pZ´ avˇ ery
Probl´em se skl´ad´a ze 4 ˇc´ast´ı: Poˇc´ateˇcn´ı stav, oper´atory,c´ılov´y test, cena cesty. C´ılem je naj´ıt cestu z poˇc´ateˇcn´ıho do c´ılov´eho stavu.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pZ´ avˇ ery
Probl´em se skl´ad´a ze 4 ˇc´ast´ı: Poˇc´ateˇcn´ı stav, oper´atory,c´ılov´y test, cena cesty. C´ılem je naj´ıt cestu z poˇc´ateˇcn´ıho do c´ılov´eho stavu. Vˇsechny strategie slep´eho prohled´av´an´ı maj´ı stejnou nejhorˇs´ı ˇcasovou sloˇzitost. Jde to v˚ ubec l´ epe?
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pZ´ avˇ ery
Probl´em se skl´ad´a ze 4 ˇc´ast´ı: Poˇc´ateˇcn´ı stav, oper´atory,c´ılov´y test, cena cesty. C´ılem je naj´ıt cestu z poˇc´ateˇcn´ıho do c´ılov´eho stavu. Vˇsechny strategie slep´eho prohled´av´an´ı maj´ı stejnou nejhorˇs´ı ˇcasovou sloˇzitost. Jde to v˚ ubec l´ epe? Obousmˇern´e prohled´av´an´ı m˚ uˇze v´yraznˇe sn´ıˇzit ˇcasovou n´aroˇcnost, ale nemus´ı b´yt vˇzdy pouˇziteln´e. Nav´ıc pamˇeˇtov´e n´aroky mohou b´yt ne´unosnˇe velk´e.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pZ´ avˇ ery
Probl´em se skl´ad´a ze 4 ˇc´ast´ı: Poˇc´ateˇcn´ı stav, oper´atory,c´ılov´y test, cena cesty. C´ılem je naj´ıt cestu z poˇc´ateˇcn´ıho do c´ılov´eho stavu. Vˇsechny strategie slep´eho prohled´av´an´ı maj´ı stejnou nejhorˇs´ı ˇcasovou sloˇzitost. Jde to v˚ ubec l´ epe? Obousmˇern´e prohled´av´an´ı m˚ uˇze v´yraznˇe sn´ıˇzit ˇcasovou n´aroˇcnost, ale nemus´ı b´yt vˇzdy pouˇziteln´e. Nav´ıc pamˇeˇtov´e n´aroky mohou b´yt ne´unosnˇe velk´e.
Prohled´av´an´ı do hloubky s iterativn´ım prohled´av´an´ım je rozumn´a alternativa pˇri ˇreˇsen´ı u´loh s rozs´ahl´ym prohled´avac´ım prostorem a nezn´amou hloubkou ˇreˇsen´ı.
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
pMateri´ aly
S. Russell, P. Norvig: ”Artificial Intelligence: A Modern Approach” (Second Edition), Prentice Hall, 2003. Luger, G.F., and Stubblefield, W.A. ”Artificial Intelligence: Structures and Stratergies for Complex Problem Solving.” (Third Edition), London: Addison-Wesley, 1998.
Maˇr´ık a kol.: Umˇel´a inteligence 1, 2, 3, 4, 5. Academia.
Internet . . .
Stavov´ y prostor a r ˇeˇ sen´ ı u ´loh prohled´ av´ an´ ım
