Prohledávání stavového prostoru Aleš Horák E-mail: hales@fi.muni.cz http://nlp.fi.muni.cz/uui/ Obsah: o Prohledávání stavového prostoru 9 Neinformované prohledávání • Informované prohledávání stavového prostoru • Jak najít dobrou heuristiku? Úvod do umělé inteligence 2/12 1/39 Prohledávání stavového prostoru Prohledávání stavového prostoru Řešení problému prohledáváním stavového prostoru: o stavový prostor, předpoklady - statické a deterministické prostředí, diskrétní stavy • počáteční stav problém.init state 9 cílová podmínka problém.is_goal(State) • přechodové akce problém.moves(State) —>► NewStates Úvod do umělé inteligence 2/12 2/39 Prohledávání stavového prostoru Problém agenta Vysavače Problém agenta Vysavače P L 1585 ^0 p vj " L O • máme dvě místnosti (L, P) • jeden vysavač (v L nebo P) • v každé místnosti je/není špína 9 počet stavů je 2 x 22 = 8 • akce = {do Leva, d o Pravá, Vysávej} Úvod do umělé inteligence 2/12 3/39 Prohledávání stavového prostoru Problém agenta Vysavače Problém agenta Vysavače Prohledávací strategie - prohledávací strom: • kořenový uzel • uzel prohledávacího stromu: • (odkaz na) stav • rodičovský uzel • přechodová akce • hloubka uzlu Úvod do umělé inteligence 2/12 4/39 Prohledávání stavového prostoru Problém agenta Vysavače Problém agenta Vysavače Prohledávací strategie - prohledávací strom • kořenový uzel • uzel prohledávacího stromu: • (odkaz na) stav • rodičovský uzel • přechodová akce • hloubka uzlu • cena - g(n) cesty, c(x, a,y) přechodu • (optimální) řešení 9 A (stav např. uzel C: stav - • rodič - A • akce - doPrava • hloubka - 1 • cena - 1 • reseni - X M Úvod do umělé inteligence 2/12 4/39 v Prohledávání stavového prostoru Řešení problému prohledáváním Řešení problému prohledáváním Kostra algoritmu: function Search (problem) process ^— collection (problem. init_state ) # stavy ke zpracování while length (process) > 0 do current-node ^— remove_current_node(process) if problem. is_goal (current-node) then print current-node # řešení foreach child in problem.moves(current-node) do process. aóó-noóe(child) Úvod do umělé inteligence 2/12 5/39 v Prohledávání stavového prostoru Řešení problému prohledáváním Řešení problému prohledáváním Kostra algoritmu: function Search (problem) process ^— collection (problem. init_state ) # stavy ke zpracování while length (process) > 0 do current-node ^— remove_current_node(process) if problem. is_goal (current-node) then print current-node # řešení foreach child in problem.moves(current-node) do process. aóó-noóe(child) rekurzivně včetně cesty k řešení: function RECURSiVESEARCH(prob/e/77, path = collection()) if length(pař/7) = 0 then return RecursiveSearch(prob/e/77, collection (problem. init_state )) current-node = get_current_node(pař/7) if problem. is_goal (current-node) then print path # cesta k řešení foreach child in problem.moves(current-node) do RecursiveSearch(problem, path.with_node(c/7/7c/)) Úvod do umělé inteligence 2/12 5/39 Prohledávání stavového prostoru Prohledávací strategie Prohledávací strategie problem.moves(State) —>► NewStates - definuje prohledávací strategii Úvod do umělé inteligence 2/12 6/39 Prohledávání stavového prostoru Prohledávací strategie Prohledávací strategie problém.moves(State) —>► NewStates - definuje prohledávací strategii Porovnání strategií: o úplnost • optimálnost • časová složitost • prostorová složitost Úvod do umělé inteligence 2/12 6/39 Prohledávání stavového prostoru Prohledávací strategie Prohledávací strategie problem.moves(State) —>► NewStates - definuje prohledávací strategii Porovnání strategií: o úplnost • optimálnost • časová složitost • prostorová složitost složitost závisí na: • b - faktor větvení (branching factor) • d - hloubka cíle (goal depth) • m - maximální hloubka větve/délka cesty (maximum depth/path, může být oo?) Úvod do umělé inteligence 2/12 6/39 Neinformované prohledávání Neinformované prohledávání a prohledávání do hloubky o prohledávání do hloubky s limitem • prohledávání do šířky 9 prohledávání podle ceny • prohledávání s postupným prohlubováním Úvod do umělé inteligence 2/12 7/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky Prohledává se vždy nejlevější a nejhlubší neexpandovaný uzel (Depth-first Search, DFS) © B C d e f; g; h (\: j:• k :l; m :n o Úvod do umělé inteligence 2/12 8/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky Prohledává se vždy nejlevější a nejhlubší neexpandovaný uzel (Depth-first Search, DFS) Úvod do umělé inteligence 2/12 8/39 Neinformované prohledávání Prohledávání do hloubky íh > (ľ; (j) ík I; M (Ň) (Ô: Úvod do umělé inteligence 2/12 8/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hlou bl ky Prohledává se vždy nejlevější a nejhlubší neexpandovaný uzel (Depth-first Search, DFS) Úvod do umělé inteligence 2/12 8/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky Prohledává se vždy nejlevější a nejhlubší neexpandovaný uzel (Depth-first Search, DFS) Úvod do umělé inteligence 2/12 8/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky Prohledává se vždy nejlevější a nejhlubší neexpandovaný uzel (Depth-first Search, DFS) Úvod do umělé inteligence 2/12 8/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky Prohledává se vždy nejlevější a nejhlubší neexpandovaný uzel (Depth-first Search, DFS) Úvod do umělé inteligence 2/12 8/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky Prohledává se vždy nejlevější a nejhlubší neexpandovaný uzel (Depth-first Search, DFS) Úvod do umělé inteligence 2/12 8/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky Prohledává se vždy nejlevější a nejhlubší neexpandovaný uzel (Depth-first Search, DFS) Úvod do umělé inteligence 2/12 8/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky function DEPTHFiRSTSEARCH(prob/e/77, path «— []) if length(pař/7) = 0 then return DepthFirstSearch(prob/e/77, [problem. init_state ]) current-node ^— path, last() # poslední prvek cesty if problem. is_goal (current-node) then print path foreach child in problem.moves(current-node) do if child ^ path then DepthFirstSearch(prob/e/77, path + [c/7/7c/]) Úvod do umělé inteligence 2/12 9/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky function DEPTHFiRSTSEARCH(prob/e/77, path «— []) if length(pař/7) = 0 then return DepthFirstSearch(prob/e/77, [problem. init_state ]) current-node ^— path, last() # poslední prvek cesty if problem. is_goal (current-node) then print path foreach child in problem.moves(current-node) do if child ^ path then DepthFirstSearch(prob/e/77, path + [child]) úplnost optimálnost časová složitost prostorová složitost Úvod do umělé inteligence 2/12 9/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky function DEPTHFiRSTSEARCH(prob/e/77, path «— []) if length(pař/7) = 0 then return DepthFirstSearch(prob/e/77, [problem. init_state ]) current-node ^— path, last() # poslední prvek cesty if problem. is_goal (current-node) then print path foreach child in problem.moves(current-node) do if child ^ path then DepthFirstSearch(prob/e/77, path + [c/7/7c/]) úplnost není úplný (nekonečná větev, cykly) opt/má/ftost časouá složitost prostorová složitost Úvod do umělé inteligence 2/12 9/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky function DEPTHFiRSTSEARCH(prob/e/77, path «— []) if length(pař/7) = 0 then return DepthFirstSearch(prob/e/77, [problem. init_state ]) current-node ^— path, last() # poslední prvek cesty if problem. is_goal (current-node) then print path foreach child in problem.moves(current-node) do if child ^ path then DepthFirstSearch(prob/e/77, path + [c/7/7c/]) úplnost není úplný (nekonečná větev, cykly) optimálnost není optimální časouá složitost prostorová složitost Úvod do umělé inteligence 2/12 9/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky function DEPTHFiRSTSEARCH(prob/e/77, path «— []) if length(pař/7) = 0 then return DepthFirstSearch(prob/e/77, [problem. init_state ]) current-node ^— path, last() # poslední prvek cesty if problem. is_goal (current-node) then print path foreach child in problem.moves(current-node) do if child ^ path then DepthFirstSearch(prob/e/77, path + [c/7/7c/]) úplnost není úplný (nekonečná větev, cykly) optimálnost není optimální časouá složitost 0(bm) prostorová složitost Úvod do umělé inteligence 2/12 9/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky function DEPTHFiRSTSEARCH(prob/e/77, path «— []) if length(pař/7) = 0 then return DepthFirstSearch(prob/e/77, [problem. init_state ]) current-node ^— path, last() # poslední prvek cesty if problem. is_goal (current-node) then print path foreach child in problem.moves(current-node) do if child ^ path then DepthFirstSearch(prob/e/77, path + [c/7/7c/]) úplnost není úplný (nekonečná větev, cykly) optimálnost není optimální časouá složitost 0(bm) prostorová složitost O(bm), lineární Úvod do umělé inteligence 2/12 9/39 Neinformované prohledávání Prohledávání do hloubky Prohledávání do hloubky function DEPTHFiRSTSEARCH(prob/e/77, path «— []) if length(pař/7) = 0 then return DepthFirstSearch(prob/e/77, [problem. init_state ]) current-node ^— path, last() # poslední prvek cesty if problem. is_goal (current-node) then print path foreach child in problem.moves(current-node) do if child ^ path then DepthFirstSearch(prob/e/77, path + [c/7/7c/]) úplnost není úplný (nekonečná větev, cykly) optimálnost není optimální časouá složitost 0(bm) prostorová složitost O(bm), lineární Největší problém - nekonečná větev = nenajde se cíl, program neskončí! Úvod do umělé inteligence 2/12 9/39 Neinformované prohledávání Prohledávání do hloubky s limitem Prohledávání do hloubky s limitem Řešení nekonečné větve - použití "zarážky" = limit hloubky £ function DepthFirstSearchLimited(problem, limit, path «— []) if length(pař/7) = 0 then return DepthFirstSearchLimited (problem, limit, [problem. init_state ]) current-node ^— path, last() # poslední prvek cesty if problem. is_goal (current-node) then print path # cesta k řešení if limit = 0 then return "cutoff" cutofLoccured ^— False foreach child in problem.moves(current-node) do if child ^ path then result ^— DepthFirstSearchLimited(prob/e/77, limit-1, path + [c/7/7c/]) if result = "cutoff" then cutofLoccurred ^— True if cutofLoccurred then return "cutoff" else return "exhausted" Úvod do umělé inteligence 2/12 10 / 39 Neinformované prohledávání Prohledávání do hloubky s limitem Prohledávání do hloubky s limitem konec má dvě možné interpretace - vyčerpání limitu nebo neexistenci (dalšího) řešení Úvod do umělé inteligence 2/12 11 / 39 Neinformované prohledávání Prohledávání do hloubky s limitem Prohledávání do hloubky s limitem konec má dvě možné interpretace - vyčerpání limitu nebo neexistenci (dalšího) řešení Vlastnosti: úplnost není úplný (pro £ < d) optimálnost není optimální (pro £ > d) c a sov a složitost 0(b£) prostorová složitost 0(b£) dobrá volba limitu £ - podle znalosti problému Úvod do umělé inteligence 2/12 11 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS) Úvod do umělé inteligence 2/12 12 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS) Úvod do umělé inteligence 2/12 12 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS) Úvod do umělé inteligence 2/12 12 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS) Úvod do umělé inteligence 2/12 12 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS) Úvod do umělé inteligence 2/12 12 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS) Úvod do umělé inteligence 2/12 12 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS) Úvod do umělé inteligence 2/12 12 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS) Úvod do umělé inteligence 2/12 12 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS) Úvod do umělé inteligence 2/12 12 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do sirky ve frontě (FIFO) udržuje seznam cest function BreadthFirstSearch(problem) process ^— [[problem. init_State ] # seznam cest k aktuálnímu uzlu while length (process) > 0 do current-path ^— process, first () current-node ^— current-path. last () if problem, is.goal (current-node) then print current-path # vypíše cestu k řešení foreach child in problem.moves(current-node) do if child ^ current-path then process ^— process + [current-path + [c/7/7c/] Úvod do umělé inteligence 2/12 13 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do šířky - vlastnosti úplnost optimálnost časová složitost prostorová složitost Úvod do umělé inteligence 2/12 14 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do šířky - vlastnosti úplnost je úplný (pro konečné b) optimálnost časová složitost prostorová složitost Úvod do umělé inteligence 2/12 14 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do šířky - vlastnosti úplnost je úplný (pro konečné b) optimálnost je optimální podle délky cesty/není optimální podle obecné ceny časová složitost prostorová složitost Úvod do umělé inteligence 2/12 14 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do šířky - vlastnosti úplnost je úplný (pro konečné b) optimálnost je optimální podle délky cesty/není optimální podle obecné ceny časová složitost i + b + b2 + b3 + + bd + b^d _ i) = 0(bGf+1), exponenciální v d prostorová složitost Úvod do umělé inteligence 2/12 14 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do šířky - vlastnosti úplnost je úplný (pro konečné b) optimálnost je optimální podle délky cesty/není optimální podle obecné ceny časová složitost i + b + b2 + b3 + + bd + b^d _ i) = 0(bGf+1), exponenciální v d prostorová složitost 0{bd+1) (každý uzel v paměti) Úvod do umělé inteligence 2/12 14 / 39 Neinformované prohledávání Prohledávání do šířky Prohledávání do šířky - vlastnosti úplnost je úplný (pro konečné b) optimálnost je optimální podle délky cesty/není optimální podle obecné ceny časová složitost i + b + b2 + b3 + + bd + b^d _ i) = 0(bGf+1), exponenciální v d prostorová složitost 0{bd+1) (každý uzel v paměti) Největší problém - paměť: Hloubka Uzlů Čas Paměť 2 1100 0.11 sek 1 MB 4 111100 11 sek 106 MB 6 107 19 min 10 GB 8 109 31 hod 1 TB 10 1011 129 dnů 101 TB 12 1013 35 let 10 PB 14 1015 3 523 let 1 EB Ani čas není dobrý —± potřebujeme informované strategie prohledávání. Úvod do umělé inteligence 2/12 14 / 39 Neinformované prohledávání Prohledávání podle ceny Prohledávání podle ceny BFS je optimální pro rovnoměrně ohodnocené stromy x prohledávání podle ceny (Uniform-cost Search) je optimální pro obecné ohodnocení fronta uzlů se udržuje uspořádaná podle ceny cesty Úvod do umělé inteligence 2/12 15 / 39 Neinformované prohledávání Prohledávání podle ceny Prohledávání podle ceny • BFS je optimální pro rovnoměrně ohodnocené stromy x prohledávání podle ceny (Uniform-cost Search) je optimální pro obecné ohodnocení • fronta uzlů se udržuje uspořádaná podle ceny cesty Vlastnosti: úplnost je úplný (pro cena > e a b konečné) optimálnost je optimální (pro cena > e, g(n) roste) ca sov a složitost počet uzlů s g < C* 0(b1+Lc*AJ), kde C*... cena optimálního řešení prostorová složitost počet uzlů s g < C* 0(b1+Lc*/eJ) Úvod do umělé inteligence 2/12 15 / 39 Neinformované prohledávání Prohledávání s postupným prohlubováním Prohledávání s postupným prohlubováním prohledávání do hloubky s postupně se zvyšujícím limitem (Iterative deepening DFS, IDS) imit=0 @ ď. ď H ;i- x k -Ľ: ím; H -a H •G. j. K -Ľ: Ä Kí Úvod do umělé inteligence 2/12 16 / 39 Neinformované prohledávání Prohledávání s postupným prohlubováním Prohledávání s postupným prohlubováním prohledávání do hloubky s postupně se zvyšujícím limitem (Iterative deepening DFS, IDS) I i m it=1 Ď) ;e ■£ & & :b £ £: & :-& £ & ■ H: íl." X K. L. -0 N Q- hj. j: -'j) K V # N O- H. Ú J. 'K L. # N. ^ •b: :e -s & ■ H: 1.: j K # N Q- Úvod do umělé inteligence 2/12 16 / 39 Neinformované prohledávání Prohledávání s postupným prohlubováním Prohledávání s postupným prohlubováním prohledávání do hloubky s postupně se zvyšujícím limitem (Iterative deepening DFS, IDS) I i m it=2 ■h x- -i k :ú- ty -"jsi- :ô;- h x- J.- :k- :l: # :ó:- h x- J: k :l: ty: .;q\ -h- -x- ;j: >C- :l: u- -q- Úvod do umělé inteligence 2/12 16 / 39 Neinformované prohledávání Prohledávání s postupným prohlubováním Prohledávání s postupným prohlubováním prohledávání do hloubky s postupně se zvyšujícím limitem (Iterative deepening DFS, IDS) I i m it=3 Úvod do umělé inteligence 2/12 16 / 39 Neinformované prohledávání Prohledávání s postupným prohlubováním Prohledávání s postupným prohlubováním - vlastnosti úplnost je úplný (pro konečné b) optimálnost je optimální (pro g(n) rovnoměrně neklesající funkce hloubky) časová složitost d(b) + (d - l)b2 + ... + l(bd) = 0(bd) prostorová složitost O(bd) Úvod do umělé inteligence 2/12 17 / 39 Neinformované prohledávání Prohledávání s postupným prohlubováním Prohledávání s postupným prohlubováním - vlastnosti úplnost je úplný (pro konečné b) optimálnost je optimální (pro g(n) rovnoměrně neklesající funkce hloubky) časová složitost d(b) + (d - l)b2 + ... + l(bd) = 0(bd) prostorová složitost O(bd) 9 kombinuje výhody BFS a DFS: • nízké paměťové nároky - lineární optimálnost, úplnost Úvod do umělé inteligence 2/12 17 / 39 Neinformované prohledávání Prohledávání s postupným prohlubováním Prohledávání s postupným prohlubováním - vlastnosti úplnost je úplný (pro konečné b) optimálnost je optimální (pro g(n) rovnoměrně neklesající funkce hloubky) časová složitost d(b) + (d - l)b2 + ... + l(bd) = 0(bd) prostorová složitost 0(bd) 9 kombinuje výhody BFS a DFS: • nízké paměťové nároky - lineární • optimálnost, úplnost 9 zdánlivé plýtvání opakovaným generováním ALE generuje o jednu úroveň míň, např. pro b = 10, d = 5: A/(IDS) = 50 + 400 + 3 000 + 20 000 + 100 000 = 123 450 A/(BFS) = 10 + 100 + 1 000 + 10 000 + 100 000 + 999 990 = 1111100 Úvod do umělé inteligence 2/12 17 / 39 Neinformované prohledávání Prohledávání s postupným prohlubováním Prohledávání s postupným prohlubováním - vlastnosti úplnost je úplný (pro konečné b) optimálnost je optimální (pro g(n) rovnoměrně neklesající funkce hloubky) časová složitost d(b) + (d - l)b2 + ... + l(bd) = 0(bd) prostorová složitost O(bd) 9 kombinuje výhody BFS a DFS: • nízké paměťové nároky - lineární • optimálnost, úplnost 9 zdánlivé plýtvání opakovaným generováním ALE generuje o jednu úroveň míň, např. pro b = 10, d = 5: A/(IDS) = 50 + 400 + 3 000 + 20 000 + 100 000 = 123 450 A/(BFS) = 10 + 100 + 1 000 + 10 000 + 100 000 + 999 990 = 1111100 IDS je nejvhodnější neinformovaná strategie pro velké prostory a neznámou hloubku řešení. Úvod do umělé inteligence 2/12 17 / 39 Neinformované prohledávání Shrnutí vlastností algoritmů neinformovaného prohledávání Shrnutí vlastností algoritmů neinformovaného prohledávání Vlastnost do hloubky do hloubky s limitem do V/VI sirky podle s postupným ceny prohlubováním úplnost ne ano, ano* ano* ano* pro / > d optimálnost ne ne ano* ano* ano* časová složitost 0{bm) 0(b£) 0{bd+1) 0(bi+Lc*AJ) 0(bd) prostorová O(bm) 0(b£) 0{bd+1) 0(bi+Lc*AJ) 0(bd) složitost Úvod do umělé inteligence 2/12 18 / 39 • Řešení problému prohledáváním • Prohledávací strategie i\i ei nTor mova n e pronieuavani • Prohledávání do hloubky • Prohledávání do hloubky s limitem • Prohledávání do šířky • Prohledávání podle ceny 9 Prohledávání s postupným prohlubováním Q Informované prohledávání stavového prostoru • Hladové heuristické hledání • Hledání nejlepší cesty - algoritmus A* • Jak najít přípustnou heuristickou funkci? • Určení kvality heuristiky Úvod do umělé inteligence 2/12 19 / 39 Informované prohledávání stavového prostoru Příklad - cesta na mapě Příklad - cesta na mapě Najdi cestu z města Arad do města Bukurest Úvod do umělé inteligence 2/12 20 / 39 Informované prohledávání stavového prostoru Příklad - cesta na mapě Pří - scf léma rumunských měst Města: Cesty: Arad Arad Timisoara 118 Buku rest Arad Zerind 75 Dobreta Timisoara Lugoj 111 Eforie Sibiu <-> Fagaras 99 Fagaras Sibiu <-> Rimnicu Vilcea 80 Giurgiu Zerind Oradea 71 H i rsova y r . . . lasi Giurgiu <-> Buku rest 90 Lugoj Pitesti <-> Buku rest 101 Mehadia Fagaras Buku rest 211 Neamt Urziceni Buku rest 85 ■i Uvod do umělé i nteligence 2/12 21 , / 39 Informované prohledávání stavového prostoru Příklad - cesta na mapě Příklad - schéma rumunských měst Úvod do umělé inteligence 2/12 22 / 39 Informované prohledávání stavového prostoru Příklad - cesta na mapě Příklad - schéma rumunských měst Oradea Neamt Arad iraiova /BO □ Giurgiu Eforie Arad 366 Bukurešť 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 176 Giurgiu 77 Hirsova 151 lasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 100 Rimnicu Vilcea 193 Sibiu 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374 Úvod do umělé inteligence 2/12 22 / 39 Informované prohledávání stavového prostoru Příklad - cesta na mapě Příklad - schéma rumunských měst Oradea Neamt Arad 11* Eforie Arad 366 Bukurešť 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 176 Giurgiu 77 Hirsova 151 lasi 226 Lugoj 244 Mehadia 241 Neamt 234 Oradea 380 Pitesti 100 Rimnicu Vilcea 193 Sibiu 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374 Úvod do umělé inteligence 2/12 22 / 39 Informované prohledávání stavového prostoru Příklad - cesta na mapě Příklad - cesta na mapě Neinformované prohledávání: o DFS, BFS a varianty • nemá (téměř) žádné informace o pozici cíle - slepé prohledávání • zná pouze: • počáteční/cílový stav • přechodovou funkci Úvod do umělé inteligence 2/12 23 / 39 Informované prohledávání stavového prostoru Příklad - cesta na mapě Příklad - cesta na mapě Neinformované prohledávání: o DFS, BFS a varianty • nemá (téměř) žádné informace o pozici cíle - slepé prohledávání • zná pouze: • počáteční/cílový stav • přechodovou funkci Informované prohledávání: má navíc informaci o (odhadu) blízkosti stavu k cílovému stavu -heuristická funkce (heuristika) Úvod do umělé inteligence 2/12 23 / 39 Informované prohledávání stavového prostoru Heuristické hledání nejlepší cesty Heuristické hledání nejlepší cesty • Best-first Search • použití ohodnocovací funkce f(n) pro každý uzel - výpočet přínosu daného uzlu o udržujeme seznam uzlů uspořádaný (vzestupně) vzhledem k f (n) • použití heuristické funkce h(n) pro každý uzel - odhad vzdálenosti daného uzlu (stavu) od cíle • čím menší h(n), tím blíže k cíli, /7(Goal) = 0. • nejjednodušší varianta - hladové heuristické hledání, Greedy best-first search f(n) = h(n) Úvod do umělé inteligence 2/12 24 / 39 Informované prohledávání stavového prostoru Hladové heuristické hledání - Hladové heuristické hledání příklad Hledání cesty z města Arad do města Bukurest ohodnocovací funkce f{n) — h(n) — /7Vzd_Buk(^)» přímá vzdálenost z n do Bukurešti 366 Úvod do umělé inteligence 2/12 25 / 39 Informované prohledávání stavového prostoru Hladové heuristické hledání Hlad ové heuristické hledání - - příklad Hledání cesty z města Arad do města Bukurest ohodnocovací funkce f{n) — h(n) — /7Vzd_Buk(^)» přímá vzdálenost z n do Bukurešti Úvod do umělé inteligence 2/12 25 / 39 Informované prohledávání stavového prostoru Hladové heuristické hledání Hladové heuristické hledání - příklad Hledání cesty z města Arad do města Bukurešť ohodnocovací funkce f(n) = h(n) — /7vzd_Buk(fl)> P^má vzdálenost z n do Bukurešti CAracD Sibiu^) C]Tjmisoara^> CZerincT^ 329 374 176 CQradea^ CŔ imnicu Vilcea_I> 380 193 Úvod do umělé inteligence 2/12 25 / 39 Informované prohledávání stavového prostoru Hladové heuristické hledání Hladové heuristické hledání - příklad Hledání cesty z města Arad do města Bukurešť ohodnocovací funkce f(n) = h(rí) — /7vzd_Buk(fl)> přímá vzdálenost z n do Bukurešti 253 0 Úvod do umělé inteligence 2/12 25 / 39 Informované prohledávání stavového prostoru Hladové heuristické hledání Hladové heuristické hledání - vlastnosti • expanduje vždy uzel, který se zdá nejblíže k cíli O Cesta nalezená V příkladu (g"(Arad—Sibiu —>► Fagaras —)>Bukurest) = 450) je sice úspěšná, ale není optimální (g"(Arad—} Sibiu—} RimnicuVilcea—} Pitesti—^Bukurest) = 418) • úplnost optimálnost časová složitost prostorová složitost Úvod do umělé inteligence 2/12 26 / 39 Informované prohledávání stavového prostoru Hladové heuristické hledání Hladové heuristické hledání - vlastnosti • expanduje vždy uzel, který se zdá nejblíže k cíli O Cesta nalezená V příkladu (g(Arad^Sibiu^Fagaras^ Bukurešť) = 450) je sice úspěšná, ale není optimální (g"(Arad—} Sibiu—} RimnicuVilcea—} Pitesti—^Bukurest) = 418) • úplnost obecně není úplný (nekonečný prostor, cykly) optimálnost časová složitost prostorová složitost Úvod do umělé inteligence 2/12 26 / 39 Informované prohledávání stavového prostoru Hladové heuristické hledání Hladové heuristické hledání - vlastnosti • expanduje vždy uzel, který se zdá nejblíže k cíli O Cesta nalezená V příkladu (g(Arad^Sibiu^Fagaras^ Bukurešť) = 450) je sice úspěšná, ale není optimální (g"(Arad—} Sibiu—} RimnicuVilcea—} Pitesti—^Bukurest) = 418) • úplnost obecně není úplný (nekonečný prostor, cykly) optimálnost není optimální časová složitost prostorová složitost Úvod do umělé inteligence 2/12 26 / 39 Informované prohledávání stavového prostoru Hladové heuristické hledání Hladové heuristické hledání - vlastnosti • expanduje vždy uzel, který se zdá nejblíže k cíli O Cesta nalezená V příkladu (g(Arad^Sibiu^Fagaras^ Bukurešť) = 450) je sice úspěšná, ale není optimální (g"(Arad—} Sibiu—} RimnicuVilcea—} Pitesti—^Bukurest) = 418) • úplnost obecně není úplný (nekonečný prostor, cykly) optimálnost není optimální časová složitost 0(bm), hodně záleží na h prostorová složitost Úvod do umělé inteligence 2/12 26 / 39 Informované prohledávání stavového prostoru Hladové heuristické hledání Hladové heuristické hledání - vlastnosti • expanduje vždy uzel, který se zdá nejblíže k cíli O Cesta nalezená V příkladu (g(Arad^Sibiu^Fagaras^ Bukurešť) = 450) je sice úspěšná, ale není optimální (g"(Arad—} Sibiu—} RimnicuVilcea—} Pitesti—^Bukurest) = 418) • úplnost obecně není úplný (nekonečný prostor, cykly) optimálnost není optimální časová složitost 0(bm), hodně záleží na h prostorová složitost 0(bm), každý uzel v paměti Úvod do umělé inteligence 2/12 26 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Hledání nejlepší cesty - algoritmus A* • některé zdroje označují tuto variantu jako Best-first Search • ohodnocovací funkce - kombinace g(n) a h(n)\ f(n) = g(n) + h(n) g(n) je cena cesty do n h(n) je odhad ceny cesty z n do cíle f(n) je odhad ceny nejlevnější cesty, která vede přes n Úvod do umělé inteligence 2/12 27 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Hledání nejlepší cesty - algoritmus A* • některé zdroje označují tuto variantu jako Best-first Search • ohodnocovací funkce - kombinace g(n) a h(n)\ f(n) = g(n) + h(n) g(n) je cena cesty do n h(n) je odhad ceny cesty z n do cíle f(n) je odhad ceny nejlevnější cesty, která vede přes n 9 A* algoritmus vyžaduje tzv. přípustnou (admissible) heuristiku: 0 < h(n) < h\n), kde h\n) je skutečná cena cesty z n do cíle tj. odhad se volí vždycky kratší nebo roven ceně libovolné možné cesty do cíle Např. přímá vzdálenost /7vzd_Buk nikdy není delší než (jakákoliv) cesta Úvod do umělé inteligence 2/12 27 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* ické hledání A* - přík :lad Hledání cesty z města Arad do města Bukurešť ohodnocovací funkce f(n) — g(n) + h(n) — g(n) + /7vzd_Buk(^) 366=0+366 Úvod do umělé inteligence 2/12 28 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Heuristické hledání A* - přík ;lad Hledání cesty z města Arad do města Bukurešť ohodnocovací funkce f(n) = g(n) + h(n) — g(n) + /7Vzd_Buk(^) 393=140+253 447=118+329 449=75+374 Úvod do umělé inteligence 2/12 28 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Heuristické hledání A* - příklad Hledání cesty z města Arad do města Bukurešť ohodnocovací funkce f(n) — g(n) + h(n) — g(n) + /7vzd_Buk(^) 646=280+366 415=239+176 671=291+380 413=220+193 S Úvod do umělé inteligence 2/12 28 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Heuristické hledání A* - příklad Hledání cesty z města Arad do města Bukurešť ohodnocovací funkce f(n) — g(n) + h(n) — g(n) + /7vzd_Buk(^) 526=366+160 417=317+100 553=300+253 S Úvod do umělé inteligence 2/12 28 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Heuristické hledání A* - přík ;lad Hledání cesty z města Arad do města Bukurešť ohodnocovací funkce f(rí) — g(n) + h(n) — g(n) + /7Vzd_Buk(^) 591=338+253 450=450+0 526=366+160 417=317+100 553=300+253 Úvod do umělé inteligence 2/12 28 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Heuristické hledání A* - příklad Hledání cesty z města Arad do města Bukurešť ohodnocovací funkce f(n) — g(n) + h(n) — g(n) + /7vzd_Buk(^) 418=418+0 615=455+60 607=414+193 S Úvod do umělé inteligence 2/12 28 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Hledání nejlepší cesty A* - vlastnosti 9 expanduje uzly podle f{rí) — g{rí) + h{rí) A* expanduje všechny uzly s f(n) < C A* expanduje některé uzly s f(n) = C A* neexpanduje žádné uzly s f(n) > C 9 úplnost optimálnost časová složitost prostorová složitost Úvod do umělé inteligence 2/12 29 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Hledání nejlepší cesty A* - vlastnosti expanduje uzly podle f(n) — g(n) + h(n) A* expanduje všechny uzly s f(n) < C A* expanduje některé uzly s f(n) = C* A* neexpanduje žádné uzly s f(n) > C úplnost je úplný (pokud [počet uzlů s ř < C*] 7^ 00, tedy cena > e a b konečné) optimálnost časová složitost prostorová složitost Úvod do umělé inteligence 2/12 29 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Hledání nejlepší cesty A* - vlastnosti • expanduje uzly podle f(rí) — g(rí) + h(n) A* expanduje všechny uzly s f(n) < C A* expanduje některé uzly s f(n) — C A* neexpanduje žádné uzly s f(n) > C úplnost je úplný (pokud [počet uzlů s f < C*] ^ oo, tedy cena > e a b konečné) optimálnost je optimální časová složitost prostorová složitost Úvod do umělé inteligence 2/12 29 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Hledání nejlepší cesty A* - vlastnosti 9 expanduje uzly podle f{rí) — g{rí) + h{rí) A* expanduje všechny uzly s f(n) < C* A* expanduje některé uzly s f(n) = C* A* neexpanduje žádné uzly s f(n) > C* • úplnost je úplný (pokud [počet uzlů s ř < C*] 7^ 00, tedy cena > e a b konečné) optimálnost je optimální časová složitost 0((b*)Qf), exponenciální v délce řešení d b* ... tzv. efektivní faktor větvení, viz dále prostorová složitost Úvod do umělé inteligence 2/12 29 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Hledání nejlepší cesty A* - vlastnosti 9 expanduje uzly podle f{rí) — g{rí) + h{rí) A* expanduje všechny uzly s f (n) < C* A* expanduje některé uzly s f (n) = C* A* neexpanduje žádné uzly s f (n) > C* • úplnost je úplný (pokud [počet uzlů s f < C*] ^ oo, tedy cena > e a b konečné) optimálnost je optimálni časová složitost 0((b*)Qf), exponenciální v délce řešení d b* ... tzv. efektivní faktor větvení, viz dále prostorová složitost 0((b*)Qf), každý uzel v paměti Úvod do umělé inteligence 2/12 29 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Hledání nejlepší cesty A* - vlastnosti expanduje uzly podle f(n) — g(n) + h(n) A* expanduje všechny uzly s f(n) < C A* expanduje některé uzly s f(n) = C A* neexpanduje žádné uzly s f(n) > C úplnost optimálnost časová složitost prostorová složitost je úplný (pokud [počet uzlů s f < C*] ^ oo, tedy cena > e a b konečné) je optimální 0((b*)Qf), exponenciální v délce řešení d b* ... tzv. efektivní faktor větvení, viz dále 0((b*)Gf), každý uzel v paměti Problém s prostorovou složitostí řeší algoritmy jako IDA*, RBFS Úvod do umělé inteligence 2/12 29 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Důkaz optimálnosti algoritmu A* předpokládejme, že byl vygenerován nějaký suboptimální cíl G2 a je uložen ve frontě. • dále nechť n je neexpandovaný uzel na nejkratší cestě k optimálnímu cíli G\ (tj. chybně neexpandovaný uzel ve správném řešení) Úvod do umělé inteligence 2/12 30 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Důkaz optimálnosti algoritmu A* předpokládejme, že byl vygenerován nějaký suboptimální cíl G2 a je uložen ve frontě. • dále nechť n je neexpandovaný uzel na nejkratší cestě k optimálnímu cíli G\ (tj. chybně neexpandovaný uzel ve správném řešení) 1 Pak f(^2) — g(G2) protože h(G2) Start = o Úvod do umělé inteligence 2/12 30 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Důkaz optimálnosti algoritmu A* Start předpokládejme, že byl vygenerován nějaký suboptimální cíl G2 a je uložen ve frontě. • dále nechť n je neexpandovaný uzel na nejkratší cestě k optimálnímu cíli G\ (tj. chybně neexpandovaný uzel ve správném řešení) 1 Pak f(^2) — g(G2) protože ^(£2) = 0 > g(Gi) protože G2 je suboptimální Úvod do umělé inteligence 2/12 30 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Důkaz optimálnosti algoritmu A* předpokládejme, že byl vygenerován nějaký suboptimální cíl G2 a je uložen ve frontě. • dále nechť n je neexpandovaný uzel na nejkratší cestě k optimálnímu cíli G\ (tj. chybně neexpandovaný uzel ve správném řešení) Pak f(G2) = g(G2) > g{ g(Gi) protože G2 je suboptimální > f(rí) protože h je přípustná tedy f(G2) > f(n) A* nikdy nevybere G2 pro expanzi dřív než expanduje n —>► spor s předpokladem, že n je neexpandovaný uzel □ Úvod do umělé inteligence 2/12 30 / 39 Informované prohledávání stavového prostoru Hledání nejlepší cesty - algoritmus A* Hledání nejlepší cesty - algoritmus A* řešení pomocí prioritní fronty f-hodnota, g-hodnota a cesta k aktuálnímu uzlu function a*search(prob/e/77) process-heap ^— [(0, 0, [problem. init_state ])] # prioritní fronta podle f while length(process-heap) > 0 do f, g, current-path ^— process-hea p.heap-pop() # nejmenší f-hodnota current-node ^— current-path. last () if problem, is.goal (current-node) then print current-path # vypíše cestu k řešení foreach child, cost in problem.moves(ovrrent-node) do if child ^ current-path then # detekce cyklů - efektivnější process-heap .heap _add( (g-\-cost-\-h(child), g+cost, current-path + [ child ])) Úvod do umělé inteligence 2/12 31 / 39 Informované prohledávání stavového prostoru Příklad - řešení posunovačky Příklad - řešení posunovačky konfigurace = seznam souřadnic (x, 8p. init_state <- [(2,2), (3,1), (2,3), (2,1), (3,3), (1,2), (3,2), (1,3), (1,1)] function 8p.is_goal(S) return S = [(1,3), (2,3), (3,3), (1,2), (2,2), (3,2), (1,1), (2,1), (3,1)] y): [pozicedíry, pozicekámen čl 7 i ) 2 /-X 4 J \ 5 6 M (•] Úvod do umělé inteligence 2/12 32 / 39 Informované prohledávání stavového prostoru Příklad - řešení posunovačky Příklad - řešení posunovačky konfigurace = seznam souřadnic (x, y): [pozice^y, pozice^men n 3 8p. init_state <- [(2,2), (3,1), (2,3), (2,1), (3,3), (1,2), (3,2), (1,3), (1,1)] function 8p.is_goal(S) return S = [(1,3), (2,3), (3,3), (1,2), (2,2), (3,2), (1,1), (2,1), (3,1)] S= 7 i ) 2 /-X 4 J \ 5 6 m (•] m 2 1 1 V_J 5 l_J 8 v_ _J function 8p.moves(state) # pohyby mezery, cena vždy 1 xb> Yb state.first() # pozice mezery numbers <— state, without-first () # pozice čfsei moves <— [ if x/j > 1 then *nb <- *b -1; moves.append([(xnb, yb)] + numbers.replace((xnjb, yb), (xb, yb))) if xb < 3 then *nb <-xb + 1; moves.append([(xnb, yb)] + numbers.replace((xnjb, yb), (xb, yb))) if yb > 1 then Ynb <- Yb -1; moves.append([(xbl ynb)] + numbers.replace((xb, ynfe), (xb, yfe))) if Yb < 3 then Ynb ^ Yb + 1; mo\/es.append([(xbl ynfe)] + numbers.replace((xb, ynfe), (xbl yb))) return map move in moves to (move, 1) Úvod do umělé inteligence 2/12 32 / 39 Informované prohledávání stavového prostoru Příklad - řešení posunovačky Příklad - řešení posunovačky pokrač. Volba přípustné heuristické funkce h\ Úvod do umělé inteligence 2/12 33 / 39 Informované prohledávání stavového prostoru Příklad - řešení posunovačky Příklad - řešení posunovačky pokrač. Volba přípustné heuristické funkce h\ • hi(n) = počet dlaždiček, které nejsou na svém místě ^i(S) = 8 Úvod do umělé inteligence 2/12 33 / 39 Informované prohledávání stavového prostoru Příklad - řešení posunovačky - řešení posunovačky pokrač. Volba přípustné heuristické funkce h\ 9 hi(n) = počet dlaždiček, které nejsou na svém místě ^i(S) = 8 • h2(n) = součet manhattanských vzdáleností dlaždic od svých správných pozic h2{S) = 37 + 12 + 24 + 25 + 36 + 28 + 23 + 3X = 18 Úvod do umělé inteligence 2/12 33 / 39 Informované prohledávání stavového prostoru Příklad - řešení posunovačky Příklad - řešení posunovačky pokrač. Volba přípustné heuristické funkce h\ • hi(n) = počet dlaždiček, které nejsou na svém místě ^i(S) = 8 • h2(n) = součet manhattanských vzdáleností dlaždic od svých správných pozic h2(S) = 37 + 12 + 24 + 25 + 36 + 28 + 23 + 3, = 18 hi i /72 jsou přípustné . .. h\S) = 26 Úvod do umělé inteligence 2/12 33 / 39 Informované prohledávání stavového prostoru Příklad - řešení posunovačky Příklad - řešení posunovačky pokrač. Volba přípustné heuristické funkce h: • hi(n) = počet dlaždiček, které nejsou na svém místě ^i(S) = 8 • ^(n) = součet manhattanských vzdáleností dlaždic od svých správných pozic h2(S) = 37 + 12 + 24 + 25 + 35 + 28 + 23 + 3X = 18 hi i hi jsou přípustné ... h*(S) = 26 A*Search(8p): [[(2,2), (3,1), (2,3), (2,1), (3,3), (1,2), (3,2), (1,3), (1,1)], [(1,2), (3,1), (2,3), (2,1), (3,3), (2,2), (3,2), (1,3), (1,1)], [(1,2), (2,3), (3,3), (1,3), (2,2), (3,2), (1,1), (2,1), (3,1)], [(1,3), (2,3), (3,3), (1,2), (2,2), (3,2), (1,1), (2,1), (3,1)]] Úvod do umělé inteligence 2/12 33 / 39 Jak najít dobrou heuristiku? Jak najít přípustnou heuristickou funkci? Jak najít přípustnou heuristickou funkci? • je možné najít obecné pravidlo, jak objevit heuristiku hi nebo /?2? Úvod do umělé inteligence 2/12 34 / 39 Jak najít dobrou heuristiku? Jak najít přípustnou heuristickou funkci? Jak najít přípustnou heuristickou funkci? • je možné najít obecné pravidlo, jak objevit heuristiku hi nebo /?2? • A?i i /?2 Jsou délky cest pro zjednodušené verze problému Posunovačka: • při přenášení dlaždice kamkoliv - /?i=počet kroků nejkratšího řešení • při posouvání dlaždice kamkoliv o 1 pole (i na plné) - /?2=počet kroků nejkratšího řešení Úvod do umělé inteligence 2/12 34 / 39 Jak najít dobrou heuristiku? Jak najít přípustnou heuristickou funkci? Jak najít přípustnou heuristickou funkci? • je možné najít obecné pravidlo, jak objevit heuristiku hi nebo /?2? • /?i i /?2 jsou délky cest pro zjednodušené verze problému Posunovačka: • při přenášení dlaždice kamkoliv - /?i=počet kroků nejkratšího řešení • při posouvání dlaždice kamkoliv o 1 pole (i na plné) - /?2=počet kroků nejkratšího řešení • relaxovaný problém - méně omezení na akce než původní problém Cena optimálního řešení relaxovaného problému je přípustná heuristika pro původní problém. optimální řešení původního problému = řešení relaxovaného problému Úvod do umělé inteligence 2/12 34 / 39 Jak najít dobrou heuristiku? Jak najít přípustnou heuristickou funkci? Jak najít přípustnou heuristickou funkci? • je možné najít obecné pravidlo, jak objevit heuristiku hi nebo /?2? • A?i i /?2 Jsou délky cest pro zjednodušené verze problému Posunovačka: • při přenášení dlaždice kamkoliv - /?i=počet kroků nejkratšího řešení • při posouvání dlaždice kamkoliv o 1 pole (i na plné) - /?2=počet kroků nejkratšího řešení • relaxovaný problém - méně omezení na akce než původní problém Cena optimálního řešení relaxovaného problému je přípustná heuristika pro původní problém. optimální řešení původního problému = řešení relaxovaného problému Posunovačka a relaxovaná posunovačka: • dlaždice se může přesunout z A na B <^> A sousedí s B A B je prázdná Úvod do umělé inteligence 2/12 34 / 39 Jak najít dobrou heuristiku? Jak najít přípustnou heuristickou funkci? Jak najít přípustnou heuristickou funkci? • je možné najít obecné pravidlo, jak objevit heuristiku hi nebo /?2? • A?i i /?2 Jsou délky cest pro zjednodušené verze problému Posunovačka: • při přenášení dlaždice kamkoliv - /?i=počet kroků nejkratšího řešení • při posouvání dlaždice kamkoliv o 1 pole (i na plné) - /?2=počet kroků nejkratšího řešení • relaxovaný problém - méně omezení na akce než původní problém Cena optimálního řešení relaxovaného problému je přípustná heuristika pro původní problém. optimální řešení původního problému = řešení relaxovaného problému Posunovačka a relaxovaná posunovačka: • dlaždice se může přesunout z A na B <^> A sousedí s B A B je prázdná (a) dlaždice se může přesunout z A na B <^> A sousedí s B (b) dlaždice se může přesunout z A na B <^> B je prázdná (c) dlaždice se může přesunout z A na B Úvod do umělé inteligence 2/12 34 / 39 Jak najít dobrou heuristiku? Jak najít přípustnou heuristickou funkci? Jak najít přípustnou heuristickou funkci? • je možné najít obecné pravidlo, jak objevit heuristiku hi nebo /?2? • A?i i /?2 Jsou délky cest pro zjednodušené verze problému Posunovačka: • při přenášení dlaždice kamkoliv - /?i=počet kroků nejkratšího řešení • při posouvání dlaždice kamkoliv o 1 pole (i na plné) - /?2=počet kroků nejkratšího řešení • relaxovaný problém - méně omezení na akce než původní problém Cena optimálního řešení relaxovaného problému je přípustná heuristika pro původní problém. optimální řešení původního problému = řešení relaxovaného problému Posunovačka a relaxovaná posunovačka: • dlaždice se může přesunout z A na B <^> A sousedí s B A B je prázdná 9 (a) dlaždice se může přesunout z A na B <^> A sousedí s B .. /?2 (b) dlaždice se může přesunout z A na B <^> B je prázdná (c) dlaždice se může přesunout z A na B Úvod do umělé inteligence 2/12 34 / 39 Jak najít dobrou heuristiku? Jak najít přípustnou heuristickou funkci? Jak najít přípustnou heuristickou funkci? • je možné najít obecné pravidlo, jak objevit heuristiku hi nebo /?2? • A?i i /?2 Jsou délky cest pro zjednodušené verze problému Posunovačka: • při přenášení dlaždice kamkoliv - /?i=počet kroků nejkratšího řešení • při posouvání dlaždice kamkoliv o 1 pole (i na plné) - /?2=počet kroků nejkratšího řešení • relaxovaný problém - méně omezení na akce než původní problém Cena optimálního řešení relaxovaného problému je přípustná heuristika pro původní problém. optimální řešení původního problému = řešení relaxovaného problému Posunovačka a relaxovaná posunovačka: • dlaždice se může přesunout z A na B <^> A sousedí s B A B je prázdná 9 (a) dlaždice se může přesunout z A na B <^> A sousedí s B .. /?2 (b) dlaždice se může přesunout z A na B <^> B je prázdná (c) dlaždice se může přesunout z A na B ................... h\ Úvod do umělé inteligence 2/12 34 / 39 Jak najít dobrou heuristiku? Jak najít přípustnou heuristickou funkci? Jak najít přípustnou heuristickou funkci? • je možné najít obecné pravidlo, jak objevit heuristiku hi nebo /?2? • A?i i /?2 Jsou délky cest pro zjednodušené verze problému Posunovačka: • při přenášení dlaždice kamkoliv - /?i=počet kroků nejkratšího řešení • při posouvání dlaždice kamkoliv o 1 pole (i na plné) - /?2=počet kroků nejkratšího řešení • relaxovaný problém - méně omezení na akce než původní problém Cena optimálního řešení relaxovaného problému je přípustná heuristika pro původní problém. optimální řešení původního problému = řešení relaxovaného problému Posunovačka a relaxovaná posunovačka: • dlaždice se může přesunout z A na B <^> A sousedí s B A B je prázdná 9 (a) dlaždice se může přesunout z A na B <^> A sousedí s B .. /?2 (b) dlaždice se může přesunout z A na B <^> B je prázdná ... Gaschnigova h. (c) dlaždice se může přesunout z A na B ................... h\ Úvod do umělé inteligence 2/12 34 / 39 Jak najít dobrou heuristiku? Určení kvality heuristiky Určení kvality heuristiky efektivní faktor větvení b* — N... počet vygenerovaných uzlů, d... hloubka řešení, idealizovaný strom s N + 1 uzly má faktor větvení b* (reálné číslo): N + 1 = 1 + b* + (b*)2 + • • • + (b*)d např.: když A* najde řešení po 52 uzlech v hloubce 5 ... b* = 1.92 heuristika je tím lepší, čím blíže je b* hodnotě 1. Úvod do umělé inteligence 2/12 35 / 39 Jak najít dobrou heuristiku? Určení kvality heuristiky Určení kvality heuristiky efektivní faktor větvení b* — N... počet vygenerovaných uzlů, d... hloubka řešení, idealizovaný strom s N + 1 uzly má faktor větvení b* (reálné číslo): N + 1 = 1 + b* + (b*)2 + • • • + (b*)d např.: když A* najde řešení po 52 uzlech v hloubce 5 ... b* = 1.92 heuristika je tím lepší, čím blíže je b* hodnotě 1. ^ měření b* na množině testovacích sad - dobrá představa o přínosu heuristiky 8-posunovačka Průměrný počet uzlů Efektivní faktor větvení b* d IDS A*(/7l) A*(/72) IDS A*(/7l) A*(/72) 2 10 6 6 2.45 1.79 1.79 6 680 20 18 2.73 1.34 1.30 10 47127 93 39 2.79 1.38 1.22 12 3644035 227 73 2.78 1.42 1.24 18 — 3056 363 — 1.46 1.26 24 — 39135 1641 — 1.48 1.26 Úvod do umělé inteligence 2/12 35 / 39 Jak najít dobrou heuristiku? Určení kvality heuristiky Určení kvality heuristiky efektivní faktor větvení b* — N... počet vygenerovaných uzlů, d... hloubka řešení, idealizovaný strom s N + 1 uzly má faktor větvení b* (reálné číslo): N + 1 = 1 + b* + (b*)2 + • • • + (b*)d např.: když A* najde řešení po 52 uzlech v hloubce 5 ... b* = 1.92 heuristika je tím lepší, čím blíže je b* hodnotě 1. ^ měření b* na množině testovacích sad - dobrá představa o přínosu heuristiky 8-posunovačka Průměrný počet uzlů Efektivní faktor větvení b* d IDS A*(/7l) A*(/J2) IDS A*(/7l) A*(/72) 2 10 6 6 2.45 1.79 1.79 6 680 20 18 2.73 1.34 1.30 10 47127 93 39 2.79 1.38 1.22 12 3644035 227 73 2.78 1.42 1.24 18 — 3056 363 — 1.46 1.26 24 — 39135 1641 — 1.48 1.26 /72 dominuje h\ (Vn : h2(n) > hi(n)) ... h2 je lepší (nebo stejná) než h\ ve všech případech Úvod do umělé inteligence 2/12 35 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů • úlohy t; s potřebným časem na zpracování D; (např.: / = 1,... ,7) a m procesorů (např.: m = 3) • relace precedence mezi úlohami - které úlohy mohou začít až po skončení dané úlohy t1/D1 = 4 t2/D2 = 2 t3/D3 = 2 ŕ4/D4 = 20 ŕ5/D5 = 20 r6/D6 = 11 t7/D7 = 11 Úvod do umělé inteligence 2/12 36 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů • úlohy t; s potřebným časem na zpracování D; (např.: / = 1,... ,7) a m procesorů (např.: m = 3) • relace precedence mezi úlohami - které úlohy mohou začít až po skončení dané úlohy t1/D1 = 4 t2/D2 = 2 t3/D3 = 2 ŕ4/D4 = 20 ŕ5/D5 = 20 r6/D6 = 11 t7/D7 = 11 • problém: najít rozvrh práce pro každý procesor s minimalizací celkového času 02 4 13 24 33 CPUi ř3 ^= t6 CPU2 CPU3 Úvod do umělé inteligence 2/12 36 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů • úlohy t; s potřebným časem na zpracování D; (např.: / = 1,... ,7) a m procesorů (např.: m = 3) • relace precedence mezi úlohami - které úlohy mohou začít až po skončení dané úlohy ti/Di t2/D: ts/D, U/DA = 20 r5/D5 = 20 r6/D6 = 11 tj/Dj = 11 problém: najít rozvrh práce pro každý procesor s minimalizací celkového času 02 4 13 24 33 02 4 13 24 33 CPUi ř3 ^= t6 CPU2 CPU3 CPUi ř3 " ^= r7 CPU2 ■ CPU3 r4 Úvod do umělé inteligence 2/12 36 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů - pokrač. • stavy: (nezařazené_úlohy, běžícLúlohy, čas_ukončení) př.: ([(WaitingT1,D1)9(WaitingT2,D2)9^]9 [(Task1,F1),(Task2,F2),(Task3,F3)], FinTime) běžícLúlohy udržujeme setříděné F\ < F2 < F3 Úvod do umělé inteligence 2/12 37 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příl kl lad - rozvrf i práce procesorů - pokrač. • stavy: (nezařazené_úlohy, běžícLúlohy, čas_ukončení) př.: ([(WaitingT1,D1),(WaitingT2,D2),...], [(TasklfF1)t(Task2,F2)t(Task3,F3)]t FinTime) běžícLúlohy udržujeme setříděné F\ < F2 < F$ 9 počáteční uzel: proc. init_state <- ([(Mti",4), ("t2,,,2)I (,,r3,\2), (,,t4,,I20)I ("t5",20), (Mt6Ml), . ("ŕ7'\ll)], [("idle",0), ("idle",0), ("idle",0)]f 0) Úvod do umělé inteligence 2/12 37 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů - pokrač. • stavy: (nezařazené_úlohy, běžícLúlohy, čas_ukončení) př.: ([(WaitingT1,D1)9(WaitingT2,D2)9^]9 [(Task1,F1),(Task2,F2),(Task3,F3)], FinTime) běžícLúlohy udržujeme setříděné F\ < F2 < F3 • počáteční uzel: proc. init_state <- ([("ti'\4), ("t2'\2), ("t3'\2), ("t4'\20), ("t5'\20), ("t6'\ll), | _("t7",ll)], [("idle",0), ("idle",0), ("idle",0)], 0)_I • přechodová funkce proc.moves(Stav) —>► nové stavy s cenami: function proc.moves (state) waiting, active, finti me = state moves <— [ for task in waiting do # přednost v čekajících nebo nedokončených if not check_precedence_waiting (task, waiting, without (task)) then next if not check_precedence_active (task, active) then next newactive, newfintime <— active, without-first (). insert_sorted (task) moves.append((i/i/a/t/ng". without (task), newactive, newfintime)) moves <— moves + insert_idle(w/a/t/ng", active, fintime) # čekání na procesor return moves Úvod do umělé inteligence 2/12 37 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů - pokrač. • stavy: (nezařazené_úlohy, běžícLúlohy, čas_ukončení) př.: ([(WaitingT1,D1)9(WaitingT2,D2)9^]9 [(Task1,F1),(Task2,F2),(Task3,F3)], FinTime) běžícLúlohy udržujeme setříděné F\ < F2 < F$ 9 počáteční uzel: proc. init_state ^ ([("ti",4), (,,t2,,,2), ("t3'\2), ("t4'\20), ("t5'\20), ("t6'\ll), ("ir'Ml)], [("idle'\0), ("idle'-.O), ("idle'-.O)], 0) • přechodová funkce proc.moves(Stav) —>► nové stavy s cenami: function proc.moves (state) waiting, active, finti me = state moves <— [ for task in waiting do # přednost v čekajících nebo nedokončených if not check_precedence_waiting (task, waiting, without (task)) then next if not check_precedence_active (task, active) then next newactive, newfintime <— active, without-first (). insert_sorted (task) moves.append((i/i/a/t/ng". without (task), newactive, newfintime)) moves <— moves + insert_idle(w/a/t/ng", active, fintime) # čekání na procesor return moves 9 cílová podmínka function proc.is_goal (state) return length(state [1]) =0 # žádné čekající Úvod do umělé inteligence 2/12 37 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů - pokrač. • heuristika Úvod do umělé inteligence 2/12 38 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů - pokrač. • heuristika optimální (nedosažitelný) čas: Finall E, Di + E; Fj m skutečný (průběžný) čas výpočtu Fin = max(/=ý) Úvod do umělé inteligence 2/12 38 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů - pokrač. • heuristika optimální (nedosažitelný) čas: Finall m skutečný (průběžný) čas výpočtu Fin = max(Fý) heuristická funkce h = Finall — Fin, když Finall > Fin 0, jinak function proc.h (state) tasks, processors, fintíme estate total-task-time <— Z_task_time( tasks) # čas ke zpracování total-proc-time <— Z_proc_tiir\e(processors) # zpracovaný čas finall <— (totaLtask-time + total-proc-time)/length ( processors) if finall > fintime then return finall - fintime return 0 Úvod do umělé inteligence 2/12 38 / 39 Jak najít dobrou heuristiku? Příklad - rozvrh práce procesorů Příklad - rozvrh práce procesorů - pokrač. A*Search(proc): [ ([(ti,4),(t2,2),(t3,2),(t4,20),(t5,20),(t6,ll),(r7,ll)], ([(ti,4),(t2,2),(t4,20),(t5,20),(t6,ll),(t7,ll)], ([(ŕi,4),(t4,20),(t5,20),(ŕ6,ll),(t7,ll)], ([(ŕ4,20),(ŕ5,20),(t6,ll),(ŕ7,ll)], ([(ŕ4,20),(t5,20),(t6,ll)], ([(t4,20),(t5,20),(t6,ll)], ([(t5,20),(t6,ll)], ([(Ml)], (D. [(idle,0),(idle,0),(idle,0)], 0), [(idle,0),(idle,0),(ŕ3,2)], 2), [(idle,0),(ŕ2,2),(ŕ3,2)], 2), [(t2,2),(t3,2),(ti,4)]ľ 4), [(t3,2),(ŕi,4),(t7,13)], 13), [(idle,4),(ti,4),(ŕ7,13)], 13), [(ti,4),(t7,13),(ŕ4,24)], 24), [(t7,13),(t5,24),(t4,24)], 24), [(t6,24),(t5,24),(ŕ4,24)], 24) ] Úvod do umělé inteligence 2/12 39 / 39