Prohledávání stavového prostoru
Aleš Horák
E-mail: hales@fi.muni.cz
http://nlp.fi.muni.cz/uui/
Obsah:
Prohledávání stavového prostoru
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:
stavový prostor, předpoklady – statické a deterministické prostředí,
diskrétní stavy
počáteční stav problem.init_state
cílová podmínka problem.is_goal(State)
přechodové akce problem.moves(State) → NewStates
implementace a zpracování výstupů problem.moves() určují
prohledávací strategii
Ú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
máme dvě místnosti (L, P)
jeden vysavač (v L nebo P)
v každé místnosti je/není špína
počet stavů je 2 × 22 = 8
akce ={doLeva,doPrava,Vys´avej}
SliDo
Ú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
• cena – g(n) cesty, c(x, a, y) přechodu
(optimální) řešení
A
B
E
N O P
F
Q R S
G
T U V
C
H
W X Y
I
Z Γ ∆
J
Θ Λ Ξ
D
K
Π Σ Φ
L
Ψ Ω ℵ
M
ℶ ‫ג‬ ℸ
Ú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í
A (stav )
např. uzel C:
• stav –
• rodič – A
• akce – doPrava
• hloubka – 1
• cena – 1
řešení – XA
B
E
N O P
F
Q R S
G
T U V
C
H
W X Y
I
Z Γ ∆
J
Θ Λ Ξ
D
K
Π Σ Φ
L
Ψ Ω ℵ
M
ℶ ‫ג‬ ℸ
Úvod do umělé inteligence 2/12 4 / 39
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í, blíže neurčená kolekce
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 .add_node(child)
Úvod do umělé inteligence 2/12 5 / 39
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í, blíže neurčená kolekce
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 .add_node(child)
rekurzivně včetně cesty k řešení:
function RecursiveSearch(problem, path = collection())
if length(path) = 0 then
return ..................RecursiveSearch(problem, collection (problem.init_state))
current_node = get_current_node(path)
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(child)) # cesta rozšířená o child
Úvod do umělé inteligence 2/12 5 / 39
Prohledávání stavového prostoru Prohledávací strategie
Prohledávací strategie – vlastnosti
Porovnání strategií:
ú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 – vlastnosti
Porovnání strategií:
ú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 ∞?)
Úvod do umělé inteligence 2/12 6 / 39
Neinformované prohledávání
Neinformované prohledávání
prohledávání do hloubky
prohledávání do hloubky s limitem
prohledávání do šířky
prohledávání podle ceny
prohledávání s postupným prohlubováním
poznámka – zde názvy metod označují prohledávací strategie, které nejsou
totožné s odpovídajícími obecnými grafovými algoritmy
Ú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)
A
B
D
H I
E
J K
C
F
L M
G
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)
A
B
D
H I
E
J K
C
F
L M
G
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)
A
B
D
H I
E
J K
C
F
L M
G
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)
A
B
D
H I
E
J K
C
F
L M
G
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)
A
B
D
H I
E
J K
C
F
L M
G
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)
A
B
D
H I
E
J K
C
F
L M
G
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)
A
B
D
H I
E
J K
C
F
L M
G
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)
A
B
D
H I
E
J K
C
F
L M
G
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)
A
B
D
H I
E
J K
C
F
L M
G
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
function DepthFirstSearch(problem, path ← [])
if length(path) = 0 then
return DepthFirstSearch(problem, [problem.init_state ])
current_node ← path.last() # poslední prvek cesty
if problem.is_goal(current_node) then
print path # cesta k řešení
foreach child in problem.moves(current_node) do # možné akce
if child /∈ path then # test cyklu v cestě, obecně být nemusí
DepthFirstSearch(problem, path + [child ]) # rozšířená cesta
Ú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(problem, path ← [])
if length(path) = 0 then
return DepthFirstSearch(problem, [problem.init_state ])
current_node ← path.last() # poslední prvek cesty
if problem.is_goal(current_node) then
print path # cesta k řešení
foreach child in problem.moves(current_node) do # možné akce
if child /∈ path then # test cyklu v cestě, obecně být nemusí
DepthFirstSearch(problem, path + [child ]) # rozšířená cesta
ú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(problem, path ← [])
if length(path) = 0 then
return DepthFirstSearch(problem, [problem.init_state ])
current_node ← path.last() # poslední prvek cesty
if problem.is_goal(current_node) then
print path # cesta k řešení
foreach child in problem.moves(current_node) do # možné akce
if child /∈ path then # test cyklu v cestě, obecně být nemusí
DepthFirstSearch(problem, path + [child ]) # rozšířená cesta
úplnost není úplný (nekonečná větev, cykly)
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(problem, path ← [])
if length(path) = 0 then
return DepthFirstSearch(problem, [problem.init_state ])
current_node ← path.last() # poslední prvek cesty
if problem.is_goal(current_node) then
print path # cesta k řešení
foreach child in problem.moves(current_node) do # možné akce
if child /∈ path then # test cyklu v cestě, obecně být nemusí
DepthFirstSearch(problem, path + [child ]) # rozšířená cesta
úplnost není úplný (nekonečná větev, cykly)
optimálnost není optimální
č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(problem, path ← [])
if length(path) = 0 then
return DepthFirstSearch(problem, [problem.init_state ])
current_node ← path.last() # poslední prvek cesty
if problem.is_goal(current_node) then
print path # cesta k řešení
foreach child in problem.moves(current_node) do # možné akce
if child /∈ path then # test cyklu v cestě, obecně být nemusí
DepthFirstSearch(problem, path + [child ]) # rozšířená cesta
úplnost není úplný (nekonečná větev, cykly)
optimálnost není optimální
časová složitost O(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(problem, path ← [])
if length(path) = 0 then
return DepthFirstSearch(problem, [problem.init_state ])
current_node ← path.last() # poslední prvek cesty
if problem.is_goal(current_node) then
print path # cesta k řešení
foreach child in problem.moves(current_node) do # možné akce
if child /∈ path then # test cyklu v cestě, obecně být nemusí
DepthFirstSearch(problem, path + [child ]) # rozšířená cesta
úplnost není úplný (nekonečná větev, cykly)
optimálnost není optimální
časová složitost O(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(problem, path ← [])
if length(path) = 0 then
return DepthFirstSearch(problem, [problem.init_state ])
current_node ← path.last() # poslední prvek cesty
if problem.is_goal(current_node) then
print path # cesta k řešení
foreach child in problem.moves(current_node) do # možné akce
if child /∈ path then # test cyklu v cestě, obecně být nemusí
DepthFirstSearch(problem, path + [child ]) # rozšířená cesta
úplnost není úplný (nekonečná větev, cykly)
optimálnost není optimální
časová složitost O(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 ℓ
Ú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
Řešení nekonečné větve – použití “zarážky” = limit hloubky ℓ
konec má dvě možné interpretace – vyčerpání limitu nebo neexistenci
(dalšího) řešení
Ú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
Řešení nekonečné větve – použití “zarážky” = limit hloubky ℓ
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)
časová složitost O(bℓ)
prostorová složitost O(bℓ)
dobrá volba limitu ℓ – podle znalosti problému
Úvod do umělé inteligence 2/12 10 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou.
(Breadth-first Search, BFS)
A
B
D
H I
E
J K
C
F
L M
G
N O
Úvod do umělé inteligence 2/12 11 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou.
(Breadth-first Search, BFS)
A
B
D
H I
E
J K
C
F
L M
G
N O
Úvod do umělé inteligence 2/12 11 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou.
(Breadth-first Search, BFS)
A
B
D
H I
E
J K
C
F
L M
G
N O
Úvod do umělé inteligence 2/12 11 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou.
(Breadth-first Search, BFS)
A
B
D
H I
E
J K
C
F
L M
G
N O
Úvod do umělé inteligence 2/12 11 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou.
(Breadth-first Search, BFS)
A
B
D
H I
E
J K
C
F
L M
G
N O
Úvod do umělé inteligence 2/12 11 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou.
(Breadth-first Search, BFS)
A
B
D
H I
E
J K
C
F
L M
G
N O
Úvod do umělé inteligence 2/12 11 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou.
(Breadth-first Search, BFS)
A
B
D
H I
E
J K
C
F
L M
G
N O
Úvod do umělé inteligence 2/12 11 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou.
(Breadth-first Search, BFS)
A
B
D
H I
E
J K
C
F
L M
G
N O
Úvod do umělé inteligence 2/12 11 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou.
(Breadth-first Search, BFS)
A
B
D
H I
E
J K
C
F
L M
G
N O
Úvod do umělé inteligence 2/12 11 / 39
Neinformované prohledávání Prohledávání do šířky
Prohledávání do šířky
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 () # aktuální cesta, první v kolekci
current_node ← current_path.last() # aktuální uzel, poslední v cestě
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 # test cyklu v cestě, obecně být nemusí
process ← process + [current_path + [child ] ] # rozšířený seznam cest
Úvod do umělé inteligence 2/12 12 / 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 13 / 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 13 / 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 13 / 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 1 + b + b2 + b3 + . . . + bd + b(bd − 1) = O(bd+1),
exponenciální v d
prostorová složitost
Ú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 je úplný (pro konečné b)
optimálnost je optimální podle délky cesty/není optimální podle
obecné ceny
časová složitost 1 + b + b2 + b3 + . . . + bd + b(bd − 1) = O(bd+1),
exponenciální v d
prostorová složitost O(bd+1) (každý uzel v paměti)
Ú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 je úplný (pro konečné b)
optimálnost je optimální podle délky cesty/není optimální podle
obecné ceny
časová složitost 1 + b + b2 + b3 + . . . + bd + b(bd − 1) = O(bd+1),
exponenciální v d
prostorová složitost O(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 111 100 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í.
SliDo
Úvod do umělé inteligence 2/12 13 / 39
Neinformované prohledávání Prohledávání podle ceny
Prohledávání podle ceny
BFS je optimální pro rovnoměrně ohodnocené stromy × 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 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 × 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 ≥ ϵ a b konečné)
optimálnost je optimální (pro g(n) rostoucí)
časová složitost počet uzlů s g ≤ C∗, O(b1+⌊C∗/ϵ⌋), kde
C∗. . . cena optimálního řešení
prostorová složitost počet uzlů s g ≤ C∗, O(b1+⌊C∗/ϵ⌋)
Úvod do umělé inteligence 2/12 14 / 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)
limit=0
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
Ú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)
limit=1
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
Ú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)
limit=2
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
Ú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)
limit=3
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
A
B
D
H I
E
J K
C
F
L M
G
N O
Ú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 – 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 − 1)b2 + . . . + 1(bd ) = O(bd )
prostorová složitost O(bd)
Ú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 − 1)b2 + . . . + 1(bd ) = O(bd )
prostorová složitost O(bd)
kombinuje výhody BFS a DFS:
• nízké paměťové nároky – lineární
• optimálnost, úplnost
Ú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 − 1)b2 + . . . + 1(bd ) = O(bd )
prostorová složitost O(bd)
kombinuje výhody BFS a DFS:
• nízké paměťové nároky – lineární
• optimálnost, úplnost
zdánlivé plýtvání opakovaným generováním
ALE generuje o jednu úroveň míň, např. pro b = 10, d = 5:
N(IDS) = 50 + 400 + 3 000 + 20 000 + 100 000 = 123 450
N(BFS) = 10 + 100 + 1 000 + 10 000 + 100 000 + 999 990 = 1 111 100
Ú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 − 1)b2 + . . . + 1(bd ) = O(bd )
prostorová složitost O(bd)
kombinuje výhody BFS a DFS:
• nízké paměťové nároky – lineární
• optimálnost, úplnost
zdánlivé plýtvání opakovaným generováním
ALE generuje o jednu úroveň míň, např. pro b = 10, d = 5:
N(IDS) = 50 + 400 + 3 000 + 20 000 + 100 000 = 123 450
N(BFS) = 10 + 100 + 1 000 + 10 000 + 100 000 + 999 990 = 1 111 100
IDS je nejvhodnější neinformovaná strategie pro velké prostory a neznámou
hloubku řešení.
Úvod do umělé inteligence 2/12 16 / 39
Neinformované prohledávání Shrnutí vlastností algoritmů neinformovaného prohledávání
Shrnutí vlastností algoritmů neinformovaného prohledávání
Vlastnost do do hloubky do podle s postupným
hloubky s limitem šířky ceny prohlubováním
úplnost ne ano,
pro ℓ ≥ d
ano∗
ano∗
ano∗
optimálnost ne ne ano∗
ano∗
ano∗
časová složitost O(bm
) O(bℓ
) O(bd+1
) O(b1+⌊C∗
/ϵ⌋
) O(bd
)
prostorová složi-
tost
O(bm) O(bℓ) O(bd+1
) O(b1+⌊C∗
/ϵ⌋
) O(bd)
SliDo
Úvod do umělé inteligence 2/12 17 / 39
Informované prohledávání stavového prostoru
Obsah
1 Prohledávání stavového prostoru
Řešení problému prohledáváním
Prohledávací strategie
2 Neinformované prohledávání
Prohledávání do hloubky
Prohledávání do hloubky s limitem
Prohledávání do šířky
Prohledávání podle ceny
Prohledávání s postupným prohlubováním
3 Informované prohledávání stavového prostoru
Hladové heuristické hledání
Hledání nejlepší cesty – algoritmus A*
4 Jak najít dobrou heuristiku?
Jak najít přípustnou heuristickou funkci?
Určení kvality heuristiky
Úvod do umělé inteligence 2/12 18 / 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 19 / 39
Informované prohledávání stavového prostoru Příklad – cesta na mapě
Příklad – schéma rumunských měst
Města:
Arad
Bukurest
Craiova
Dobreta
Eforie
Fagaras
Giurgiu
Hirsova
Iasi
Lugoj
Mehadia
Neamt
. . .
Cesty:
Arad ↔ Timisoara 118
Arad ↔ Sibiu 140
Arad ↔ Zerind 75
Timisoara ↔ Lugoj 111
Sibiu ↔ Fagaras 99
Sibiu ↔ Rimnicu Vilcea 80
Zerind ↔ Oradea 71
. . . ↔ . . .
Giurgiu ↔ Bukurest 90
Pitesti ↔ Bukurest 101
Fagaras ↔ Bukurest 211
Urziceni ↔ Bukurest 85
Úvod do umělé inteligence 2/12 20 / 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
výběr uzlů pomocí BFS:
Úvod do umělé inteligence 2/12 21 / 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
výběr uzlů pomocí BFS:
Úvod do umělé inteligence 2/12 21 / 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
výběr uzlů pomocí BFS:
Úvod do umělé inteligence 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
Arad 366
Bukurest 0
Craiova 160
Dobreta 242
Eforie 161
Fagaras 176
Giurgiu 77
Hirsova 151
Iasi 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
Arad 366
Bukurest 0
Craiova 160
Dobreta 242
Eforie 161
Fagaras 176
Giurgiu 77
Hirsova 151
Iasi 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í:
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í:
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 (obecný, varianty podle ohodnocovací funkce)
použití ohodnocovací funkce f (n) pro každý uzel – výpočet přínosu
daného uzlu (stavu)
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, h(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) = hvzd_Buk(n), přímá vzdálenost z n do
Bukuresti
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Timisoara Zerind
366
Ú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 Bukurest
ohodnocovací funkce f (n) = h(n) = hvzd_Buk(n), přímá vzdálenost z n do
Bukuresti
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Timisoara Zerind
253 329 374
Ú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 Bukurest
ohodnocovací funkce f (n) = h(n) = hvzd_Buk(n), přímá vzdálenost z n do
Bukuresti
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Timisoara Zerind
366 176 380 193
329 374
Ú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 Bukurest
ohodnocovací funkce f (n) = h(n) = hvzd_Buk(n), přímá vzdálenost z n do
Bukuresti
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Timisoara Zerind
366
253 0
380 193
329
Ú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
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
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 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
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 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
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 obecně není úplný (nekonečný prostor, cykly)
optimálnost není optimální
časová složitost O(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
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 obecně není úplný (nekonečný prostor, cykly)
optimálnost není optimální
časová složitost O(bm), hodně záleží na h
prostorová složitost O(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
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 hvzd_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*
Heuristické hledání A* – příklad
Hledání cesty z města Arad do města Bukurest
ohodnocovací funkce f (n) = g(n) + h(n) = g(n) + hvzd_Buk(n)
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Craiova Pitesti
Bukurest Craiova Rimnicu Vilcea
Sibiu
Timisoara Zerind
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říklad
Hledání cesty z města Arad do města Bukurest
ohodnocovací funkce f (n) = g(n) + h(n) = g(n) + hvzd_Buk(n)
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Craiova Pitesti
Bukurest Craiova Rimnicu Vilcea
Sibiu
Timisoara Zerind
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 Bukurest
ohodnocovací funkce f (n) = g(n) + h(n) = g(n) + hvzd_Buk(n)
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Craiova Pitesti
Bukurest Craiova Rimnicu Vilcea
Sibiu
Timisoara Zerind
646=280+366 415=239+176 671=291+380 413=220+193
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 Bukurest
ohodnocovací funkce f (n) = g(n) + h(n) = g(n) + hvzd_Buk(n)
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Craiova Pitesti
Bukurest Craiova Rimnicu Vilcea
Sibiu
Timisoara Zerind
646=280+366 415=239+176 671=291+380
526=366+160 417=317+100 553=300+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 Bukurest
ohodnocovací funkce f (n) = g(n) + h(n) = g(n) + hvzd_Buk(n)
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Craiova Pitesti
Bukurest Craiova Rimnicu Vilcea
Sibiu
Timisoara Zerind
646=280+366
591=338+253 450=450+0
671=291+380
526=366+160 417=317+100 553=300+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 Bukurest
ohodnocovací funkce f (n) = g(n) + h(n) = g(n) + hvzd_Buk(n)
Arad
Sibiu
Arad Fagaras
Sibiu Bukurest
Oradea Rimnicu Vilcea
Craiova Pitesti
Bukurest Craiova Rimnicu Vilcea
Sibiu
Timisoara Zerind
646=280+366
591=338+253 450=450+0
671=291+380
526=366+160
418=418+0 615=455+60 607=414+193
553=300+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*
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
Ú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 f < C∗] ̸= ∞,
tedy cena ≥ ϵ 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(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 f < C∗] ̸= ∞,
tedy cena ≥ ϵ 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
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 f < C∗] ̸= ∞,
tedy cena ≥ ϵ a b konečné)
optimálnost je optimální
časová složitost O (b∗)d , 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
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 f < C∗] ̸= ∞,
tedy cena ≥ ϵ a b konečné)
optimálnost je optimální
časová složitost O (b∗)d , exponenciální v délce řešení d
b∗ . . . tzv. efektivní faktor větvení , viz dále
prostorová složitost O (b∗)d , 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 je úplný (pokud [počet uzlů s f < C∗] ̸= ∞,
tedy cena ≥ ϵ a b konečné)
optimálnost je optimální
časová složitost O (b∗)d , exponenciální v délce řešení d
b∗ . . . tzv. efektivní faktor větvení , viz dále
prostorová složitost O (b∗)d , 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 G1 (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 G1 (tj. chybně neexpandovaný
uzel ve správném řešení)
Pak
f (G2) = g(G2) protože h(G2) = 0
Ú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 G1 (tj. chybně neexpandovaný
uzel ve správném řešení)
Pak
f (G2) = g(G2) protože h(G2) = 0
> g(G1) 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 G1 (tj. chybně neexpandovaný
uzel ve správném řešení)
Pak
f (G2) = g(G2) protože h(G2) = 0
> g(G1) protože G2 je suboptimální
≥ f (n) protože h je přípustná
Ú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 G1 (tj. chybně neexpandovaný
uzel ve správném řešení)
Pak
f (G2) = g(G2) protože h(G2) = 0
> g(G1) protože G2 je suboptimální
≥ f (n) 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
function A*Search(problem)
process_heap ← [(0, 0, [problem.init_state ])] # prioritní fronta podle f
while length(process_heap) > 0 do
f , g, current_path ← process_heap.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(current_node) do
if child /∈ current_path then # detekce cyklů, obecně být nemusí
process_heap.heap_add( (g+cost+h(child),
g+cost,
current_path + [child ]))
f -hodnota, g-hodnota a cesta k aktuálnímu uzlu
Ú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, y): [pozicedíry, pozicekámen č.1, . . . ]
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)]
function 8p.moves(state):
2 až 4 možnosti – pohyb mezery
cena vždy 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:
h1(n) = počet dlaždiček, které nejsou na svém místě h1(S) = 8
Ú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:
h1(n) = počet dlaždiček, které nejsou na svém místě h1(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 + 31 = 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:
h1(n) = počet dlaždiček, které nejsou na svém místě h1(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 + 31 = 18
h1 i h2 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:
h1(n) = počet dlaždiček, které nejsou na svém místě h1(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 + 31 = 18
h1 i h2 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 h1 nebo h2?
Ú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 h1 nebo h2?
h1 i h2 jsou délky cest pro zjednodušené verze problému Posunovačka:
• při přenášení dlaždice kamkoliv – h1=počet kroků nejkratšího řešení
• při posouvání dlaždice kamkoliv o 1 pole (i na plné) – h2=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 h1 nebo h2?
h1 i h2 jsou délky cest pro zjednodušené verze problému Posunovačka:
• při přenášení dlaždice kamkoliv – h1=počet kroků nejkratšího řešení
• při posouvání dlaždice kamkoliv o 1 pole (i na plné) – h2=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 h1 nebo h2?
h1 i h2 jsou délky cest pro zjednodušené verze problému Posunovačka:
• při přenášení dlaždice kamkoliv – h1=počet kroků nejkratšího řešení
• při posouvání dlaždice kamkoliv o 1 pole (i na plné) – h2=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 ∧ 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 h1 nebo h2?
h1 i h2 jsou délky cest pro zjednodušené verze problému Posunovačka:
• při přenášení dlaždice kamkoliv – h1=počet kroků nejkratšího řešení
• při posouvání dlaždice kamkoliv o 1 pole (i na plné) – h2=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 ∧ 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 h1 nebo h2?
h1 i h2 jsou délky cest pro zjednodušené verze problému Posunovačka:
• při přenášení dlaždice kamkoliv – h1=počet kroků nejkratšího řešení
• při posouvání dlaždice kamkoliv o 1 pole (i na plné) – h2=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 ∧ B je prázdná
(a) dlaždice se může přesunout z A na B ⇔ A sousedí s B . . h2
(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 h1 nebo h2?
h1 i h2 jsou délky cest pro zjednodušené verze problému Posunovačka:
• při přenášení dlaždice kamkoliv – h1=počet kroků nejkratšího řešení
• při posouvání dlaždice kamkoliv o 1 pole (i na plné) – h2=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 ∧ B je prázdná
(a) dlaždice se může přesunout z A na B ⇔ A sousedí s B . . h2
(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 . . . . . . . . . . . . . . . . . . . h1
Ú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 h1 nebo h2?
h1 i h2 jsou délky cest pro zjednodušené verze problému Posunovačka:
• při přenášení dlaždice kamkoliv – h1=počet kroků nejkratšího řešení
• při posouvání dlaždice kamkoliv o 1 pole (i na plné) – h2=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 ∧ B je prázdná
(a) dlaždice se může přesunout z A na B ⇔ A sousedí s B . . h2
(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 . . . . . . . . . . . . . . . . . . . h1
Ú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∗
(h1) A∗
(h2) IDS A∗
(h1) A∗
(h2)
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∗
(h1) A∗
(h2) IDS A∗
(h1) A∗
(h2)
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
h2 dominuje h1 ∀n : h2(n) ≥ h1(n) . . . h2 je lepší (nebo stejná) než h1
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 ti s potřebným časem na zpracování Di (např.: i = 1, . . . , 7)
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
t4/D4 = 20 t5/D5 = 20 t6/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 ti s potřebným časem na zpracování Di (např.: i = 1, . . . , 7)
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
t4/D4 = 20 t5/D5 = 20 t6/D6 = 11 t7/D7 = 11
problém: najít rozvrh práce pro každý procesor s minimalizací celkového
času
0 2 4 13 24 33
CPU1 t3⇐= t6 =⇒⇐= t5 =⇒
CPU2 t2⇐= t7 =⇒ . . . . . . . . . . . .
CPU3 t1⇒⇐= t4 =⇒ . . . . .
Ú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 ti s potřebným časem na zpracování Di (např.: i = 1, . . . , 7)
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
t4/D4 = 20 t5/D5 = 20 t6/D6 = 11 t7/D7 = 11
problém: najít rozvrh práce pro každý procesor s minimalizací celkového
času
0 2 4 13 24 33
CPU1 t3⇐= t6 =⇒⇐= t5 =⇒
CPU2 t2⇐= t7 =⇒ . . . . . . . . . . . .
CPU3 t1⇒⇐= t4 =⇒ . . . . .
0 2 4 13 24 33
CPU1 t3⇐= t6 =⇒⇐= t7 =⇒ . . . . .
CPU2 t2 . ⇐= t5 =⇒ . . . . .
CPU3 t1⇒⇐= t4 =⇒ . . . . .
Ú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ěžící_úlohy, čas_ukončení)
př.: ([(WaitingT1,D1),(WaitingT2,D2),...], [(Task1,F1),(Task2,F2),(Task3,F3)], FinTime)
běžící_úlohy udržujeme setříděné F1 ≤ F2 ≤ F3
Ú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ěžící_úlohy, čas_ukončení)
př.: ([(WaitingT1,D1),(WaitingT2,D2),...], [(Task1,F1),(Task2,F2),(Task3,F3)], FinTime)
běžící_úlohy udržujeme setříděné F1 ≤ F2 ≤ F3
počáteční uzel:
proc. init_state ← ([("t1",4), ("t2",2), ("t3",2), ("t4",20), ("t5",20), ("t6",11),
("t7",11)], [("idle",0), ("idle",0), ("idle",0)], 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ěžící_úlohy, čas_ukončení)
př.: ([(WaitingT1,D1),(WaitingT2,D2),...], [(Task1,F1),(Task2,F2),(Task3,F3)], FinTime)
běžící_úlohy udržujeme setříděné F1 ≤ F2 ≤ F3
počáteční uzel:
proc. init_state ← ([("t1",4), ("t2",2), ("t3",2), ("t4",20), ("t5",20), ("t6",11),
("t7",11)], [("idle",0), ("idle",0), ("idle",0)], 0)
přechodová funkce proc.moves(Stav) → nové stavy s cenami:
function proc.moves (state)
waiting , active , fintime = state
moves ← []
for task in waiting do # kontrolujem přednost v nezařazených a 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.replace_first_and_sort(task)
moves.append((waiting.without(task), newactive, newfintime))
moves ← moves + insert_idle(waiting, 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ěžící_úlohy, čas_ukončení)
př.: ([(WaitingT1,D1),(WaitingT2,D2),...], [(Task1,F1),(Task2,F2),(Task3,F3)], FinTime)
běžící_úlohy udržujeme setříděné F1 ≤ F2 ≤ F3
počáteční uzel:
proc. init_state ← ([("t1",4), ("t2",2), ("t3",2), ("t4",20), ("t5",20), ("t6",11),
("t7",11)], [("idle",0), ("idle",0), ("idle",0)], 0)
přechodová funkce proc.moves(Stav) → nové stavy s cenami:
function proc.moves (state)
waiting , active , fintime = state
moves ← []
for task in waiting do # kontrolujem přednost v nezařazených a 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.replace_first_and_sort(task)
moves.append((waiting.without(task), newactive, newfintime))
moves ← moves + insert_idle(waiting, active, fintime ) # čekání na procesor
return moves
cílová podmínka function proc.is_goal (state)
return length(state [1]) = 0 # žádné nezařazené
Ú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 =
i Di + j Fj
m
skutečný (průběžný) čas výpočtu:
Fin = max(Fj)
Ú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 =
i Di + j Fj
m
skutečný (průběžný) čas výpočtu:
Fin = max(Fj)
heuristická funkce h =
Finall − Fin, když Finall > Fin
0, jinak
function proc.h (state)
tasks , processors , fintime ← state
total_task_time ← Σ_task_time(tasks) # čas potřebný ke zpracování čekajících úloh
total_proc_time ← Σ_proc_time(processors) # aktuálně naplánovaný čas všech procesorů
finall ← (total_task_time + total_proc_time)/length(processors)
if finall > fintime then
return finall - fintime # odhad času pro zpracování čekajících úloh v plánu
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):
[ ([(t1,4),(t2,2),(t3,2),(t4,20),(t5,20),(t6,11),(t7,11)], [(idle,0),(idle,0),(idle,0)], 0),
([(t1,4),(t2,2),(t4,20),(t5,20),(t6,11),(t7,11)], [(idle,0),(idle,0),(t3,2)], 2),
([(t1,4),(t4,20),(t5,20),(t6,11),(t7,11)], [(idle,0),(t2,2),(t3,2)], 2),
([(t4,20),(t5,20),(t6,11),(t7,11)], [(t2,2),(t3,2),(t1,4)], 4),
([(t4,20),(t5,20),(t6,11)], [(t3,2),(t1,4),(t7,13)], 13),
([(t4,20),(t5,20),(t6,11)], [(idle,4),(t1,4),(t7,13)], 13),
([(t5,20),(t6,11)], [(t1,4),(t7,13),(t4,24)], 24),
([(t6,11)], [(t7,13),(t5,24),(t4,24)], 24),
([], [(t6,24),(t5,24),(t4,24)], 24) ]
Úvod do umělé inteligence 2/12 39 / 39