Created by
Základy umelej inteligencie (IZU) - Prehľadávanie stavového priestoru.md Added
- Ignore whitespace
+Pre ďalšie generácie študentov a záujemcov o oblasť AI, zverejňujem moje poznámky z predmetu Základy umelej inteligencie. Tieto poznámky dokumentujú oblasť známu taktiež aj ako prehľadávania stavového priestoru.
+Na čo je to dobré? Stavový priestor môže byť čokoľvek. Pre matematikov sú známe predovšetkým asi grafy a ich prechody. Pre bežných smrtelníkov to môžu byť mapy, bludiská na konci novín alebo sudoku (CSP problém). Niektorý možno poznajú hlavolami ako Problém N dám, Loydova osmićka, Hanoyské veže a pod.
+Nie je tu popísané strojové učenie, genetické algoritmy alebo rozpoznávanie obrazu a reči. Aj keď sme to na predmete prebrali, prepisovanie poznámok do elektronickej podoby je zdĺhavá robota a zrovna som na tom dosť zle s časom, tak že pokračovanie bude asi len v prípade že nespravím najblizší termín :D
+<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.0.13/css/all.css" integrity="sha384-DNOHZ68U8hZfKXOrtjWvjxusGo9WQnrNx2sqG0tfsghAvtVlRW3tvkXWZh58N9jp" crossorigin="anonymous">
+* vybraný uzol expanduj a všetky nové uzly, ktoré ešte nie su vo fronte OPEN ani v zozname CLOSED umiestni do fronty OPEN. Expandovaný uzol umiestni do zoznamu CLOSED
+* vybraný uzol expanduj, a všetky nové uzly, ktoré ešte v zásobníku nie su a taktiež nie su ani predkami (t.j. uzly, ktoré sa už rozgenerovali) umiestni do zásobníku OPEN
+V tabuľke som túto metódu nazval DFS+, v skutočnosti je to **DFS s elimínaciou rovnakých stavov v OPEN**
+Podobné metóde DLS popísanej vyšie, len bod 5 sa mení a pridáva sa podmienka, že uzly sa rozgenerujú, len ak je úroven zanorenia nižšia, ako je maximálna povolená hĺbka.
+Podobná metóde DLS a vlastne celý princíp spočíva v tom, že sa volá DLS s hĺbkou zanorenia 1, a postupne sa hlbka zanorenia inkrementuje. Ak metoda DLS skončí neuspechom, ale nebol rozvinutý uzol, pretože sa narazilo na max zanorenie, inkrementuje sa maximálne zanorenie a DLS sa spustí znova. Ak sa DLS skončilo, pretože je zásobník prázny, a limit nebol hitnutý, uloha nemá riešenie. Pravda že keď DLS skončí úspechom, tak máme riešenie a končíme prehľadávanie.
+Vo svojej podstate je to BFS s tým, že každá cesta je ohodnotená. Vieme taktiež použiť UCS verziu so zoznamom CLOSED a v prípade že máme viacero uzlov s rovnakým ohodnotením, nechávame len uzol s najnižším ohodnotením (najnižšou cenou). V prípade že by ceny všetkých ciest boli rovnaké, UCS degraduje na BFS. Z toho dôvodu taktiež nie je algoritmus vhodný, ak optimálna cesta vedie cez malý poćet uzlov s vysokým ohodnotením. V takom prípade sa prechádza zbytočne veľké mnoźstvo lacnejších ciest (tento problém rieši A*), ale algoritmus stále najde optimálnu cestu.
+3. Ak je možné na uzol na vrchole zásobníku aplikova prvý/ďalśí operátor, tak ho aplikujte, inak odstránte daný uzol s vrcholu zásobníku a pokračujte bodom 2.
+4. Ak je vygenerovaný uzol uzlom cieľovým tak sme našli riešenie (success), inak sa nový uzol vloží na vrchol zásobníku a pokraćuje sabodom 2.
+Rozdiel oproti DFS je v tom, že DFS pri rozgenerovaní uzlov vložilo na zásobník všetky nové uzly, zatiaľ čo backtracking vloží na zásobnik vždy len jeden nový uzol, a pri spätnom navrátení (narazilo na slepu cestu) rozgeneruváva dalsie uzly.
+Znova je možné algoritmus upraviť podobne ako pri DFS a to že sa na zásobník nevložia uzly, ktoré uź v zásobníku sú obsiahnuté, alebo su predkami práve expandovaného (rozgenerovaného) uzla.
+Ak ste niekedy hrali sudoku, tak určite viete pravidlá. Postupne dosadzujete čísla 1 - 9 do voľných políčok pričom každé číslo sa môže nachádzať len raz v:
+**VSUVKA:** Sudoku som pred predmetom IZU nikdy v živote nehral. Zrovna pri bodovanom cvičení z Forward checkingu a Min-conflictu som sa naučil ako pravidlá, tak aj ako aplikovať dané algoritmy na riešenie sudoku :) (neodporúčam, dané algoritmy sú pre PC. Manuálne je to zdlhavé s možnostou zavedenia chyby)
+Nič sa oproti základnému algoritmu nemení, ak by daná aplikácia operátoru (napr. dosadenie čísla na políćko) poruśovala obmedzujúce podmienky/pravidlá, tak sa operátor považuje za neaplikovateľný
+* Pre každú premennú i(i=1, ..., n) **(políčka v sudoku napríklad)** sa priradí množina prípustných hodnôt.
+1. Odstránte prvú hodnotu z množiny S(i) a priradte tuto hodnotu premennej x(i), nech X je nový stav tvorený hodnotami všetkých premenných x(i), kde i = <1,n>
+3. Odstránte z množín S(j), kde j = <i+1, n> všetky hodnoty, ktoré sú v konflikte s doteraz priradenými hodnotami
+4. Ak je niektorá množina S(j) prázdna, obnovte pôvodný stav množín S(j) pred bodom 3 a prejdite na bod 7.
+* pre každe políčko v sudoku zistite ake všetky hodnoty je moźné do daného políćka vloźiť a vytvorte mnoźinu týchto hodnôt
+* Prejdite všetky nasledujúce políčka a zistíte, ktoré hodnoty treba vyškrtnuť, lebo sa uź nedaju pre dané políćko pouźiť
+* Pokiaľ zistíte, že pre nejake polićko sa nedá pouźiť źiadna hodnota, daná hodnota prvého políčka sa nedá aplikovať, a teda sa zoberie dalsia hodnota preprve policko a skusi sa aplikovať
+* Pokiaľ pre každé ďalšie políčko ostala aspoň jedna hodnota, prejde sa na druhé políčko a pokraćuje sa rovnako ako pri prvom políćku.
+* Je možné že sa stane to, že v druhom políćku sa zrazu prejdu všetky hodnoty a ani jedna sa nebude dat aplikovať. V takom prípade sa zase vrátime na prvé políćko a zoberieme dalsiu hodnotu z mnoźiny.
+ * premennú s najväčším vplyvom na obmedzenie zvyšných volných premenných (farbenie obrazu, ak aplikujem tuto farbu, ovplyvni to moznosti v týchto x dalsich premenných (tvaroch))
+ * vybranie hodnoty, ktorá obmedzi najmenej hodnôt v dalsich premenných (ak na prve policko v sudoku viem aplikovat cisla 1,2,3 a vo vsetkych ostatných sa nachádza len 1,2 a 4,5 tak zvolim 3, nakolko ovplyvni najmenej hodnôt dalsich policok)
+1. Prirad každej premennej x(i), kde i = <1,n> ) ľubovolnú hodnotu z množiny prípustných hodnôt. Nastav premenné i a j na 1.
+3. Pokiaľ existuje hodnota premennej x(i) kde je menší počet konfliktov tak ju použi (použije sa tá, kde je rozdiel najväčší). V prípade že vychádza rovnaký počet konfliktov, tak ju zmeň aj tak. A resetuj hodnotu premennej j na 1. Ak takáto hodnota neexistuje inkrementuj premennu j.
+4. Pokiaľ sa j rovná počtu premenných, našli sme optimálne riešenie (prešli sa všetky premenne bez akejkoľvek zmeny). (success)
+5. Inkrementuj premnnú i. Ak i > n, resetuj i na 1. Inak povedané, zační prechádzať premenné od znova.
+* do kazdeho volneho policka vlozime nahodne cislo z mnoziny pripustnych hodnôt. Cisla vlozime naraz, takze riesime len obmedzenia danne hodnotami, ktore su v sudoku od "výroby".
+* zoberieme teraz prve poličko takto vyplnenej sudoku. Pre každú jednu hodnotu v množine a aj tú, ktorú sme dosadili vypoćítame poćet konfliktov. Pozrieme sa na dané mnozstvá konfliktov pre dané hodnoty, a vyberieme to najmensie. Ak je najmensie cislo uz vlozene v sudoku, inkrementujeme premennu j. Pokial by vsak bola hodnota s rovnakym poctom konfliktov, alebo mensim, j-cko nastavime na 1 a pouzijeme ju. Teraz sa inkrementuje aj hodnota i (co je vlastne len index, ktorý nam hovorí, ktore policko premennej zrovna menime)
+* Dojdeme na posledne policko. Vtedy je i > n (pretoze matematici indexuju od jednicky a pri piatich prvkoch ma posledny index i=6, ale pocet n=5. Nic ine v tom nie je). Takze premennu i resetneme a zacneme teda znova od zaciatku.
+* Skôr ci neskôr, ked najdeme spravne riesenie pre sudoku. Hodnota j dosiahne urovne n, pretoze sme preiterovali cez vsetky policka sudoku a ani jedno nezmenili (t.j. premenna j nebola resetnuta).
+Pokiaľ dostanete popísať BestFS, popíšte princíp algoritmu UCS. Je to jedna z dvoch extrémnych variant BestFS. Druhá je Greedy Search. Prečo?
+Pretože BestFS vypočítava hodnotu z funkcie "f(s(k))" z ceny cesty od počiatočného stavu ku rozgenerovanému uzlu "g(s(k))" a z hodnoty heuristickej funkcie (h(sk)). Povedané polopatisticky:
+Keď teda odstranite heuristiku, BestFS degraduje na UCS, ktoré používa len cenu cesty. Keď odstranite cenu cesty a použijete len heuristiku tak vznikne...
+Áno, Greedy Search. Pri Greedy search je cena cesty v celom grafe nulová/konštantná a poćíta sa len s hodnotou heuristickej funkcie. A to je celé. Vlastne len zoberiete UCS, ale namiesto ceny cesty sa pozriete, ako daleko je to podla heuristiky z daneho uzla do ciela.
+Pokiaľ zoberiete cenu cesty od pociatocneho stavu do aktuálneho uzla a pripocítate k tomu, hodnotu heuristickej funkcie daného uzla do ciela, vznikne vám z toho A*. Na rozdiel od Greedy search, A* je taktiez optimálnou a priestorová a ćasová náročnost je velmi závislá na pouźitej heuristickej funkcii. V najlepsom pripade sa bude blizit linearnej funkcii, v najhorsom prípade exponencionálnej (degraduje na UCS).
+1. Vytvor uzol Current a uloz do neho pociatocny stav spolu s jeho ohodnotením (obvykle je ohodnotenie dané len heuristikou)
+Táto metóda sice nie je ani úplná, a ani optimálna, ale má extrémne nízku priestorovú (konštantnú) a ćasovú (lineárnu) náročnosť.
+2. Vytvor uzol Current, vloz do neho pociatocny stav s ohodnotením (zase obvykle len z heuristickej funkcie) a nastav krok výpoctu na nulu (k=0)
+3. Z tabulky zisti aktuálnu teplotu pre daný krok. Ak je teplota nulová, ukonci riesenie a navráť uzol Current (success)
+5. Vypoćítaj rozdiel uzlov Current a Next, a nazvi hodnotu ΔE (ΔE = hodnota(Current)-hodnota(Next)).
+6. Ak je rozdiel väčší ako 0 (ΔE>0), nahrad Current uzlom Next, inak sprav túto zmenu s pravdepodobnostou e^(ΔE/T), kde T je teplota z tabulky