CLP(FD) - prohledávání Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnoty jsou instanciovány při backtrackingu ve vzrůstajícím pořadí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? Hana Rudová, Logické programování I, 7. května 2007 2 CLP(FD) Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnoty jsou instanciovány při backtrackingu ve vzrůstajícím pořadí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? labeling( [] ). labeling( [Var|Rest] ) :- % výběr nejlevější proměnné k instanciaci indomain( Var ), % výběr hodnot ve vzrůstajícím pořadí labeling( Rest ). Hana Rudová, Logické programování I, 7. května 2007 2 CLP(FD) Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnoty jsou instanciovány při backtrackingu ve vzrůstajícím pořadí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? labeling( [] ). labeling( [Var|Rest] ) :- % výběr nejlevější proměnné k instanciaci indomain( Var ), % výběr hodnot ve vzrůstajícím pořadí labeling( Rest ). labeling( Options, Variables ) ?- A in 0..2, B in 0..2, B#< A, labeling([], [A,B]). Hana Rudová, Logické programování I, 7. května 2007 2 CLP(FD) Uspořádání hodnot a proměnných Při prohledávání je rozhodující uspořádání hodnot a proměnných Určují je heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) :- select_variable(Variables,Var,Rest), select_value(Var,Value), Hana Rudová, Logické programování I, 7. května 2007 3 CLP(FD) Uspořádání hodnot a proměnných Při prohledávání je rozhodující uspořádání hodnot a proměnných Určují je heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) :- select_variable(Variables,Var,Rest), select_value(Var,Value), ( Var #= Value, labeling( Rest ) Hana Rudová, Logické programování I, 7. května 2007 3 CLP(FD) Uspořádání hodnot a proměnných Při prohledávání je rozhodující uspořádání hodnot a proměnných Určují je heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) :- select_variable(Variables,Var,Rest), select_value(Var,Value), ( Var #= Value, labeling( Rest ) ; Var #\= Value , % nemusí dojít k instanciaci Var labeling( Variables ) % proto pokračujeme se všemi proměnnými včetně Var ). Hana Rudová, Logické programování I, 7. května 2007 3 CLP(FD) Uspořádání hodnot a proměnných Při prohledávání je rozhodující uspořádání hodnot a proměnných Určují je heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) :- select_variable(Variables,Var,Rest), select_value(Var,Value), ( Var #= Value, labeling( Rest ) ; Var #\= Value , % nemusí dojít k instanciaci Var labeling( Variables ) % proto pokračujeme se všemi proměnnými včetně Var ). Statické uspořádání: určeno už před prohledáváním Dynamické uspořádání: počítá se během prohledávání Hana Rudová, Logické programování I, 7. května 2007 3 CLP(FD) Výběr hodnoty Obecný princip výběru hodnoty: první úspěch (succeed first) volíme pořadí tak, abychom výběr nemuseli opakovat ?- domain([A,B,C],1,2), A#=B+C. Hana Rudová, Logické programování I, 7. května 2007 4 CLP(FD) Výběr hodnoty Obecný princip výběru hodnoty: první úspěch (succeed first) volíme pořadí tak, abychom výběr nemuseli opakovat ?- domain([A,B,C],1,2), A#=B+C. optimální výběr A=2,B=1,C=1 je bez backtrackingu Hana Rudová, Logické programování I, 7. května 2007 4 CLP(FD) Výběr hodnoty Obecný princip výběru hodnoty: první úspěch (succeed first) volíme pořadí tak, abychom výběr nemuseli opakovat ?- domain([A,B,C],1,2), A#=B+C. optimální výběr A=2,B=1,C=1 je bez backtrackingu Parametry labeling/2 ovlivňující výběr hodnoty př. labeling([down], Vars) up: doména procházena ve vzrůstajícím pořadí (default) down: doména procházena v klesajícím pořadí Hana Rudová, Logické programování I, 7. května 2007 4 CLP(FD) Výběr hodnoty Obecný princip výběru hodnoty: první úspěch (succeed first) volíme pořadí tak, abychom výběr nemuseli opakovat ?- domain([A,B,C],1,2), A#=B+C. optimální výběr A=2,B=1,C=1 je bez backtrackingu Parametry labeling/2 ovlivňující výběr hodnoty př. labeling([down], Vars) up: doména procházena ve vzrůstajícím pořadí (default) down: doména procházena v klesajícím pořadí Parametry labeling/2 řídící, jak je výběr hodnoty realizován step: volba mezi X #= M, X #\= M (default) viz dřívější příklad u "Uspořádání hodnot a proměnných" enum: vícenásobná volba mezi všemi hodnotami v doméně podobně jako při indomain/1 bisect: volba mezi X #=< Mid, X #> Mid v jednom kroku labelingu nedochází nutně k instanciaci proměnné Hana Rudová, Logické programování I, 7. května 2007 4 CLP(FD) Výběr proměnné Obecný princip výběru proměnné: first-fail výběr proměnné, pro kterou je nejobtížnější nalézt správnou hodnotu pozdější výběr hodnoty pro tuto proměnnou by snadněji vedl k failu výbereme proměnnou s nejmenší doménou ?- domain([A,B,C],1,3), A#<3, A#=B+C. Hana Rudová, Logické programování I, 7. května 2007 5 CLP(FD) Výběr proměnné Obecný princip výběru proměnné: first-fail výběr proměnné, pro kterou je nejobtížnější nalézt správnou hodnotu pozdější výběr hodnoty pro tuto proměnnou by snadněji vedl k failu výbereme proměnnou s nejmenší doménou ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je začít s výběrem A Hana Rudová, Logické programování I, 7. května 2007 5 CLP(FD) Výběr proměnné Obecný princip výběru proměnné: first-fail výběr proměnné, pro kterou je nejobtížnější nalézt správnou hodnotu pozdější výběr hodnoty pro tuto proměnnou by snadněji vedl k failu výbereme proměnnou s nejmenší doménou ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je začít s výběrem A Parametry labeling/2 ovlivňující výběr proměnné leftmost: nejlevější (default) ff: s (a) nejmenší velikostí domény fd_size(Var,Size) (b) nejlevější z nich Hana Rudová, Logické programování I, 7. května 2007 5 CLP(FD) Výběr proměnné Obecný princip výběru proměnné: first-fail výběr proměnné, pro kterou je nejobtížnější nalézt správnou hodnotu pozdější výběr hodnoty pro tuto proměnnou by snadněji vedl k failu výbereme proměnnou s nejmenší doménou ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je začít s výběrem A Parametry labeling/2 ovlivňující výběr proměnné leftmost: nejlevější (default) ff: s (a) nejmenší velikostí domény fd_size(Var,Size) (b) nejlevější z nich ffc: s (a) nejmenší velikostí domény (b) největším množstvím omezením ,,čekajících" na proměnné fd_degree(Var,Size) (c) nejlevější z nich min/max: s (a) nejmenší/největší hodnotou v doméně proměnné (b) nejlevnější z nich fd_min(Var,Min)/fd_max(Var,Max) Hana Rudová, Logické programování I, 7. května 2007 5 CLP(FD) Hledání optimálního řešení (předpokládejme minimalizaci) Parametry labeling/2 pro optimalizaci: minimize(F)/maximize(F) Cena #= A+B+C, labeling([minimize(Cena)], [A,B,C]) Metoda větví a mezí (branch&bound) uvažujeme nejhorší možnou cenu řešení UB (např. cena už nalezeného řešení) počítáme dolní odhad LB ceny částečného řešení LB je tedy nejlepší možná cena pro rozšíření tohoto řešení procházíme strom a vyžadujeme, aby prozkoumávaná větev měla cenu LB < UB pokud je LB UB, tak víme, že v této větvi není lepší řešení a odřízneme ji Hana Rudová, Logické programování I, 7. května 2007 6 CLP(FD) Hledání optimálního řešení (předpokládejme minimalizaci) Parametry labeling/2 pro optimalizaci: minimize(F)/maximize(F) Cena #= A+B+C, labeling([minimize(Cena)], [A,B,C]) Metoda větví a mezí (branch&bound) uvažujeme nejhorší možnou cenu řešení UB (např. cena už nalezeného řešení) počítáme dolní odhad LB ceny částečného řešení LB je tedy nejlepší možná cena pro rozšíření tohoto řešení procházíme strom a vyžadujeme, aby prozkoumávaná větev měla cenu LB < UB pokud je LB UB, tak víme, že v této větvi není lepší řešení a odřízneme ji Hana Rudová, Logické programování I, 7. května 2007 6 CLP(FD) Algoritmy pro řešení problému splňování podmínek (CSP) Grafová reprezentace CSP Reprezentace podmínek intenzionální (matematická/logická formule) extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) Hana Rudová, Logické programování I, 7. května 2007 8 Algoritmy pro CSP Grafová reprezentace CSP Reprezentace podmínek intenzionální (matematická/logická formule) extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) Graf: vrcholy, hrany (hrana spojuje dva vrcholy) Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) Reprezentace CSP pomocí hypergrafu podmínek vrchol = proměnná, hyperhrana = podmínka Hana Rudová, Logické programování I, 7. května 2007 8 Algoritmy pro CSP Grafová reprezentace CSP Reprezentace podmínek intenzionální (matematická/logická formule) extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) Graf: vrcholy, hrany (hrana spojuje dva vrcholy) Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) Reprezentace CSP pomocí hypergrafu podmínek vrchol = proměnná, hyperhrana = podmínka Příklad proměnné x1, . . . , x6 s doménou {0, 1} omezení c1 : x1 + x2 + x6 = 1 c2 : x1 - x3 + x4 = 1 c3 : x4 + x5 - x6 > 0 c4 : x2 + x5 - x6 = 0 Hana Rudová, Logické programování I, 7. května 2007 8 Algoritmy pro CSP Binární CSP Binární CSP CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény proměnné Graf podmínek pro binární CSP není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) Hana Rudová, Logické programování I, 7. května 2007 9 Algoritmy pro CSP Binární CSP Binární CSP CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény proměnné Graf podmínek pro binární CSP není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) Každý CSP lze transformovat na "korespondující" binární CSP Výhody a nevýhody binarizace získáváme unifikovaný tvar CSP problému, řada algoritmů navržena pro binární CSP bohužel ale značné zvětšení velikosti problému Hana Rudová, Logické programování I, 7. května 2007 9 Algoritmy pro CSP Binární CSP Binární CSP CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény proměnné Graf podmínek pro binární CSP není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) Každý CSP lze transformovat na "korespondující" binární CSP Výhody a nevýhody binarizace získáváme unifikovaný tvar CSP problému, řada algoritmů navržena pro binární CSP bohužel ale značné zvětšení velikosti problému Nebinární podmínky složitější propagační algoritmy lze využít jejich sémantiky pro lepší propagaci příklad: all_different vs. množina binárních nerovností Hana Rudová, Logické programování I, 7. května 2007 9 Algoritmy pro CSP Vrcholová a hranová konzistence Vrcholová konzistence (node consistency) NC každá hodnota z aktuální domény Vi proměnné splňuje všechny unární podmínky s proměnnou Vi Hana Rudová, Logické programování I, 7. května 2007 10 Algoritmy pro CSP Vrcholová a hranová konzistence Vrcholová konzistence (node consistency) NC každá hodnota z aktuální domény Vi proměnné splňuje všechny unární podmínky s proměnnou Vi Hranová konzistence (arc consistency) AC pro binární CSP hrana (Vi, Vj) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Di existuje hodnota y tak, že ohodnocení [Vi = x, Vj = y] splňuje všechny binární podmínky nad Vi, Vj. Hana Rudová, Logické programování I, 7. května 2007 10 Algoritmy pro CSP Vrcholová a hranová konzistence Vrcholová konzistence (node consistency) NC každá hodnota z aktuální domény Vi proměnné splňuje všechny unární podmínky s proměnnou Vi Hranová konzistence (arc consistency) AC pro binární CSP hrana (Vi, Vj) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Di existuje hodnota y tak, že ohodnocení [Vi = x, Vj = y] splňuje všechny binární podmínky nad Vi, Vj. hranová konzistence je směrová konzistence hrany (Vi, Vj) nezaručuje konzistenci hrany (Vj, Vi) 1..5 B A B => min(A) = min(B)+1, max(B) = max(A)-1 příklad: A in 4..10, B in 6..18, A #> B min(A) = 6+1 A in 7..10 max(B) = 10-1 B in 6..9 Hana Rudová, Logické programování I, 7. května 2007 15 Algoritmy pro CSP Konzistence mezí Bounds consistency BC: slabší než obecná hranová konzistence podmínka má konzistentní meze (BC), právě když pro každou proměnnou Vj z této podmínky a každou hodnou x Dj existuje ohodnocení zbylých proměnných v podmínce tak, že je podmínka splněna a pro vybrané ohodnocení yi proměnné Vi platí min(Di) yi max(Di) stačí propagace pouze při změně minimální nebo maximální hodnoty (při změně mezí) v doméně proměnné Konzistence mezí pro nerovnice A #> B => min(A) = min(B)+1, max(B) = max(A)-1 příklad: A in 4..10, B in 6..18, A #> B min(A) = 6+1 A in 7..10 max(B) = 10-1 B in 6..9 podobně: A #< B, A #>= B, A #=< B Hana Rudová, Logické programování I, 7. května 2007 15 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) Hana Rudová, Logické programování I, 7. května 2007 16 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Hana Rudová, Logické programování I, 7. května 2007 16 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 Hana Rudová, Logické programování I, 7. května 2007 16 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 min(A)=1+2, max(A)=10+2 A in 3..10 min(B)=1-2, max(B)=10-2 B in 1..8 Hana Rudová, Logické programování I, 7. května 2007 16 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 min(A)=1+2, max(A)=10+2 A in 3..10 min(B)=1-2, max(B)=10-2 B in 1..8 A #> 5 min(A)=6 A in 6..10 min(B)=6-2 B in 4..8 (nové vyvolání A #= B + 2) Hana Rudová, Logické programování I, 7. května 2007 16 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 min(A)=1+2, max(A)=10+2 A in 3..10 min(B)=1-2, max(B)=10-2 B in 1..8 A #> 5 min(A)=6 A in 6..10 min(B)=6-2 B in 4..8 (nové vyvolání A #= B + 2) A #\= 8 A in (6..7) \/ (9..10) (meze stejné, k propagaci A #= B + 2 nedojde) Hana Rudová, Logické programování I, 7. května 2007 16 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(B) = min(A)-max(C), max(B) = max(A)-min(C) min(C) = min(A)-max(B), max(C) = max(A)-min(B) změna min(A)vyvolá pouze změnu min(B) a min(C) změna max(A)vyvolá pouze změnu max(B) a max(C), ... Příklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 min(A)=1+2, max(A)=10+2 A in 3..10 min(B)=1-2, max(B)=10-2 B in 1..8 A #> 5 min(A)=6 A in 6..10 min(B)=6-2 B in 4..8 (nové vyvolání A #= B + 2) A #\= 8 A in (6..7) \/ (9..10) (meze stejné, k propagaci A #= B + 2 nedojde) Vyzkoušejte si: A #= B - C, A #>= B + C Hana Rudová, Logické programování I, 7. května 2007 16 Algoritmy pro CSP Globální podmínky Propagace je lokální pracuje se s jednotlivými podmínkami interakce mezi podmínkami je pouze přes domény proměnných Jak dosáhnout více, když je silnější propagace drahá? Seskupíme několik podmínek do jedné tzv. globální podmínky Propagaci přes globální podmínku řešíme speciálním algoritmem navrženým pro danou podmínku Příklady: all_different omezení: hodnoty všech proměnných různé serialized omezení: rozvržení úloh zadaných startovním časem a dobou trvání tak, aby se nepřekrývaly Hana Rudová, Logické programování I, 7. května 2007 17 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 Hana Rudová, Logické programování I, 7. května 2007 18 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Hana Rudová, Logické programování I, 7. května 2007 18 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k Hana Rudová, Logické programování I, 7. května 2007 18 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k stačí hledat Hallův interval I: velikost intervalu I je rovna počtu proměnných, jejichž doména je v I Hana Rudová, Logické programování I, 7. května 2007 18 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k stačí hledat Hallův interval I: velikost intervalu I je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo U = {X1, . . . , Xk}, dom(U) = {D1 Dk} card(U) = card(dom(U)) v dom(U), X (V - U), X = v Hana Rudová, Logické programování I, 7. května 2007 18 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k stačí hledat Hallův interval I: velikost intervalu I je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo U = {X1, . . . , Xk}, dom(U) = {D1 Dk} card(U) = card(dom(U)) v dom(U), X (V - U), X = v hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Hana Rudová, Logické programování I, 7. května 2007 18 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k stačí hledat Hallův interval I: velikost intervalu I je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo U = {X1, . . . , Xk}, dom(U) = {D1 Dk} card(U) = card(dom(U)) v dom(U), X (V - U), X = v hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Složitost: O(2n ) ­ hledání všech podmnožin množiny n proměnných (naivní) Hana Rudová, Logické programování I, 7. května 2007 18 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: {X1, . . . , Xk} V : card{D1 Dk} k stačí hledat Hallův interval I: velikost intervalu I je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo U = {X1, . . . , Xk}, dom(U) = {D1 Dk} card(U) = card(dom(U)) v dom(U), X (V - U), X = v hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Složitost: O(2n ) ­ hledání všech podmnožin množiny n proměnných (naivní) O(n log n) ­ kontrola hraničních bodů Hallových intervalů (1998) Hana Rudová, Logické programování I, 7. května 2007 18 Algoritmy pro CSP Prohledávání + konzistence Splňování podmínek prohledáváním prostoru řešení podmínky jsou užívány pasivně jako test přiřazuji hodnoty proměnných a zkouším co se stane vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj Hana Rudová, Logické programování I, 7. května 2007 19 Algoritmy pro CSP Prohledávání + konzistence Splňování podmínek prohledáváním prostoru řešení podmínky jsou užívány pasivně jako test přiřazuji hodnoty proměnných a zkouším co se stane vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) zbytečně pomalé (exponenciální): procházím i ,,evidentně" špatná ohodnocení Hana Rudová, Logické programování I, 7. května 2007 19 Algoritmy pro CSP Prohledávání + konzistence Splňování podmínek prohledáváním prostoru řešení podmínky jsou užívány pasivně jako test přiřazuji hodnoty proměnných a zkouším co se stane vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) zbytečně pomalé (exponenciální): procházím i ,,evidentně" špatná ohodnocení Konzistenční (propagační) techniky umožňují odstranění nekonzistentních hodnot z domény proměnných neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) relativně rychlé (polynomiální) Hana Rudová, Logické programování I, 7. května 2007 19 Algoritmy pro CSP Prohledávání + konzistence Splňování podmínek prohledáváním prostoru řešení podmínky jsou užívány pasivně jako test přiřazuji hodnoty proměnných a zkouším co se stane vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) zbytečně pomalé (exponenciální): procházím i ,,evidentně" špatná ohodnocení Konzistenční (propagační) techniky umožňují odstranění nekonzistentních hodnot z domény proměnných neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) relativně rychlé (polynomiální) Používá se kombinace obou metod postupné přiřazování hodnot proměnným po přiřazení hodnoty odstranění nekonzistentních hodnot konzistenčními technikami Hana Rudová, Logické programování I, 7. května 2007 19 Algoritmy pro CSP Prohledávání s navracením Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky Dvě fáze prohledávání s navracením dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistení hodnoty (pokud existuje) další proměnné po vybrání hodnoty testujeme konzistenci zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí přiřazené hodnotě Hana Rudová, Logické programování I, 7. května 2007 20 Algoritmy pro CSP Prohledávání s navracením Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky Dvě fáze prohledávání s navracením dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistení hodnoty (pokud existuje) další proměnné po vybrání hodnoty testujeme konzistenci zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí přiřazené hodnotě Proměnné dělíme na minulé ­ proměnné, které už byly vybrány (a mají přiřazenu hodnotu) aktuální ­ proměnná, která je právě vybrána a je jí přiřazována hodnota budoucí ­ proměnné, které budou vybrány v budoucnosti Hana Rudová, Logické programování I, 7. května 2007 20 Algoritmy pro CSP Přehled algoritmů prirazene (minule) neprirazene (budouci) 7 6 1 2 3 5 promenne a aktualni4 n FC LA BT Backtracking (BT) kontroluje v kroku a podmínky c(V1, Va), . . . , c(Va-1, Va) z minulých proměnných do aktuální proměnné Hana Rudová, Logické programování I, 7. května 2007 21 Algoritmy pro CSP Přehled algoritmů prirazene (minule) neprirazene (budouci) 7 6 1 2 3 5 promenne a aktualni4 n FC LA BT Backtracking (BT) kontroluje v kroku a podmínky c(V1, Va), . . . , c(Va-1, Va) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky c(Va, Va+1), . . . , c(Va, Vn) z aktuální proměnné do budoucích proměnných Hana Rudová, Logické programování I, 7. května 2007 21 Algoritmy pro CSP Přehled algoritmů prirazene (minule) neprirazene (budouci) 7 6 1 2 3 5 promenne a aktualni4 n FC LA BT Backtracking (BT) kontroluje v kroku a podmínky c(V1, Va), . . . , c(Va-1, Va) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky c(Va, Va+1), . . . , c(Va, Vn) z aktuální proměnné do budoucích proměnných Pohled dopředu (LA) kontroluje v kroku a podmínky l(a l n), k(a k n), k = l : c(Vk, Vl) z aktuální proměnné do budoucích proměnných a mezi budoucími proměnnými Hana Rudová, Logické programování I, 7. května 2007 21 Algoritmy pro CSP Základní algoritmus prohledávání s navracením Pro jednoduchost proměnné očíslujeme a ohodnocujeme je v daném pořadí Na začátku voláno jako labeling(G,1) procedure labeling(G,a) if a > |uzly(G)| then return uzly(G) for x Da do if consistent(G,a) then % consistent(G,a) je nahrazeno FC, LA, ... R := labeling(G,a + 1) if R = fail then return R return fail end labeling Po přiřazení všech proměnných vrátíme jejich ohodnocení Procedury consistent uvedeme pouze pro binární podmínky Hana Rudová, Logické programování I, 7. května 2007 22 Algoritmy pro CSP Backtracking (BT) Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné Backtracking tedy zajišt'uje konzistenci podmínek na všech minulých proměnných na podmínkách mezi minulými proměnnými a aktuální proměnnou Hana Rudová, Logické programování I, 7. května 2007 23 Algoritmy pro CSP Backtracking (BT) Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné Backtracking tedy zajišt'uje konzistenci podmínek na všech minulých proměnných na podmínkách mezi minulými proměnnými a aktuální proměnnou procedure BT(G,a) Q:={(Vi, Va) hrany(G), i < a} % hrany vedoucí do minulých proměnných Consistent := true while Q není prázdná Consistent do vyber a smaž libovolnou hranu (Vk, Vm) z Q Consistent := not revise(Vk, Vm) % pokud vyřadíme prvek, bude doména prázdná return Consistent end BT Hana Rudová, Logické programování I, 7. května 2007 23 Algoritmy pro CSP Příklad: backtracking Omezení: V1, V2, V3 in 1 . . . 3, V1# = 3 × V3 Stavový prostor: V3 V1 V2 1 2 3 1 2 31 2 3 1 2 3 1 2 31 2 3 1 2 3 1 2 31 2 31 2 3 1 2 31 2 3 1 2 3 červené čtverečky: chybný pokus o instanciaci, řešení neexistuje nevyplněná kolečka: nalezeno řešení černá kolečka: vnitřní uzel, máme pouze částečné přiřazení Hana Rudová, Logické programování I, 7. května 2007 24 Algoritmy pro CSP Kontrola dopředu (FC ­ forward checking) FC je rozšíření backtrackingu FC navíc zajišt'uje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami Hana Rudová, Logické programování I, 7. května 2007 25 Algoritmy pro CSP Kontrola dopředu (FC ­ forward checking) FC je rozšíření backtrackingu FC navíc zajišt'uje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami procedure FC(G,a) Q:={(Vi, Va) hrany(G), i > a} % přidání hran z aktuální proměnné do budoucích prom. Consistent := true while Q není prázdná Consistent do vyber a smaž libovolnou hranu (Vk, Vm) z Q if revise((Vk, Vm)) then Consistent := (|Dk| > 0) % vyprázdnění domény znamená nekonzistenci return Consistent end FC Hrany z aktuální proměnné do minulých proměnných není nutno testovat Hana Rudová, Logické programování I, 7. května 2007 25 Algoritmy pro CSP Příklad: kontrola dopředu Omezení: V1, V2, V3 in 1 . . . 3, V1# = 3 × V3 Stavový prostor: 1 2 3 V3 V1 V2 1 11 1 2 3 Hana Rudová, Logické programování I, 7. května 2007 26 Algoritmy pro CSP Pohled dopředu (LA ­ looking ahead) LA je rozšíření FC, LA zajišt'uje hranovou konzistenci LA navíc ověřuje i konzistenci všech hran mezi budoucími proměnnými procedure LA(G,a) Q := {(Vi, Va) hrany(G), i > a} % začínáme s hranami do a Consistent := true while Q není prázdná Consistent do vyber a smaž libovolnou hranu (Vk, Vm) z Q if revise((Vk, Vm)) then Q := Q {(Vi, Vk)|(Vi, Vk) hrany(G), i = k, i = m, i > a} Consistent := (|Dk| > 0) return Consistent end LA Hana Rudová, Logické programování I, 7. května 2007 27 Algoritmy pro CSP Pohled dopředu (LA ­ looking ahead) LA je rozšíření FC, LA zajišt'uje hranovou konzistenci LA navíc ověřuje i konzistenci všech hran mezi budoucími proměnnými procedure LA(G,a) Q := {(Vi, Va) hrany(G), i > a} % začínáme s hranami do a Consistent := true while Q není prázdná Consistent do vyber a smaž libovolnou hranu (Vk, Vm) z Q if revise((Vk, Vm)) then Q := Q {(Vi, Vk)|(Vi, Vk) hrany(G), i = k, i = m, i > a} Consistent := (|Dk| > 0) return Consistent end LA Hrany z aktuální proměnné do minulých proměnných opět netestujeme Tato LA procedura je založena na AC-3, lze použít i jiné AC algoritmy Hana Rudová, Logické programování I, 7. května 2007 27 Algoritmy pro CSP Příklad: pohled dopředu Omezení: V1, V2, V3 in 1 . . . 4, V1# > V2, V2# = 3 × V3 Stavový prostor: V3 V1 V2 1 2 3 4 3 1 Hana Rudová, Logické programování I, 7. května 2007 28 Algoritmy pro CSP