CLP(FD) - prohledávání Vestavěné predikáty pro labeling M Instanciace proměnné Variable hodnotami vjejí 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, 28. dubna 2009 2 CLP(FD) Vestavěné predikáty pro labeling M Instanciace proměnné Variable hodnotami vjejí 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 ? labelingC [] ). labelingC [Var | Rest] ) :- % výběr nejlevější proměnné k instanciaci indomain( Var ), % výběr hodnot ve vzrůstajícím pořadí labelingC Rest ). Hana Rudová, Logické programování I, 28. dubna 2009 2 CLP(FD) Vestavěné predikáty pro labeling M Instanciace proměnné Variable hodnotami vjejí 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 ? labelingC [] ). labelingC [Var | Rest] ) :- % výběr nejlevější proměnné k instanciaci indomain( Var ), % výběr hodnot ve vzrůstajícím pořadí labelingC Rest ). -• labelingC Options, Variables ) ?- A in 0..2, B in 0..2, B#< A, labeling([], [A,B]). Hana Rudová, Logické programování I, 28. dubna 2009 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 labelingC [] ). labelingC Variables ) :- sel ect_vari able(Vari ables,Var,Rest), select_value(Var,Value), Hana Rudová, Logické programování I, 28. dubna 2009 3 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 labelingC [] ). labelingC Variables ) :- sel ect_vari able(Vari ables,Var,Rest), select_value(Var,Value), ( Var #= Value, labelingC Rest ) Hana Rudová, Logické programování I, 28. dubna 2009 3 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 labelingC [] ). labelingC Variables ) :- sel ect_vari able(Vari ables,Var,Rest), select_value(Var,Value), ( Var #= Value, labelingC Rest ) Var #\= Value , % nemusí dojít k instanciaci Var labelingC Variables ) % proto pokračujeme se všemi proměnnými včetně Var )■ Hana Rudová, Logické programování I, 28. dubna 2009 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 labelingC [] ). labelingC Variables ) :- sel ect_vari able(Vari ables,Var,Rest), select_value(Var,Value), ( Var #= Value, labelingC Rest ) Var #\= Value , % nemusí dojít k instanciaci Var labelingC 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, 28. dubna 2009 3 CLP(FD) Výběr hodnoty -• Obecný princip výběru hodnoty: první úspěch (succeed first) M volíme pořadí tak, abychom výběr nemuseli opakovat M ?- domain([A,B,C],1,2), A#=B+C. Hana Rudová, Logické programování I, 28. dubna 2009 4 CLP(FD) Výběr hodnoty -• Obecný princip výběru hodnoty: první úspěch (succeed first) M volíme pořadí tak, abychom výběr nemuseli opakovat M ?- 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, 28. dubna 2009 4 CLP(FD) Výběr hodnoty -• Obecný princip výběru hodnoty: první úspěch (succeed first) M volíme pořadí tak, abychom výběr nemuseli opakovat M ?- domain([A, B,C] ,1, 2) , A#=B+C. optimální výběr A=2,B=1 ,C=1 je bez backtrackingu -• Parametry label i ng/2 ovlivňující výběr hodnoty př. label i ng( [down], Vars) M 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, 28. dubna 2009 4 CLP(FD) Výběr hodnoty -• Obecný princip výběru hodnoty: první úspěch (succeed first) M volíme pořadí tak, abychom výběr nemuseli opakovat M ?- domain([A, B,C] ,1, 2) , A#=B+C. optimální výběr A=2,B=1 ,C=1 je bez backtrackingu -• Parametry label i ng/2 ovlivňující výběr hodnoty př. label i ng( [down], Vars) M 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 1 abel i ng/2 řídící, jak je výběr hodnoty realizován M step: volba mezi X #= M, X #\= M (default) X 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ě St podobně jako při i ndomain/1 «• bisect: volba mezi X #=< Mid, X #> Mid ± vjednom kroku labelingu nedochází nutně k instanciaci proměnné Hana Rudová, Logické programování I, 28. dubna 2009 4 CLP(FD) Výběr proměnné -• Obecný princip výběru proměnné: first-fail 3 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 3 vybereme proměnnou s nejmenší doménou -• ?- domain([A,B,C],1,3), A#<3, A#=B+C. Hana Rudová, Logické programování I, 28. dubna 2009 5 Výběr proměnné -• Obecný princip výběru proměnné: first-fail 3 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 3 vybereme proměnnou s nejmenší doménou M ?- 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, 28. dubna 2009 5 CLP(FD) Výběr proměnné -• Obecný princip výběru proměnné: first-fail 3 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 3 vybereme proměnnou s nejmenší doménou M ?- domain ([A, B, C] ,1, 3) , A#<3, A#=B+C. nejlépe je začít s výběrem A -• Parametry label i ng/2 ovlivňující výběr proměnné 3 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, 28. dubna 2009 5 CLP(FD) Výběr proměnné -• Obecný princip výběru proměnné: first-fail 3 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 3 vybereme proměnnou s nejmenší doménou M ?- domain ([A, B, C] ,1, 3) , A#<3, A#=B+C. nejlépe je začít s výběrem A -• Parametry label i ng/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 M f f c: 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 M 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, 28. dubna 2009 5 CLP(FD) 95 Hledání optimálního řešení (předpokládejme minimaliz -• Parametry labeling/2 pro optimalizaci: minimize(F)/maxirrrize(F) M Cena #= A+B+C, labeling([mi ni mi ze(Cena)], [A,B,C]) -• Metoda větví a mezí (branch&bound) branch_and_bound(Vars, Cost) -• uvažujeme nejhorší možnou cenu řešení UB (např. cena už nalezeného řešení) 3 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, 28. dubna 2009 6 CLP(FD) Hledání optimálního řešení (předpokládejme minimalizaci -• Parametry labeling/2 pro optimalizaci: minimize(F)/maxirrrize(F) M Cena #= A+B+C, labeling([mi ni mi ze(Cena)], [A,B,C]) -• Metoda větví a mezí (branch&bound) branch_and_bound(Vars, Cost) -• uvažujeme nejhorší možnou cenu řešení UB (např. cena už nalezeného řešení) 3 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 M Iniciálně je Bound je předem známá nejhorší cena (např. krajní hodnota v doméně) branch_and_bound( Bound, Vars, Cost ) :- % jednoduchá implementace Cost #< Bound, findall( Vars-Cost, (labeling( Vars ), ! ), [ Solution-FoundCost ]), !, asserta( solution( Solution, FoundCost ) ), branch_and_bound( FoundCost, Vars, Cost ). branch_and_bound( _, Vars, Cost ) :- solution( Vars, Cost ), !. Hana Rudová, Logické programování I, 28. dubna 2009 6 CLP(FD) Hledání optimálního řešení (předpokládejme minimalizaci -• Parametry labeling/2 pro optimalizaci: minimize(F)/maxirrrize(F) M Cena #= A+B+C, labeling([mi ni mi ze(Cena)], [A,B,C]) -• Metoda větví a mezí (branch&bound) branch_and_bound(Vars, Cost) -• uvažujeme nejhorší možnou cenu řešení UB (např. cena už nalezeného řešení) 3 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 M Iniciálně je Bound je předem známá nejhorší cena (např. krajní hodnota v doméně) branch_and_bound( Bound, Vars, Cost ) :- % jednoduchá implementace Cost #< Bound, findall( Vars-Cost, (labeling( Vars ), ! ), [ Solution-FoundCost ]), !, asserta( solution( Solution, FoundCost ) ), branch_and_bound( FoundCost, Vars, Cost ). branch_and_bound( _, Vars, Cost ) :- solution( Vars, Cost ), !. Hana Rudová, Logické programování I, 28. dubna 2009 6 CLP(FD) Algoritmy pro řešení problému splňování podmínek (CSP) Grafová reprezentace CSP -• Reprezentace podmínek M intenzionální (matematická/logická formule) M extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) Hana Rudová, Logické programování I, 28. dubna 2009 8 Algoritmy pro CSP Grafová reprezentace CSP -• Reprezentace podmínek M intenzionální (matematická/logická formule) M extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) -• Graf: vrcholy, hrany (hrana spojuje dva vrcholy) M Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) -• Reprezentace CSP pomocí hypergrafu podmínek M vrchol = proměnná, hyperhrana = podmínka Hana Rudová, Logické programování I, 28. dubna 2009 8 Algoritmy pro CSP Grafová reprezentace CSP Reprezentace podmínek M intenzionální (matematická/logická formule) M extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) -• Graf: vrcholy, hrany (hrana spojuje dva vrcholy) M Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) -• Reprezentace CSP pomocí hypergrafu podmínek M vrchol = proměnná, hyperhrana = podmínka -• Příklad °1 M proměnné X\,...,Xq s doménou {0,1 3 omezení c\ : X\ + %2 + Xq = 1 C2 : X\ - X3 + X4 = 1 C3 : X4 + Xs - Xq > 0 Ca : X2 + Xs - Xq = 0 Hana Rudová, Logické programování I, 28. dubna 2009 3 Algoritmy pro CSP Binární CSP Binární CSP M CSP, ve kterém jsou pouze binární podmínky M unární podmínky zakódovány do domény proměnné Graf podmínek pro binární CSP M není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) Hana Rudová, Logické programování I, 28. dubna 2009 9 Algoritmy pro CSP Binární CSP -• Binární CSP M CSP, ve kterém jsou pouze binární podmínky M unární podmínky zakódovány do domény proměnné M Graf podmínek pro binární CSP M není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) M Každý CSP lze transformovat na "korespondující" binární CSP M Výhody a nevýhody binarizace M 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, 28. dubna 2009 9 Algoritmy pro CSP Binární CSP -• Binární CSP M CSP, ve kterém jsou pouze binární podmínky M unární podmínky zakódovány do domény proměnné M Graf podmínek pro binární CSP M není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) M Každý CSP lze transformovat na "korespondující" binární CSP M Výhody a nevýhody binarizace M 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 M lze využít jejich sémantiky pro lepší propagaci S* příklad: all_different vs. množina binárních nerovností Hana Rudová, Logické programování I, 28. dubna 2009 9 Algoritmy pro CSP Vrcholová a hranová konzistence -• Vrcholová konzistence (node consistency) NC -• každá hodnota z aktuální domény Vt proměnné splňuje všechny unární podmínky s proměnnou Vt Hana Rudová, Logické programování I, 28. dubna 2009 10 Algoritmy pro CSP Vrcholová a hranová konzistence -• Vrcholová konzistence (node consistency) NC -• každá hodnota z aktuální domény Vt proměnné splňuje všechny unární podmínky s proměnnou Vt M Hranová konzistence (arc consistency) AC pro binární CSP 3 hrana (Ví, V/) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Dt existuje hodnota y tak, že ohodnocení [Vt = x,Vj = y] splňuje všechny binární podmínky nad Ví, V). Hana Rudová, Logické programování I, 28. dubna 2009 10 Algoritmy pro CSP Vrcholová a hranová konzistence Vrcholová konzistence (node consistency) NC -• každá hodnota z aktuální domény Vt proměnné splňuje všechny unární podmínky s proměnnou Vt Hranová konzistence (arc consistency) AC pro binární CSP 3 hrana (Ví, V/) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Dt existuje hodnota y tak, že ohodnocení [Vt = x,Vj = y] splňuje všechny binární podmínky nad Ví, V), M hranová konzistence je směrová 3 konzistence hrany (V*, V}) nezaručuje konzistenci hrany (V/, V*) A řešení neexistuje -i- všechny domény jsou jednoprvkové => máme řešení -• v obecném případě se alespoň zmenší prohledávaný prostor Hana Rudová, Logické programování I, 28. dubna 2009 14 Algoritmy pro CSP k-konzistence M Mají NC a AC něco společného? -• NC: konzistence jedné proměnné M AC: konzistence dvou proměnných M ... můžeme pokračovat Hana Rudová, Logické programování I, 28. dubna 2009 15 k-konzistence M Mají NC a AC něco společného? -• NC: konzistence jedné proměnné M AC: konzistence dvou proměnných M ... můžeme pokračovat -• CSP je k-konzistentní právě tehdy, když můžeme libovolné konzistentní ohodnocení (k-1) různých proměnných rozšířit do libovolné k-té proměnné Hana Rudová, Logické programování I, 28. dubna 2009 15 Algoritmy pro CSP k-konzistence Mají NC a AC něco společného? -• NC: konzistence jedné proměnné M AC: konzistence dvou proměnných M ... můžeme pokračovat CSP je k-konzistentní právě tehdy, když můžeme libovolné konzistentní ohodnocení (k-1) různých proměnných rozšířit do libovolné k-té proměnné * / 9 ¥ 1,2,3-------1,2,3-------1,2,3------- 4 4-konzistentní graf Pro obecné CSP, tedy i pro nebinární podmínky Hana Rudová, Logické programování I, 28. dubna 2009 15 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf není 2-konzistentní Hana Rudová, Logické programování I, 28. dubna 2009 16 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1.1) lze rozšířit na (1,1,1) (2.2) lze rozšířit na (2,2,2) není 2-konzistentní (3) nelze rozšířit (1,3) ani (2,3) nejsou konzistentní dvojice (nerozšiřujeme je) Hana Rudová, Logické programování I, 28. dubna 2009 16 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1.1) lze rozšířit na (1,1,1) (2.2) lze rozšířit na (2,2,2) (1.3) ani (2,3) nejsou konzistentní dvojice (nerozšiřujeme je) není 2-konzistentní (3) nelze rozšířit CSPje silně k-konzistentní právě tehdy, když je j-konzistentní pro každé j k-konzistence Silná k-konzistence => j-konzistence V j < k k-konzistence ^> silná k-konzistence Hana Rudová, Logické programování I, 28. dubna 2009 16 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1.1) lze rozšířit na (1,1,1) (2.2) lze rozšířit na (2,2,2) (1.3) ani (2,3) nejsou konzistentní dvojice (nerozšiřujeme je) není 2-konzistentní (3) nelze rozšířit CSPje silně k-konzistentní právě tehdy, když je j-konzistentní pro každé j k-konzistence Silná k-konzistence => j-konzistence V j < k k-konzistence ^> silná k-konzistence NC = silná 1-konzistence = 1-konzistence AC = (silná) 2-konzistence Hana Rudová, Logické programování I, 28. dubna 2009 16 Algoritmy pro CSP Konzistence pro nalezení řešení -• Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení? M silná n-konzistence je nutná pro graf s n vrcholy Hana Rudová, Logické programování I, 28. dubna 2009 17 Algoritmy pro CSP Konzistence pro nalezení řešení -• Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení? M silná n-konzistence je nutná pro graf s n vrcholy s* n-konzistence nestačí (viz předchozí příklad) Hana Rudová, Logické programování I, 28. dubna 2009 17 Algoritmy pro CSP Konzistence pro nalezení řešení Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení? M silná n-konzistence je nutná pro graf s n vrcholy s* n-konzistence nestačí (viz předchozí příklad) s> silná k-konzistence pro k silná k-konzistence pro k B => min(A) = min(B)+l, max(B) = max(A)-l 3 příklad: A in 4.. 10, B in 6.. 18, A #> B mi n (A) = 6+1 => A in 7.. 10 max(B) = 10-1 => B in 6. .9 Hana Rudová, Logické programování I, 28. dubna 2009 21 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 e 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é Ví platí min(Di) < yt< max(Di) M stačí propagace pouze při změně minimální nebo maximální hodnoty (při změně mezí) v doméně proměnné M Konzistence mezí pro nerovnice M A #> B => min(A) = min(B)+l, max(B) = max(A)-l 3 příklad: A in 4.. 10, B in 6.. 18, A #> B mi n (A) = 6+1 => A in 7.. 10 max(B) = 10-1 => B in 6. .9 3 podobně: A #< B, A #>= B, A #=< B Hana Rudová, Logické programování I, 28. dubna 2009 21 Algoritmy pro CSP Konzistence mezí a aritmetická omezení -• A #= B + C => mi n(A) = min(B)+min(C), max(A) = max(B)+max(C) mi n (B) = mi n (A)-max (C) , max (B) = max (A)-mi n (C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) Hana Rudová, Logické programování I, 28. dubna 2009 22 Algoritmy pro CSP Konzistence mezí a aritmetická omezení -• A #= B + C => mi n(A) = min(B)+min(C), max(A) = max(B)+max(C) mi n (B) = mi n (A)-max (C) , max (B) = max (A)-mi n (C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) M změna max(A)vyvolá pouze změnu max(B) a max(C) , ... Hana Rudová, Logické programování I, 28. dubna 2009 22 Algoritmy pro CSP Konzistence mezí a aritmetická omezení -• A #= B + C => mi n(A) = min(B)+min(C), max(A) = max(B)+max(C) mi n (B) = mi n (A)-max (C) , max (B) = max (A)-mi n (C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) M změna max(A)vyvolá pouze změnu max(B) a max(C) , ... 3 Prí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, 28. dubna 2009 22 Algoritmy pro CSP Konzistence mezí a aritmetická omezení A #= B + C => mi n(A) = min(B)+min(C), max(A) = max(B)+max(C) mi n (B) = mi n (A)-max (C) , max (B) = max (A)-mi n (C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) M 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)=l+2, max(A)=10+2 => A in 3.. 10 => min(B)=l-2, max(B)=10-2 => B in 1..8 Hana Rudová, Logické programování I, 28. dubna 2009 22 Algoritmy pro CSP Konzistence mezí a aritmetická omezení -• A #= B + C => mi n(A) = min(B)+min(C), max(A) = max(B)+max(C) mi n (B) = mi n (A)-max (C) , max (B) = max (A)-mi n (C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) M změna max(A)vyvolá pouze změnu max(B) a max(C) , ... 3 Príklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 ^> min(A)=l+2, max(A)=10+2 => A in 3.. 10 => min(B)=l-2, max(B)=10-2 => B in 1..8 A #> 5 => mi n (A) =6 => A in 6.. 10 => mi n (B) =6-2 => B in 4.. 8 (nové vyvolání A #= B + 2) Hana Rudová, Logické programování I, 28. dubna 2009 22 Algoritmy pro CSP Konzistence mezí a aritmetická omezení -• A #= B + C => mi n(A) = min(B)+min(C), max(A) = max(B)+max(C) mi n (B) = mi n (A)-max (C) , max (B) = max (A)-mi n (C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) M změna max(A)vyvolá pouze změnu max(B) a max(C) , ... 3 Príklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 ^> min(A)=l+2, max(A)=10+2 => A in 3.. 10 => min(B)=l-2, max(B)=10-2 => B in 1..8 A #> 5 => mi n (A) =6 => A in 6.. 10 => mi n (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, 28. dubna 2009 22 Algoritmy pro CSP Konzistence mezí a aritmetická omezení -• A #= B + C => mi n(A) = min(B)+min(C), max(A) = max(B)+max(C) mi n (B) = mi n (A)-max (C) , max (B) = max (A)-mi n (C) mi n(C) = mi n(A)-max(B), max(C) = max(A)-mi n(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) M změna max(A)vyvolá pouze změnu max(B) a max(C) , ... 3 Príklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 ^> min(A)=l+2, max(A)=10+2 => A in 3.. 10 => min(B)=l-2, max(B)=10-2 => B in 1..8 A #> 5 => mi n (A) =6 => A in 6.. 10 => mi n (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) M Vyzkoušejte si: A #= B - C, A #>= B + C Hana Rudová, Logické programování I, 28. dubna 2009 22 Algoritmy pro CSP Globální podmínky M Propagace je lokální M pracuje se s jednotlivými podmínkami M interakce mezi podmínkami je pouze přes domény proměnných M 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: M all_different omezení: hodnoty všech proměnných různé 3 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, 28. dubna 2009 23 Algoritmy pro CSP Propagace pro al 1 -• U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 Hana Rudová, Logické programování I, 28. dubna 2009 24 _distinct učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Algoritmy pro CSP Propagace pro all_distinct -• U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Hana Rudová, Logické programování I, 28. dubna 2009 24 Alg Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: \/{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u D^} > k Hana Rudová, Logické programování I, 28. dubna 2009 24 Alg Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: \/{Xi,... ,Xk} c V : card{Di u ■ ■ ■ u D^} > k stačí hledat Halluv interval ľ. velikost intervalu /je rovna počtu proměnných, jejichž doména je v I Hana Rudová, Logické programování I, 28. dubna 2009 24 Alg Propagace pro a~N_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: \/{Xi,... ,Xk} c V : card{D\ u ■ ■ ■ u D^} > k stačí hledat Halluv interval ľ. velikost intervalu /je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo M U = {Xu ... ,Xk], dom(U) = {Di u ■ ■ ■ u Dk] učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 card(U) = card(dom(U)) => Vv g dom(U),VX g (V - U),X ± v Hana Rudová, Logické programování I, 28. dubna 2009 24 Algoritmy pro CSP Propagace pro all_distinct -• U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) -• Konzistence: \/{Xi,... ,Xk} c V : card{D\ u ■ ■ ■ u D^} > k stačí hledat Halluv interval ľ. velikost intervalu /je rovna počtu proměnných, jejichž doména je v I -• Inferenční pravidlo M U = {Xu ... ,Xk], dom(U) = {Di u ■ ■ ■ u Dk] 3 card(U) = card(dom(U)) => Vv g dom{U),\/X g (V - U),X + v M hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 28. dubna 2009 24 Algoritmy pro CSP Propagace pro a~N_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: \/{Xi,... ,Xk} c V : card{D\ u ■ ■ ■ u D^} > k stačí hledat Hallův interval ľ. velikost intervalu /je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo M U = {Xu ... ,Xk], dom(U) = {Di u ■ ■ ■ u Dk] 3 card(U) = card(dom(U)) => Vv g dom{U),\/X g (V - U),X + v M hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Složitost: 0(2n) - hledání všech podmnožin množiny n proměnných (naivní) Hana Rudová, Logické programování I, 28. dubna 2009 24 Algoritmy pro CSP Propagace pro all_distinct -• U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro XI, X3, X6 XI in 5..6, X3 = 5, X6 in {1} \/ (5..6) -• Konzistence: \/{Xi,... ,Xk} c V : card{D\ u ■ ■ ■ u D^} > k stačí hledat Hallův interval ľ. velikost intervalu /je rovna počtu proměnných, jejichž doména je v I -• Inferenční pravidlo M U = {Xu ... ,Xk], dom(U) = {Di u ■ ■ ■ u Dk] 3 card(U) = card(dom(U)) => Vv g dom{U),\/X g (V - U),X + v M hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné M Složitost: 0(2n) - hledání všech podmnožin množiny n proměnných (naivní) 0(n\ogn) - kontrola hraničních bodů Hallových intervalů (1998) Hana Rudová, Logické programování I, 28. dubna 2009 24 Algoritmy pro CSP učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6