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, 30. dubna 2013 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, 30. dubna 201 3 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, 30. dubna 201 3 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, 30. dubna 2013 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, 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# 0 C4 : X2 + Xs - X6 = 0 Hana Rudová, Logické programování I, 30. dubna 201 3 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_distinct vs. množina binárních nerovností Hana Rudová, Logické programování I, 30. dubna 2013 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, 30. dubna 2013 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, 30. dubna 201 3 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, 30. dubna 201 3 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