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 2010 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 0 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í 1 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 ■ bisect: volba mezi X #=< Mid, X #> Mi d ■ vjednom kroku labelingu nedochází nutně k instanciaci proměnné Hana Rudová, Logické programování I, 29. dubna 2010 4 (default) (default) 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 Tabel i ng/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 2010 5 CLP(FD) Hledání optimálního řešení (předpokládejme minimalizaci) ■ Parametry 1 abel i ng/2 pro optimalizaci: minimize(F)/maximize(F) ■ Cena #= A+B+C, labeling([minimize(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í) ■ 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 ■ Iniciálně je Bound je předem známá nejhorší cena (např. krajní hodnota v doméně) branch_and_bound( Bound, Vars, Cost ) :- % triviálni implementace Cost #< Bound, findallC Vars-Cost, (labelingC Vars ), ! ), [ Solution-FoundCost ]), !, assertaC solutionC Solution, FoundCost ) ), branch_and_bound( FoundCost, Vars, Cost ). branch_and_bound( _, Vars, Cost ) :- solutionC Vars, Cost ), !. Hana Rudová, Logické programování I, 29. dubna 2010 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) 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é Xi.....Xe s doménou {0,1} ■ omezení C\ : Xi + x-i + Xe = 1 /X C2 I Xi - X3 + %4 = 1 C3 \ X4 + Xs - X% > 0 C4 : X2 + Xs - X6 = 0 Hana Rudová, Logické programování I, 29. dubna 2010 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: a"l"l_different vs. množina binárních nerovností Hana Rudová, Logické programování I, 29. dubna 2010 9 Algoritmy pro CSP Algoritmus revize hrany Jak udělat hranu (Vj, V,) hranově konzistentní? Z domény Dí vyřadím takové hodnoty x, které nejsou konzistentní s aktuální doménou D, (pro x neexistuje žádá hodnoty y v D, tak, aby ohodnocení Vi = x a Vj■ = y splňovalo všechny binární podmínky mezi Ví a Vj) proceduře revise((í,j)) Deleted := falše for V x in Dí do if neexistuje y e Dj takové, že (x,y) je konzistentní then Dí := Dí - {x\ Deleted := true end i f return Deleted end revise domain([Vi, V21,2 ,4) , Vľ#< V2 revise((l,2)) smaže 4 z L>i,L>2 se nezmění Hana Rudová, Logické programování I, 29. dubna 2010 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 (Vj, 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 Vt,Vj. ■ hranová konzistence je směrová ■ konzistence hrany (Ví,Vj) nezaručuje konzistenci hrany (Vj,Ví) 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 0 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,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 Vj < 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 2010 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 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 2010 20 Algoritmy pro CSP Konzistence mezí a aritmetická omezení Globální podmínky ■ 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) amin(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 ■ 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: ■ a"l"l_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 2010 21 Algoritmy pro CSP Hana Rudová, Logické programování I, 29. dubna 2010 22 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{Ai,.. .,Xk} c V : card{Dx 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) Hana Rudová, Logické programování I, 29. dubna 2010 23 Algoritmy pro CSP učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6