Vestavěné predikáty pro labeling CLPCFD) - prohledávání 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 TabelingC [] ). TabelingC Variables ) :- select_variable(Variables,Var,Rest), select_va"lue(Var,Va"lue), C Var #= Value, TabelingC Rest ) Var #\= Value , % nemusí dojít k instanciaci Var TabelingC 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, 29. dubna 2012 3 CLP(FD) Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnotyjsou instanciovány při backtrackingu ve vzrůstajícím pořadí ?- X in 4. .5, indomain(X). X = 4 ? ; X = 5 ? TabelingC [] ). TabelingC [Var|Rest] ) indomain( Var ) , TabelingC Rest ) . % výběr nejlevější proměnné k instanciaci % výběr hodnot ve vzrůstajícím pořadí ■ TabelingC Options, Variables ) ?- A in 0..2, B in 0..2, B#< A, labeling([], [A,B]). Hana Rudová, Logické programování I, 29. dubna 201 2 2 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 ■ ?- domai n( [A, B, C] , 1,2) , A#=B+C. optimální výběr A=2,B=1 ,C=1 je bez backtrackingu Parametry 1 abeling/2 ovlivňující výběr hodnoty př. labe"ling([down], Vars) ■ up: doména procházena ve vzrůstajícím pořadí ■ 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 ■ step: volba mezi X #= M, X #\= M ■ 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 (default) (default) Hana Rudová, Logické programování I, 29. dubna 201 2 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 ■ vybereme proměnnou s nejmenší doménou ■ ?- domai n ([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 (1) nejmenší velikostí domény fd_size(Var,Size) (2) (pokud s nejmenší velikostí domény více, tak) nejlevější z nich ■ f f c: s (1) nejmenší velikostí domény (2) největším množstvím omezením „čekajících" na proměnné fd_degree(Var,Size) (3) nejlevější z nich ■ mi n/max: s (1) nejmenší/největší hodnotou v doméně proměnné (2) nejlevnějšíz nich fd_min(Var,Min)/fd_max(Var,Max) Hana Rudová, Logické programování I, 29. dubna 2012 5 CLP(FD) Hledání optimálního řešení (předpokládejme minimalizaci) ■ Parametry 1 abeli ng/2 pro optimalizaci: minimize(F)/maximize(F) ■ Cena #= A+B+C, labe"ling([minimize(Cena)] , [A,B,C]) ■ Metoda větví a mezí (branch&bound) ■ algoritmus, který implementuje proceduru pro minimalizaci (duálně pro maximalizaci) ■ 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í Li? 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 ■ přidává se tedy inkrementálně omezení LB#= S+D, afterCSs, Ds, End). Hana Rudová, Logické programování I, 29. dubna 2012 8 CLP(FD) Algoritmy pro řešení problému splňování podmínek (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: a"l"l_different vs. množina binárních nerovností Hana Rudová, Logické programování 1,29. dubna 2012 11 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) 1 Graf: vrcholy, hrany (hrana spojuje dva vrcholy) 1 Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) 1 Reprezentace CSP pomocí hypergrafu podmínek ■ vrchol = proměnná, hyperhrana = podmínka ■ Příklad ■ proměnné x\.....s doménou {0,1 ■ omezení c\ : X\ + x-i + = 1 /X C2 I Xi - X3 + %4 = 1 C3 \ X4 + Xs - X% > 0 C4 : X2 + Xs - X% = 0 Hana Rudová, Logické programování I, 29. dubna 201 2 Algoritmy pro CSP Vrcholová a hranová konzistence Vrcholová konzistence (node consistency) NC ■ každá hodnota z aktuální domény V proměnné splňuje všechny unární podmínky s proměnnou Ví Hranová konzistence (arc consistency) AC pro binární CSP ■ hrana (Ví, V}) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Dí existuje hodnota y tak, že ohodnocení [Ví = x,Vj = y] splňuje všechny binární podmínky nad Ví, V,. ■ hranová konzistence je směrová ■ konzistence hrany (VuVj) nezaručuje konzistenci hrany (Vj,Ví) » l„ _ i A v ■ hranu (m, fe) vedoucí z proměnné Vm, která zmenšení domény způsobila, není třeba revidovat (změna sejí nedotkne) Hana Rudová, Logické programování I, 29. dubna 2012 14 Algoritmy pro CSP Algoritmus AC-3 procedure AC-3CC) Q := {(í.j) I Cíi j) e hrany(G), i 4= j} % seznam hran pro revizi while Q non empty do vyber a smaž (fe,m) z Q if revise((fc,m)) then % přidáni pouze hran, které Q := Q u {(í, k) e hrany(G), í 4 k, í4=in} % dosud nejsou ve fronte end while end AC-3 ®^®^® A řešení neexistuje ■ všechny domény jsou jednoprvkové => máme řešení ■ v obecném případě se alespoň zmenší prohledávaný prostor NE NE Hana Rudová, Logické programování I, 29. dubna 201 2 Algoritmy pro CSP k-konzistence Silná k-konzistence Mají NC a AC něco společného? ■ NC: konzistence jedné proměnné ■ AC: konzistence dvou proměnných "... můžeme pokračovat CSPje 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é 4-konzistentní graf ■ Pro obecné CSP, tedy i pro nebinární podmínky Hana Rudová, Logické programování I, 29. dubna 2012 17 Algoritmy pro CSP 3-konzistentní graf (1.1) lze rozšířit na (1,1,1) (2.2) lze rozšířit na (2,2,2) 1,2 _ 1,2 _ 1 ?3 není 2-konzistentní (3) nelze rozšířit (1,3) ani (2,3) nejsou konzistentní dvojice (nerozšiřujeme je) ■ 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 =fr silná k-konzistence ■ NC = silná 1-konzistence = 1-konzistence ■ AC = (silná) 2-konzistence Hana Rudová, Logické programování I, 29. dubna 201 2 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í? ■ silná n-konzistence je nutná pro graf s n vrcholy ■ n-konzistence nestačí (viz předchozí příklad) ■ silná k-konzistence pro k min(A) = min(B)+min(C), max(A) = max(B)+max(C) min(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) ■ změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) ■ změna max(A)vyvolá pouze změnu max(B) amax(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 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 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 D j 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(Dí) < yi < max(Dj) ■ 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)+l, max(B) = max(A)-l ■ 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 ■ podobně: A #< B, A #>= B, A #=< B Hana Rudová, Logické programování I, 29. dubna 201 2 22 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, 29. dubna 2012 23 Algoritmy pro CSP Hana Rudová, Logické programování I, 29. dubna 2012 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: V{Xi,.. .,Xk} c V : card{Di u ■ ■ ■ u Dk} > k stačí hledat Hallův interval J: velikost intervalu / je rovna počtu proměnných, jejichž doména je v J Inferenční pravidlo ■ U = {Xi,...,Xk}, dom(U) = {Di u ■ ■ ■ uDk] ' card(U) = card(dom(U)) ^Vve dom(U), VX e (V - U),X ± v * hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Složitost: 0(2") - hledání všech podmnožin množiny n proměnných (naivní) O(nlogn) - kontrola hraničních bodů Hallových intervalů (1 998) učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Hana Rudová, Logické programování I, 29. dubna 201 2 25 Algoritmy pro CSP