Dekompozice problému, AND/OR grafy,
problémy s omezujícími podmínkami
Aleš Horák
E-mail: hales@fi.muni.cz
http://nlp.fi.muni.cz/uui/
Obsah:
Dekompozice a AND/OR grafy
Prohledávání AND/OR grafů
Problémy s omezujícími podmínkami
CLP – Constraint Logic Programming
Úvod do umělé inteligence 3/12 1 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže
máme tři tyče: A, B a C.
na tyči A je (podle velikosti) n
kotoučů.
úkol: přeskládat z A pomocí C
na tyč B (zaps. n(A, B, C)) bez
porušení uspořádání
bit.ly/uuihanoi1 (Tower3 je zde cíl)
SliDo
Úvod do umělé inteligence 3/12 2 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže
máme tři tyče: A, B a C.
na tyči A je (podle velikosti) n
kotoučů.
úkol: přeskládat z A pomocí C
na tyč B (zaps. n(A, B, C)) bez
porušení uspořádání
bit.ly/uuihanoi1 (Tower3 je zde cíl)
SliDo
Můžeme rozložit na fáze:
1.
přeskládat n − 1 kotoučů z A pomocí B na
C.
Úvod do umělé inteligence 3/12 2 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže
máme tři tyče: A, B a C.
na tyči A je (podle velikosti) n
kotoučů.
úkol: přeskládat z A pomocí C
na tyč B (zaps. n(A, B, C)) bez
porušení uspořádání
bit.ly/uuihanoi1 (Tower3 je zde cíl)
SliDo
Můžeme rozložit na fáze:
1.
přeskládat n − 1 kotoučů z A pomocí B na
C.
2. přeložit 1 kotouč z A na B
Úvod do umělé inteligence 3/12 2 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže
máme tři tyče: A, B a C.
na tyči A je (podle velikosti) n
kotoučů.
úkol: přeskládat z A pomocí C
na tyč B (zaps. n(A, B, C)) bez
porušení uspořádání
bit.ly/uuihanoi1 (Tower3 je zde cíl)
SliDo
Můžeme rozložit na fáze:
1.
přeskládat n − 1 kotoučů z A pomocí B na
C.
2. přeložit 1 kotouč z A na B
3. přeskládat n − 1 kotoučů z C pomocí A na B
Úvod do umělé inteligence 3/12 2 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže – pokrač.
schéma celého řešení pro n = 3:
n = 3(A,B,C)
⃝
n − 1 = 2(A,C,B)
n − 2 = 1(A,B,C)
1(A,C,B)
n − 2 = 1(B,C,A)
1(A,B,C) n − 1 = 2(C,B,A)
n − 2 = 1(C,A,B)
1(C,B,A)
n − 2 = 1(A,B,C)
Úvod do umělé inteligence 3/12 3 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže – pokrač.
schéma celého řešení pro n = 3:
n = 3(A,B,C)
⃝
n − 1 = 2(A,C,B)
⃝
n − 2 = 1(A,B,C)
1(A,C,B)
n − 2 = 1(B,C,A)
1(A,B,C) n − 1 = 2(C,B,A)
⃝
n − 2 = 1(C,A,B)
1(C,B,A)
n − 2 = 1(A,B,C)
Úvod do umělé inteligence 3/12 3 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže – pokrač.
schéma celého řešení pro n = 3:
n = 3(A,B,C)
⃝
n − 1 = 2(A,C,B)
⃝
n − 2 = 1(A,B,C)
1(A,C,B)
n − 2 = 1(B,C,A)
1(A,B,C) n − 1 = 2(C,B,A)
⃝
n − 2 = 1(C,A,B)
1(C,B,A)
n − 2 = 1(A,B,C)
Úvod do umělé inteligence 3/12 3 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže – pokrač.
function HanoiTower(n, source, dest, spare)
if n = 1 then
return (source, dest) # pro 1 disk – přesuň ho ze source na dest
else
output = .............HanoiTower(n - 1, source, spare, dest) # přesuň n − 1 disků na spare
output.append((source, dest)) # přesuň zbývající největší disk na dest
# přesuň odložených n − 1 disků na dest
output.append(..............HanoiTower(n - 1, spare, dest, source))
return output
Úvod do umělé inteligence 3/12 4 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže – pokrač.
function HanoiTower(n, source, dest, spare)
if n = 1 then
return (source, dest) # pro 1 disk – přesuň ho ze source na dest
else
output = .............HanoiTower(n - 1, source, spare, dest) # přesuň n − 1 disků na spare
output.append((source, dest)) # přesuň zbývající největší disk na dest
# přesuň odložených n − 1 disků na dest
output.append(..............HanoiTower(n - 1, spare, dest, source))
return output
HanoiTower(3,’a’,’b’,’c’):
[(’a’, ’b’), (’a’, ’c’), (’b’, ’c’), (’a’, ’b’), (’c’, ’a’),
(’c’, ’b’), (’a’, ’b’)]
optimalizace?
Úvod do umělé inteligence 3/12 4 / 35
Dekompozice a AND/OR grafy Příklad – Hanojské věže
Příklad – Hanojské věže – pokrač.
function HanoiTower(n, source, dest, spare)
if n = 1 then
return (source, dest) # pro 1 disk – přesuň ho ze source na dest
else
output = .............HanoiTower(n - 1, source, spare, dest) # přesuň n − 1 disků na spare
output.append((source, dest)) # přesuň zbývající největší disk na dest
# přesuň odložených n − 1 disků na dest
output.append(..............HanoiTower(n - 1, spare, dest, source))
return output
HanoiTower(3,’a’,’b’,’c’):
[(’a’, ’b’), (’a’, ’c’), (’b’, ’c’), (’a’, ’b’), (’c’, ’a’),
(’c’, ’b’), (’a’, ’b’)]
optimalizace – ukládat výsledky prvního rekurzivního volání a uložený výsledek
vždy převzít bez nadbytečné další rekurze
Úvod do umělé inteligence 3/12 4 / 35
Dekompozice a AND/OR grafy Cesta mezi městy pomocí dekompozice
Cesta mezi městy pomocí dekompozice
města:
a, . . . , e . . . ve státě S
l a k . . . hraniční přechody
u, . . . , z . . . ve státě T
hledáme cestu z a do z:
cesta z a do hraničního
přechodu
cesta z hraničního přechodu
do z
S .
c l v
a e u z
b k y
d x T
.
Úvod do umělé inteligence 3/12 5 / 35
Dekompozice a AND/OR grafy Cesta mezi městy pomocí dekompozice
Cesta mezi městy pomocí dekompozice – pokrač.
schéma řešení pomocí rozkladu na podproblémy = AND/OR graf
a→z
via k
⃝
a→k
. . . . . .
k→z
. . . . . .
via l
⃝
a→l
. . . . . .
l→z
. . . . . .
OR uzel
AND uzly
Celkové řešení = podgraf AND/OR grafu, který nevynechává žádného
následníka AND-uzlu.
Úvod do umělé inteligence 3/12 6 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – agent vysavač v nestálém prostředí
problém agenta Vysavače
v nestálém prostředí:
dvě místnosti, jeden vysavač
v každé místnosti je/není špína
počet stavů je 2 × 22
= 8
akce ={doLeva,doPrava,Vys´avej}
nedeterminismus – akce Vysávej může:
• ve špinavé místnosti – vysát místnost a někdy i tu vedlejší
• v čisté místnosti – někdy místnost zašpinit
Úvod do umělé inteligence 3/12 7 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – agent vysavač v nestálém prostředí
problém agenta Vysavače
v nestálém prostředí:
dvě místnosti, jeden vysavač
v každé místnosti je/není špína
počet stavů je 2 × 22
= 8
akce ={doLeva,doPrava,Vys´avej}
nedeterminismus – akce Vysávej může:
• ve špinavé místnosti – vysát místnost a někdy i tu vedlejší
• v čisté místnosti – někdy místnost zašpinit
Strategie/kontingenční plán (prohledávací strom) obsahuje 2 typy uzlů:
deterministické stavy, kde se prostředí nemůže měnit – agent jen volí
další postup, OR
nedeterministické stavy, kde se prostředí náhodně může změnit – agent
musí řešit více možností, AND
mohou nastat cykly, řešení je jen když nedeterminismus není vždy
negativní
Úvod do umělé inteligence 3/12 7 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – agent vysavač v nestálém prostředí pokrač.
⃝
⃝
⃝
Vysávej
Vysávej
doPrava
Vysávej doLeva
doPrava
doLeva
Vysávej
Úvod do umělé inteligence 3/12 8 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – agent vysavač v nestálém prostředí pokrač.
⃝
⃝
⃝
Vysávej
Vysávej
doPrava
Vysávej doLeva
doPrava
doLeva
Vysávej
Úvod do umělé inteligence 3/12 8 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – agent vysavač v nestálém prostředí pokrač.
⃝
⃝
⃝
Vysávej
Vysávej
doPrava
Vysávej doLeva
doPrava
doLeva
Vysávej
Úvod do umělé inteligence 3/12 8 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – výherní strategie
Hra 2 hráčů s perfektními znalostmi, 2 výstupy
výhra
prohra
Výherní strategii je možné formulovat jako AND/OR graf:
počáteční stav P typu já-jsem-na-tahu
moje tahy vedou do stavů Q1, Q2, ... typu soupeř-je-na-tahu
následně soupeřovy tahy vedou do stavů R11, R12, ... já-jsem-na-tahu
P
Q1
R11 R12 . . .
Q2
R21 R22 . . .
Q3
R31 R32 . . .
Úvod do umělé inteligence 3/12 9 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – výherní strategie
Hra 2 hráčů s perfektními znalostmi, 2 výstupy
výhra
prohra
Výherní strategii je možné formulovat jako AND/OR graf:
počáteční stav P typu já-jsem-na-tahu
moje tahy vedou do stavů Q1, Q2, ... typu soupeř-je-na-tahu
následně soupeřovy tahy vedou do stavů R11, R12, ... já-jsem-na-tahu
cíl – stav, který je výhra podle pravidel (prohra je neřešitelný problém)
stav P já-jsem-na-tahu je výherní ⇔ některý z Qi je výherní, OR
stav Qi soupeř-je-na-tahu je výherní ⇔ všechny Rij jsou výherní, AND
výherní strategie = řešení AND/OR grafu
P
Q1
⃝
R11 R12 . . .
Q2
⃝
R21 R22 . . .
Q3
⃝
R31 R32 . . .
Úvod do umělé inteligence 3/12 9 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – výherní strategie
Hra 2 hráčů s perfektními znalostmi, 2 výstupy
výhra
prohra
Výherní strategii je možné formulovat jako AND/OR graf:
počáteční stav P typu já-jsem-na-tahu
moje tahy vedou do stavů Q1, Q2, ... typu soupeř-je-na-tahu
následně soupeřovy tahy vedou do stavů R11, R12, ... já-jsem-na-tahu
cíl – stav, který je výhra podle pravidel (prohra je neřešitelný problém)
stav P já-jsem-na-tahu je výherní ⇔ některý z Qi je výherní, OR
stav Qi soupeř-je-na-tahu je výherní ⇔ všechny Rij jsou výherní, AND
výherní strategie = řešení AND/OR grafu
P
Q1
⃝
R11 R12 . . .
Q2
⃝
R21 R22 . . .
Q3
⃝
R31 R32 . . .
Úvod do umělé inteligence 3/12 9 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – výherní strategie
o o x
x
x o
Úvod do umělé inteligence 3/12 10 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – výherní strategie
o o x
x
x o
o o x
x x
x o
o o x
x x
x o
o o x
x
x x o
Úvod do umělé inteligence 3/12 10 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – výherní strategie
o o x
x
x o
o o x
x x
x o
o o x
o x x
x o
o o x
o x x
x x o
o o x
x x
o x o
o o x
x x x
o x o
o o x
x x
x o
o o x
x o x
x o
o o x
x o x
x x o
o o x
x x
o x o
o o x
x x x
o x o
o o x
x
x x o
o o x
o x
x x o
o o x
o x x
x x o
o o x
o x
x x o
o o x
x o x
x x o
Úvod do umělé inteligence 3/12 10 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – výherní strategie
o o x
x
x o
o o x
x x
x o
o o x
o x x
x o
o o x
o x x
x x o
o o x
x x
o x o
o o x
x x x
o x o
o o x
x x
x o
o o x
x o x
x o
o o x
x o x
x x o
o o x
x x
o x o
o o x
x x x
o x o
o o x
x
x x o
o o x
o x
x x o
o o x
o x x
x x o
o o x
o x
x x o
o o x
x o x
x x o
Úvod do umělé inteligence 3/12 10 / 35
Dekompozice a AND/OR grafy Další příklady
Příklad – výherní strategie
o o x
x
x o
o o x
x x
x o
o o x
o x x
x o
o o x
o x x
x x o
o o x
x x
o x o
o o x
x x x
o x o
o o x
x x
x o
o o x
x o x
x o
o o x
x o x
x x o
o o x
x x
o x o
o o x
x x x
o x o
o o x
x
x x o
o o x
o x
x x o
o o x
o x x
x x o
o o x
o x
x x o
o o x
x o x
x x o
Úvod do umělé inteligence 3/12 10 / 35
Dekompozice a AND/OR grafy AND/OR graf a strom řešení
AND/OR graf a strom řešení
AND/OR graf = graf s 2 typy vnitřních uzlů – AND uzly a OR uzly
AND uzel jako součást řešení vyžaduje průchod všech svých poduzlů
OR uzel se chová jako bežný uzel klasického grafu
Úvod do umělé inteligence 3/12 11 / 35
Dekompozice a AND/OR grafy AND/OR graf a strom řešení
AND/OR graf a strom řešení
AND/OR graf = graf s 2 typy vnitřních uzlů – AND uzly a OR uzly
AND uzel jako součást řešení vyžaduje průchod všech svých poduzlů
OR uzel se chová jako bežný uzel klasického grafu
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
Úvod do umělé inteligence 3/12 11 / 35
Dekompozice a AND/OR grafy AND/OR graf a strom řešení
AND/OR graf a strom řešení
strom řešení T problému P s AND/OR grafem G:
problém P je kořen stromu T
jestliže P je OR uzel grafu G ⇒ právě jeden z jeho následníků se svým
stromem řešení je v T
jestliže P je AND uzel grafu G ⇒ všichni jeho následníci se svými
stromy řešení jsou v T
každý list stromu řešení T je cílovým uzlem v G
Úvod do umělé inteligence 3/12 12 / 35
Dekompozice a AND/OR grafy AND/OR graf a strom řešení
AND/OR graf a strom řešení
strom řešení T problému P s AND/OR grafem G:
problém P je kořen stromu T
jestliže P je OR uzel grafu G ⇒ právě jeden z jeho následníků se svým
stromem řešení je v T
jestliže P je AND uzel grafu G ⇒ všichni jeho následníci se svými
stromy řešení jsou v T
každý list stromu řešení T je cílovým uzlem v G
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
−→
a
b
⃝
d e
h
Úvod do umělé inteligence 3/12 12 / 35
Prohledávání AND/OR grafů Prohledávání AND/OR grafu do hloubky
Obsah
1 Dekompozice a AND/OR grafy
Příklad – Hanojské věže
Další příklady
AND/OR graf a strom řešení
2 Prohledávání AND/OR grafů
Prohledávání AND/OR grafu do hloubky
Heuristické prohledávání AND/OR grafu (AO*)
3 Problémy s omezujícími podmínkami
Varianty CSP podle hodnot proměnných
Varianty omezení
4 CLP – Constraint Logic Programming
Řešení problémů s omezujícími podmínkami
Prohledávání s navracením
Ovlivnění efektivity prohledávání s navracením
Úvod do umělé inteligence 3/12 13 / 35
Prohledávání AND/OR grafů Prohledávání AND/OR grafu do hloubky
Prohledávání AND/OR grafu do hloubky
function AndOrDepthFirstSearch(problem, path ← []) # vrací řešení nebo "failure"
if length(path) = 0 then
return AndOrDepthFirstSearch(problem, [problem.init_state])
current_node ← path.last() # poslední prvek cesty
if problem.is_goal(current_node) then
return [ ] # prázdné (elementární) řešení
else if problem.is_or_state(current_node) then
foreach child in problem.moves(current_node) do
if child ∈ path then next
result = AndOrDepthFirstSearch(problem, path + [child])
if result ̸= "failure" then return [child ] + result
return "failure"
else if problem.is_and_state(current_node) then
results = []
foreach child in problem.moves(current_node) do
if child ∈ path then return "failure"
result = AndOrDepthFirstSearch(problem, path + [child])
if result = "failure" then return "failure"
results .append(result)
return [ child ] + [ results ]
OR-uzel
AND-uzel
Úvod do umělé inteligence 3/12 14 / 35
Prohledávání AND/OR grafů Prohledávání AND/OR grafu do hloubky
Prohledávání AND/OR grafu do hloubky
function AndOrDepthFirstSearch(problem, path ← []) # vrací řešení nebo "failure"
if length(path) = 0 then
return AndOrDepthFirstSearch(problem, [problem.init_state])
current_node ← path.last() # poslední prvek cesty
if problem.is_goal(current_node) then
return [ ] # prázdné (elementární) řešení
else if problem.is_or_state(current_node) then
foreach child in problem.moves(current_node) do
if child ∈ path then next
result = AndOrDepthFirstSearch(problem, path + [child])
if result ̸= "failure" then return [child ] + result
return "failure"
else if problem.is_and_state(current_node) then
results = []
foreach child in problem.moves(current_node) do
if child ∈ path then return "failure"
result = AndOrDepthFirstSearch(problem, path + [child])
if result = "failure" then return "failure"
results .append(result)
return [ child ] + [ results ]
AndOrDepthFirstSearch(problem):
[’a’,’b’,[ [’d’], [’e’,’h’]] ]
OR-uzel
AND-uzel
a
b
⃝
d e
h
Úvod do umělé inteligence 3/12 14 / 35
Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*)
Heuristické prohledávání AND/OR grafu (AO*)
algoritmus AO* má stejné charakteristiky a složitost jako A*
cena přechodové hrany = míra složitosti podproblému:
uzel = and
or
, [(NaslUzel1,Cena1), (NaslUzel2,Cena2), ... , (NaslUzelN,CenaN)]
definujeme cenu uzlu jako cenu optimálního řešení jeho podstromu
pro každý uzel N máme daný odhad jeho ceny:
h(N) = heuristický odhad ceny optimálního podgrafu s kořenem N
pro každý uzel N, jeho následníky N1, . . . , Nb a jeho předchůdce M
definujeme:
F(N) = cena(M, N)+



h(N), pro ještě neexpandovaný uzel N
0, pro cílový uzel (elementární problém)
mini (F(Ni )), pro OR-uzel N
i F(Ni ), pro AND-uzel N
Pro optimální strom řešení S je tedy F(S) právě cena tohoto řešení
Úvod do umělé inteligence 3/12 15 / 35
Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*)
Heuristické prohledávání AND/OR grafu – příklad
setříděný seznam částečně expandovaných stromů řešení =
[Nevyřešený1, Nevyřešený2, . . . , Vyřešený1, . . . ]
FNevyřešený1
≤ FNevyřešený2
≤ . . .
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
1
1 1
6
3
2
3
1
2
předp. ∀N : h(N) = 0
Úvod do umělé inteligence 3/12 16 / 35
Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*)
Heuristické prohledávání AND/OR grafu – příklad
setříděný seznam částečně expandovaných stromů řešení =
[Nevyřešený1, Nevyřešený2, . . . , Vyřešený1, . . . ]
FNevyřešený1
≤ FNevyřešený2
≤ . . .
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
1
1 1
6
3
2
3
1
2
předp. ∀N : h(N) = 0
a
b
d e
h
c
f
i
g
1 3
1
1 3
Úvod do umělé inteligence 3/12 16 / 35
Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*)
Heuristické prohledávání AND/OR grafu – příklad
setříděný seznam částečně expandovaných stromů řešení =
[Nevyřešený1, Nevyřešený2, . . . , Vyřešený1, . . . ]
FNevyřešený1
≤ FNevyřešený2
≤ . . .
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
1
1 1
6
3
2
3
1
2
předp. ∀N : h(N) = 0
a
b
⃝
d e
h
c
f
i
g
1
1 1
3
3
3
1 1
3
Úvod do umělé inteligence 3/12 16 / 35
Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*)
Heuristické prohledávání AND/OR grafu – příklad
setříděný seznam částečně expandovaných stromů řešení =
[Nevyřešený1, Nevyřešený2, . . . , Vyřešený1, . . . ]
FNevyřešený1
≤ FNevyřešený2
≤ . . .
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
1
1 1
6
3
2
3
1
2
předp. ∀N : h(N) = 0
a
b
⃝
d e
h
c
f
i
g
1
1 1
6
3
3
9
1 7
6
3
Úvod do umělé inteligence 3/12 16 / 35
Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*)
Heuristické prohledávání AND/OR grafu – příklad
setříděný seznam částečně expandovaných stromů řešení =
[Nevyřešený1, Nevyřešený2, . . . , Vyřešený1, . . . ]
FNevyřešený1
≤ FNevyřešený2
≤ . . .
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
1
1 1
6
3
2
3
1
2
předp. ∀N : h(N) = 0
a
b
⃝
d e
h
c
⃝
f
i
g
1
1 1
6
3
2 1
6
9
1 7
6
6
2 1
Úvod do umělé inteligence 3/12 16 / 35
Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*)
Heuristické prohledávání AND/OR grafu – příklad
setříděný seznam částečně expandovaných stromů řešení =
[Nevyřešený1, Nevyřešený2, . . . , Vyřešený1, . . . ]
FNevyřešený1
≤ FNevyřešený2
≤ . . .
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
1
1 1
6
3
2
3
1
2
předp. ∀N : h(N) = 0
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
1
1 1
6
3
2
3
1
9
2
9
1 7
6/2
11
7
3
1
Úvod do umělé inteligence 3/12 16 / 35
Prohledávání AND/OR grafů Heuristické prohledávání AND/OR grafu (AO*)
Heuristické prohledávání AND/OR grafu – příklad
setříděný seznam částečně expandovaných stromů řešení =
[Nevyřešený1, Nevyřešený2, . . . , Vyřešený1, . . . ]
FNevyřešený1
≤ FNevyřešený2
≤ . . .
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
1
1 1
6
3
2
3
1
2
předp. ∀N : h(N) = 0
a
b
⃝
d e
h
c
⃝
f
⃝
i
g
1
1 1
6
3
2
3
1
9
2
9
1 7
6/2
11
7
3
1
Úvod do umělé inteligence 3/12 16 / 35
Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním
Cesta mezi městy heuristickým AND/OR hledáním
cesta mezi sousedícími městy Mesto1 a Mesto2 – ohodnocené hrany
problem.moves(Mesto1) → [(Mesto2,Vzdal2), ...]
klíčové postavení města Mesto3 na cestě z Mesto1 do Mesto2 – funkce
problem.key(Mesto1, Mesto2) → [Mesto3, ...].
S .
c l v
a e u z
b k y
d x T
.
3
2
2
1 2
3
2
4 23
1
3 3
5 31
2
Úvod do umělé inteligence 3/12 17 / 35
Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním
Cesta mezi městy heuristickým AND/OR hledáním
vlastní hledání cesty:
1. ∃ Y1, Y2,. . . klíčové body mezi městy A a Z.
Hledej jednu z cest:
• cestu z A do Z přes Y1
• cestu z A do Z přes Y2
• . . .
2. Není-li mezi městy A a Z klíčové město ⇒ hledej
souseda Y města A takového, že existuje cesta z Y
do Z.
Úvod do umělé inteligence 3/12 18 / 35
Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním
Cesta mezi městy heuristickým AND/OR hledáním
Konstrukce příslušného AND/OR grafu:
“manuální” výpis všech uzlů:
# kterákoliv cesta přes klíčové město
’a-z’ → (’or’, [(’a-z via k’, 0), (’a-z via l’, 0)])
’a-v’ → (’or’, [(’a-v via k’, 0), (’a-v via l’, 0)])
...
# kterákoliv cesta přes sousední města
’a-l’ → (’or’, [(’c-l’, 3), (’b-l’, 2)])
’b-l’ → (’or’, [(’e-l’, 3), (’d-l’, 2)])
...
# cesta do klíčového města a z klíčového města
’a-z via l’ → (’and’, [(’a-l’, 0), (’l-z’, 0)])
’a-v via l’ → (’and’, [(’a-l’, 0), (’l-v’, 0)])
...
# cíle – elementární problémy
goal(’a-a’); goal(’b-b’); ...
Úvod do umělé inteligence 3/12 19 / 35
Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním
Cesta mezi městy heuristickým AND/OR hledáním
Konstrukce příslušného AND/OR grafu:
“pravidlová” definice grafu:
# kterákoliv cesta přes klíčové město ’a-z’ → (’or’, [(’a-z via k’, 0), (’a-z via l’, 0)]) ...
for X ∈ problem.cities do for Z ∈ problem.cities do
nodes = []; for Y ∈ problem.key(X, Z) do nodes.append((’X-Z via Y ’, 0))
if length(nodes)>0 then problem.add(’X-Z’ → (’or’, nodes))
# kterákoliv cesta přes sousední města ’a-l’ → (’or’, [(’c-l’, 3), (’b-l’, 2)]) ...
for X ∈ problem.cities do for Z ∈ problem.cities do
nodes = []; for Y, V ∈ problem.moves(X) do nodes.append((’Y -Z’, V))
if length(nodes)>0 then problem.add(’X-Z’ → (’or’, nodes))
# cesta do a z klíčového města ’a-z via l’ → (’and’, [(’a-l’, 0), (’l-z’, 0)]) ...
for X ∈ problem.cities do for Z ∈ problem.cities do
for Y ∈ problem.key(X, Z) do
problem.add(’X-Z via Y ’ → (’and’, [(’X-Y ’,0), (’Y -Z’,0)]))
# cíle – elementární problémy goal(’a-a’); goal(’b-b’); ...
for X ∈ problem.cities do
problem.add(goal(’X-X’))
Úvod do umělé inteligence 3/12 19 / 35
Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním
Cesta mezi městy heuristickým AND/OR
hledáním – pokrač.
heuristika h( X − Z | X − Z via Y ) = vzdušná vzdálenost
Když ∀n : h(n) ≤ h∗(n), kde h∗ je minimální cena řešení uzlu n ⇒
najdeme vždy optimální řešení
Úvod do umělé inteligence 3/12 20 / 35
Prohledávání AND/OR grafů Cesta mezi městy heuristickým AND/OR hledáním
Cesta mezi městy heuristickým AND/OR
hledáním – pokrač.
heuristika h( X − Z | X − Z via Y ) = vzdušná vzdálenost
Když ∀n : h(n) ≤ h∗(n), kde h∗ je minimální cena řešení uzlu n ⇒
najdeme vždy optimální řešení
S .
c l v
a e u z
b k y
d x T
.
3
2
2
1 2
3
2
4 23
1
3 3
5 31
2
AO∗Search(’a-z’):
[(’a-z’,11),
(’a-z via l’,11),
[[(’l-z’,6),
(’u-z’,6),
(’y-z’,5),
(’z-z’,3)],
[(’a-l’,5),
(’c-l’,5),
(’l-l’,2)]]]
AND-uzel
Úvod do umělé inteligence 3/12 20 / 35
Problémy s omezujícími podmínkami
Obsah
1 Dekompozice a AND/OR grafy
Příklad – Hanojské věže
Další příklady
AND/OR graf a strom řešení
2 Prohledávání AND/OR grafů
Prohledávání AND/OR grafu do hloubky
Heuristické prohledávání AND/OR grafu (AO*)
3 Problémy s omezujícími podmínkami
Varianty CSP podle hodnot proměnných
Varianty omezení
4 CLP – Constraint Logic Programming
Řešení problémů s omezujícími podmínkami
Prohledávání s navracením
Ovlivnění efektivity prohledávání s navracením
Úvod do umělé inteligence 3/12 21 / 35
Problémy s omezujícími podmínkami
Problémy s omezujícími podmínkami
standardní problém řešený prohledáváním stavového prostoru → stav je
“černá skříňka” – pouze cílová podmínka a přechodová funkce
Úvod do umělé inteligence 3/12 22 / 35
Problémy s omezujícími podmínkami
Problémy s omezujícími podmínkami
standardní problém řešený prohledáváním stavového prostoru → stav je
“černá skříňka” – pouze cílová podmínka a přechodová funkce
problém s omezujícími podmínkami, Constraint Satisfaction
Problem, CSP:
• n-tice proměnných X1, X2, . . . , Xn s hodnotami z domén D1, D2, . . . , Dn,
Di ̸= ∅
• množina omezení C1, C2, . . . , Cm nad proměnnými Xi
Úvod do umělé inteligence 3/12 22 / 35
Problémy s omezujícími podmínkami
Problémy s omezujícími podmínkami
standardní problém řešený prohledáváním stavového prostoru → stav je
“černá skříňka” – pouze cílová podmínka a přechodová funkce
problém s omezujícími podmínkami, Constraint Satisfaction
Problem, CSP:
• n-tice proměnných X1, X2, . . . , Xn s hodnotami z domén D1, D2, . . . , Dn,
Di ̸= ∅
• množina omezení C1, C2, . . . , Cm nad proměnnými Xi
• stav = přiřazení hodnot proměnným {Xi = vi , Xj = vj , . . .}
– konzistentní přiřazení neporušuje žádné z omezení Ci
– úplné přiřazení zmiňuje každou proměnnou Xi
• řešení = úplné konzistentní přiřazení hodnot proměnným
někdy je ještě potřeba maximalizovat cílovou funkci
Úvod do umělé inteligence 3/12 22 / 35
Problémy s omezujícími podmínkami
Problémy s omezujícími podmínkami
standardní problém řešený prohledáváním stavového prostoru → stav je
“černá skříňka” – pouze cílová podmínka a přechodová funkce
problém s omezujícími podmínkami, Constraint Satisfaction
Problem, CSP:
• n-tice proměnných X1, X2, . . . , Xn s hodnotami z domén D1, D2, . . . , Dn,
Di ̸= ∅
• množina omezení C1, C2, . . . , Cm nad proměnnými Xi
• stav = přiřazení hodnot proměnným {Xi = vi , Xj = vj , . . .}
– konzistentní přiřazení neporušuje žádné z omezení Ci
– úplné přiřazení zmiňuje každou proměnnou Xi
• řešení = úplné konzistentní přiřazení hodnot proměnným
někdy je ještě potřeba maximalizovat cílovou funkci
výhody:
• jednoduchý formální jazyk pro specifikaci problému
• může využívat obecné heuristiky (ne jen specifické pro daný problém)
Úvod do umělé inteligence 3/12 22 / 35
Problémy s omezujícími podmínkami Příklad – obarvení mapy
Příklad – obarvení mapy
Western
Australia
Northern
Territory
South
Australia
Queensland
New South Wales
Victoria
Tasmania
Proměnné WA, NT, Q, NSW , V , SA, T
Domény Di = {červená, zelená, modrá}
Omezení – sousedící oblasti musí mít různou barvu
tj. pro každé dvě sousedící: WA ̸= NT nebo
(WA, NT) ∈ {(červená, zelená), (červená, modrá), (zelená, modrá), . . .}
Úvod do umělé inteligence 3/12 23 / 35
Problémy s omezujícími podmínkami Příklad – obarvení mapy
Příklad – obarvení mapy – pokrač.
Western
Australia
Northern
Territory
South
Australia
Queensland
New South Wales
Victoria
Tasmania
Řešení – konzistentní přiřazení všem proměnným:
{WA = červená, NT = zelená, Q = červená, NSW = zelená, V = červená,
SA = modrá, T = zelená}
SliDo
Úvod do umělé inteligence 3/12 24 / 35
Problémy s omezujícími podmínkami Varianty CSP podle hodnot proměnných
Varianty CSP podle hodnot proměnných
diskrétní hodnoty proměnných – spočetně mnoho jednotlivých hodnot
• konečné domény
– např. Booleovské (včetně NP-úplných problémů splnitelnosti)
– výčtové
• nekonečné domény – čísla, řetězce, . . .
– např. rozvrh prací – proměnné = počáteční/koncový den každého úkolu
– vyžaduje jazyk omezení, např. StartJob1 + 5 ≤ StartJob3
– číselné lineární problémy jsou řešitelné, nelineární obecné řešení nemají
spojité hodnoty proměnných
Úvod do umělé inteligence 3/12 25 / 35
Problémy s omezujícími podmínkami Varianty CSP podle hodnot proměnných
Varianty CSP podle hodnot proměnných
diskrétní hodnoty proměnných – spočetně mnoho jednotlivých hodnot
• konečné domény
– např. Booleovské (včetně NP-úplných problémů splnitelnosti)
– výčtové
• nekonečné domény – čísla, řetězce, . . .
– např. rozvrh prací – proměnné = počáteční/koncový den každého úkolu
– vyžaduje jazyk omezení, např. StartJob1 + 5 ≤ StartJob3
– číselné lineární problémy jsou řešitelné, nelineární obecné řešení nemají
spojité hodnoty proměnných
• časté u reálných problémů
• např. počáteční/koncový čas měření na Webbově teleskopu (závisí na
astronomických, precedenčních a technických omezeních)
• lineární omezení řešené pomocí Lineárního programování (omezení =
lineární (ne)rovnice tvořící konvexní oblast) → jsou řešitelné
v polynomiálním čase
Úvod do umělé inteligence 3/12 25 / 35
Problémy s omezujícími podmínkami Varianty omezení
Varianty omezení
unární omezení zahrnuje jedinou proměnnou
např. SA ̸= zelená
binární omezení zahrnují dvě proměnné
např. SA ̸= WA
omezení vyššího řádu zahrnují 3 a více proměnných
např. kryptoaritmetické omezení na sloupce u algebrogramu
preferenční omezení (soft constraints), např. ‘červená je lepší než zelená’
možno reprezentovat pomocí ceny přiřazení u konkrétní hodnoty a
konkrétní proměnné → hledá se optimalizované řešení vzhledem k ceně
Úvod do umělé inteligence 3/12 26 / 35
Problémy s omezujícími podmínkami Graf omezení
Graf omezení
Pro binární omezení: uzly = proměnné, hrany = reprezentují jednotlivá
omezení
Pro n-ární omezení: hypergraf: uzly = proměnné, uzly = omezení,
hrany = použití proměnné v omezení
Western
Australia
Northern
Territory
South
Australia
Queensland
New South Wales
Victoria
Tasmania
Victoria
WA
NT
SA
Q
NSW
V
T
Algoritmy pro řešení CSP využívají této grafové reprezentace omezení
Úvod do umělé inteligence 3/12 27 / 35
CLP – Constraint Logic Programming
CLP – Constraint Logic Programming
X in 1..5 , Y in 2..8 , X+Y #= T:
X in 1..5
Y in 2..8
T in 3..13
Úvod do umělé inteligence 3/12 28 / 35
CLP – Constraint Logic Programming
CLP – Constraint Logic Programming
X in 1..5 , Y in 2..8 , X+Y #= T:
X in 1..5
Y in 2..8
T in 3..13
?X in +Min..+Max
?X in +Domain . . .
A in 1..3 \/8..15 \/5..9 \/100.
+VarList ins +Domain
fd_dom(?Var,?Domain) zjištění domény proměnné
Úvod do umělé inteligence 3/12 28 / 35
CLP – Constraint Logic Programming
CLP – Constraint Logic Programming
X in 1..5 , Y in 2..8 , X+Y #= T:
X in 1..5
Y in 2..8
T in 3..13
?X in +Min..+Max
?X in +Domain . . .
A in 1..3 \/8..15 \/5..9 \/100.
+VarList ins +Domain
fd_dom(?Var,?Domain) zjištění domény proměnné
aritmetická omezení . . .
– rel. operátory #=, #\=, #<, #=<, #>, #>=
– sum(Variables,RelOp,Suma)
výroková omezení . . .
#\ negace, #/\ konjunkce, #\/ disjunkce, #<==>
ekvivalence
kombinatorická omezení . . .
all_distinct(List), global_cardinality(List, KeyCounts)
Úvod do umělé inteligence 3/12 28 / 35
CLP – Constraint Logic Programming
CLP – Constraint Logic Programming
X in 1..5 , Y in 2..8 , X+Y #= T:
X in 1..5
Y in 2..8
T in 3..13
X in 1..5 , Y in 2..8 , X+Y #= T, labeling([X,Y,T]):
T = 3
X = 1
Y = 2
?X in +Min..+Max
?X in +Domain . . .
A in 1..3 \/8..15 \/5..9 \/100.
+VarList ins +Domain
fd_dom(?Var,?Domain) zjištění domény proměnné
aritmetická omezení . . .
– rel. operátory #=, #\=, #<, #=<, #>, #>=
– sum(Variables,RelOp,Suma)
výroková omezení . . .
#\ negace, #/\ konjunkce, #\/ disjunkce, #<==>
ekvivalence
kombinatorická omezení . . .
all_distinct(List), global_cardinality(List, KeyCounts)
hledá hodnoty podle omezení
Úvod do umělé inteligence 3/12 28 / 35
CLP – Constraint Logic Programming Příklad – algebrogram
Příklad – algebrogram
S E N D
+ M O R E
----------
M O N E Y
Úvod do umělé inteligence 3/12 29 / 35
CLP – Constraint Logic Programming Příklad – algebrogram
Příklad – algebrogram
S E N D
+ M O R E
----------
M O N E Y
Proměnné
Domény
Omezení
Úvod do umělé inteligence 3/12 29 / 35
CLP – Constraint Logic Programming Příklad – algebrogram
Příklad – algebrogram
S E N D
+ M O R E
----------
M O N E Y
Proměnné {S, E, N, D, M, O, R, Y }
Domény
Omezení
Úvod do umělé inteligence 3/12 29 / 35
CLP – Constraint Logic Programming Příklad – algebrogram
Příklad – algebrogram
S E N D
+ M O R E
----------
M O N E Y
Proměnné {S, E, N, D, M, O, R, Y }
Domény Di = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Omezení
Úvod do umělé inteligence 3/12 29 / 35
CLP – Constraint Logic Programming Příklad – algebrogram
Příklad – algebrogram
S E N D
+ M O R E
----------
M O N E Y
Proměnné {S, E, N, D, M, O, R, Y }
Domény Di = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Omezení – S > 0, M > 0
– S ̸= E ̸= N ̸= D ̸= M ̸= O ̸= R ̸= Y
– 1000 ∗ S + 100 ∗ E + 10 ∗ N + D + 1000 ∗ M +
100 ∗ O + 10 ∗ R + E =
10000 ∗ M + 1000 ∗ O + 100 ∗ N + 10 ∗ E + Y
Úvod do umělé inteligence 3/12 29 / 35
CLP – Constraint Logic Programming Příklad – algebrogram
Příklad – algebrogram
S E N D
+ M O R E
----------
M O N E Y
Proměnné {S, E, N, D, M, O, R, Y }
Domény Di = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Omezení – S > 0, M > 0
– S ̸= E ̸= N ̸= D ̸= M ̸= O ̸= R ̸= Y
– 1000 ∗ S + 100 ∗ E + 10 ∗ N + D + 1000 ∗ M +
100 ∗ O + 10 ∗ R + E =
10000 ∗ M + 1000 ∗ O + 100 ∗ N + 10 ∗ E + Y
function MoreMoney([S,E,N,D,M,O,R,Y])
[S,E,N,D,M,O,R,Y] ins 0..9
S #> 0; M #> 0
all_distinct ([S,E,N,D,M,O,R,Y])
1000∗S + 100∗E + 10∗N + D + 1000∗M + 100∗O + 10∗R + E
#= 10000∗M + 1000∗O + 100∗N + 10∗E + Y
labeling([S,E,N,D,M,O,R,Y])
Úvod do umělé inteligence 3/12 29 / 35
CLP – Constraint Logic Programming Příklad – algebrogram
Příklad – algebrogram
S E N D
+ M O R E
----------
M O N E Y
Proměnné {S, E, N, D, M, O, R, Y }
Domény Di = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Omezení – S > 0, M > 0
– S ̸= E ̸= N ̸= D ̸= M ̸= O ̸= R ̸= Y
– 1000 ∗ S + 100 ∗ E + 10 ∗ N + D + 1000 ∗ M +
100 ∗ O + 10 ∗ R + E =
10000 ∗ M + 1000 ∗ O + 100 ∗ N + 10 ∗ E + Y
function MoreMoney([S,E,N,D,M,O,R,Y])
[S,E,N,D,M,O,R,Y] ins 0..9
S #> 0; M #> 0
all_distinct ([S,E,N,D,M,O,R,Y])
1000∗S + 100∗E + 10∗N + D + 1000∗M + 100∗O + 10∗R + E
#= 10000∗M + 1000∗O + 100∗N + 10∗E + Y
labeling([S,E,N,D,M,O,R,Y])
MoreMoney([S,E,N,D,M,O,R,Y]):
S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, Y = 2
Úvod do umělé inteligence 3/12 29 / 35
CLP – Constraint Logic Programming Řešení problémů s omezujícími podmínkami
Inkrementální formulace CSP
CSP je možné převést na standardní prohledávání takto:
stav – přiřazení hodnot proměnným
počáteční stav – prázdné přiřazení {}
přechodová funkce – přiřazení hodnoty libovolné dosud nenastavené
proměnné tak, aby výsledné přiřazení bylo konzistentní
cílová podmínka – aktuální přiřazení je úplné
cena cesty – konstantní (např. 1) pro každý krok
Úvod do umělé inteligence 3/12 30 / 35
CLP – Constraint Logic Programming Řešení problémů s omezujícími podmínkami
Inkrementální formulace CSP
CSP je možné převést na standardní prohledávání takto:
stav – přiřazení hodnot proměnným
počáteční stav – prázdné přiřazení {}
přechodová funkce – přiřazení hodnoty libovolné dosud nenastavené
proměnné tak, aby výsledné přiřazení bylo konzistentní
cílová podmínka – aktuální přiřazení je úplné
cena cesty – konstantní (např. 1) pro každý krok
1. platí beze změny pro všechny CSP!
2. prohledávácí strom dosahuje hloubky n (počet proměnných) a řešení se
nachází v této hloubce (d = n) ⇒ je vhodné použít prohledávání do
hloubky
Úvod do umělé inteligence 3/12 30 / 35
CLP – Constraint Logic Programming Prohledávání s navracením
Prohledávání s navracením
přiřazení proměnným jsou komutativní
tj. [1. WA = červená, 2. NT = zelená] je totéž jako
[1. NT = zelená, 2. WA = červená]
stačí uvažovat pouze přiřazení jediné proměnné v každém kroku ⇒
počet listů max. |Di |n, větvení jde ovlivnit obecnými strategiemi
prohledávání do hloubky pro CSP – tzv. prohledávání s navracením
(backtracking search)
prohledávání s navracením je základní neinformovaná strategie pro
řešení problémů s omezujícími podmínkami
schopný vyřešit např. problém n-dam pro n ≈ 25 (naivní řešení 1069,
vlastní sloupce 1025)
Úvod do umělé inteligence 3/12 31 / 35
CLP – Constraint Logic Programming Příklad – problém N dam
Příklad – problém N dam
function Queens(N)
L = [qy1, qy2, ..., qyN ] # seznam N proměnných
L ins 1.. N
for i ← 1 to N-1 do
for j ← i+1 to N do
NoThreat(L[i], L[j ] , j - i)
labeling(L)
function NoThreat(Y1, Y2, J)
return Y1 #\= Y2 and Y1+J #\= Y2 and Y1-J #\= Y2
Úvod do umělé inteligence 3/12 32 / 35
CLP – Constraint Logic Programming Příklad – problém N dam
Příklad – problém N dam
function Queens(N)
L = [qy1, qy2, ..., qyN ] # seznam N proměnných
L ins 1.. N
for i ← 1 to N-1 do
for j ← i+1 to N do
NoThreat(L[i], L[j ] , j - i)
labeling(L)
function NoThreat(Y1, Y2, J)
return Y1 #\= Y2 and Y1+J #\= Y2 and Y1-J #\= Y2
1. definice proměnných a domén
2. definice omezení
3. hledání řešení
Úvod do umělé inteligence 3/12 32 / 35
CLP – Constraint Logic Programming Příklad – problém N dam
Příklad – problém N dam
function Queens(N)
L = [qy1, qy2, ..., qyN ] # seznam N proměnných
L ins 1.. N
for i ← 1 to N-1 do
for j ← i+1 to N do
NoThreat(L[i], L[j ] , j - i)
labeling(L)
function NoThreat(Y1, Y2, J)
return Y1 #\= Y2 and Y1+J #\= Y2 and Y1-J #\= Y2
Queens(4):
[2,4,1,3]
[3,1,4,2]
1. definice proměnných a domén
2. definice omezení
3. hledání řešení
Úvod do umělé inteligence 3/12 32 / 35
CLP – Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením
Ovlivnění efektivity prohledávání s navracením
Obecné metody ovlivnění efektivity:
– Která proměnná dostane hodnotu v tomto kroku?
– V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné?
– Můžeme předčasně detekovat nutný neúspěch v dalších krocích?
Úvod do umělé inteligence 3/12 33 / 35
CLP – Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením
Ovlivnění efektivity prohledávání s navracením
Obecné metody ovlivnění efektivity:
– Která proměnná dostane hodnotu v tomto kroku?
– V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné?
– Můžeme předčasně detekovat nutný neúspěch v dalších krocích?
používané strategie:
nejomezenější proměnná → vybrat proměnnou s nejméně možnými
hodnotami
Úvod do umělé inteligence 3/12 33 / 35
CLP – Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením
Ovlivnění efektivity prohledávání s navracením
Obecné metody ovlivnění efektivity:
– Která proměnná dostane hodnotu v tomto kroku?
– V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné?
– Můžeme předčasně detekovat nutný neúspěch v dalších krocích?
používané strategie:
nejomezenější proměnná → vybrat proměnnou s nejméně možnými
hodnotami
nejvíce omezující proměnná → vybrat proměnnou s nejvíce omezeními
na zbývající proměnné
Úvod do umělé inteligence 3/12 33 / 35
CLP – Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením
Ovlivnění efektivity prohledávání s navracením
Obecné metody ovlivnění efektivity:
– Která proměnná dostane hodnotu v tomto kroku?
– V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné?
– Můžeme předčasně detekovat nutný neúspěch v dalších krocích?
používané strategie:
nejomezenější proměnná → vybrat proměnnou s nejméně možnými
hodnotami
nejvíce omezující proměnná → vybrat proměnnou s nejvíce omezeními
na zbývající proměnné
nejméně omezující hodnota → pro danou proměnnou – hodnota, která
zruší nejmíň hodnot zbývajících proměnných SliDo
umožňuje 1 hodnotu pro SA
umožňuje 0 hodnot pro SA
Úvod do umělé inteligence 3/12 33 / 35
CLP – Constraint Logic Programming Ovlivnění efektivity prohledávání s navracením
Ovlivnění efektivity prohledávání s navracením
Obecné metody ovlivnění efektivity:
– Která proměnná dostane hodnotu v tomto kroku?
– V jakém pořadí zkoušet přiřazení hodnot konkrétní proměnné?
– Můžeme předčasně detekovat nutný neúspěch v dalších krocích?
používané strategie:
nejomezenější proměnná → vybrat proměnnou s nejméně možnými
hodnotami
nejvíce omezující proměnná → vybrat proměnnou s nejvíce omezeními
na zbývající proměnné
nejméně omezující hodnota → pro danou proměnnou – hodnota, která
zruší nejmíň hodnot zbývajících proměnných SliDo
dopředná kontrola → udržovat seznam možných hodnot pro zbývající
proměnné
propagace omezení → navíc kontrolovat možné nekonzistence mezi
zbývajícími proměnnými
Úvod do umělé inteligence 3/12 33 / 35
CLP – Constraint Logic Programming Ovlivnění efektivity v CLP
Ovlivnění efektivity v CLP
V Prologu (CLP) možnosti ovlivnění efektivity – labeling(Typ, ...):
?- constraints (Vars,Cost),
labeling ([ ff , bisect ,down,min(Cost)],Vars).
výběr proměnné – leftmost, min, max, ff, . . .
dělení domény – step, enum, bisect
prohledávání domény – up, down
uspořádání řešení – bez uspořádání nebo min(X), max(X), . . .
Úvod do umělé inteligence 3/12 34 / 35
CLP – Constraint Logic Programming Systémy pro řešení omezujících podmínek
Systémy pro řešení omezujících podmínek
Prolog – SWI, CHIP, ECLiPSe, SICStus Prolog, Prolog
IV, GNU Prolog, IF/Prolog
C/C++ – CHIP++, ILOG Solver, Gecode
Java – JCK, JCL, Koalog
LISP – Screamer
Python – logilab-constraint www.logilab.org/852,
python-constraint
Úvod do umělé inteligence 3/12 35 / 35