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, 7. května 2007 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, 7. května 2007 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, 7. května 2007 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 labeling/2 ovlivňující výběr proměnné ■ leftmost: nejlevější ■ ff: s (a) nejmenší velikostí domény (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é (c) nejlevější z nich ■ mi n/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) (default) fd_si ze(Var,Si ze) fd_deg ree(Var,Si ze) Hana Rudová, Logické programování I, 7. května 2007 CLP(FD) Algoritmy pro řešení problému splňování podmínek (CSP) Hledání optimálního řešení (předpokládejme minimalizaci) Parametry labeling/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) ■ 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 Hana Rudová, Logické programování I, 7. května 2007 CLP(FD) 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 - X6 > 0 C4 : X2 + Xs - X6 = 0 Hana Rudová, Logické programování I, 7. května 2007 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, 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 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í,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 Řešení nebinárních podmínek ■ S n-árními podmínkami se pracuje přímo ■ Podmínka je obecně hranově konzistentní (CAC), právě když pro každou proměnnou Ví z této podmínky a každou hodnou xeDj existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí ■ A + B = C, A in 1..3, B i n 2. . 4, Cin3..7je obecně hranově konzistentní ■ Využívá se sémantika podmínek ■ speciální typy konzistence pro globální omezení ■ viz al 1_di sti nct ■ konzistence mezí ■ propagace pouze při změně nejmenší a největší hodnoty v doméně proměnné ■ Pro různé podmínky lze použít různý druh konzistence ■ 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, 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) = 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 Hana Rudová, Logické programování I, 7. května 2007 16 Algoritmy pro CSP Globální podmínky Propagace pro all_distinct 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, 7. května 2007 Algoritmy pro CSP 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{D\ u ■ ■ ■ u Dk} > k stačí hledat Hallův interval J: velikost intervalu / je rovna počtu proměnných, jejichž doména je v I Inferenční pravidlo ■ U = {Xi,...,Xk}, dom(U) = {Di u ■ ■ ■ uDk] ■ card(U) = card(dom(U)) Vv e 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ů (1998) 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, 7. května 2007 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ě ■ 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ů Základní algoritmus prohledávání s navracením proměnné BT Backtracking (BT) kontroluje v kroku a podmínky c(Vi,Vfl),...,c(Vfl-i,Vfl) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky \^ c(V«,V«+i),...,c(Vfl,V„) z aktuální proměnné do budoucích proměnných Pohled dopředu (LA) kontroluje v kroku a podmínky ^ /I Vi(a < l < n), Vfe(a |uzly(G)| then return uzly(G) for V x e Da do if consistentCC,a) then % consistentCC,a) je nahrazeno FC, LA, ... R := Tabel ing(G,a +1) if R 4= 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 21 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šť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:={(Ví, V a) e hranyCC) , í < a] % hrany vedoucí do minulých proměnných Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vk,Vm) z Q Consistent := not revise(VJt, Vm) % pokud vyradí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 Hana Rudová, Logické programování I, 7. května 2007 22 Algoritmy pro CSP Příklad: backtracking ■ č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šťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami ■ proceduře FC(G,a) Q:={(V, V a) e hrany(G) , i > a] % přidání hran z aktuální proměnné do budoucích prom. Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (VJt,Vm) z Q if revi se((V(;, Vm)) then Consistent := (|Djt|>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 Pohled dopředu (LA - looking ahead) ■ LA je rozšíření FC, LA zajišť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) e h rany (C), í > a] % začináme s hranami do a Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (VJt,Vm) z Q if revi se((VJt, Vm)) then Q := Q u {(V;, Vit) I (V;, Vit) e hrany(G), í + k, í + m, í > 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 naAC-3, lze použít i jiné AC algoritmy Hana Rudová, Logické programování I, 7. května 2007 27 Algoritmy pro Příklad: kontrola dopředu ■ Omezení: Vlt V2, V3 in 1... 3, V1# = 3xV3 ■ Stavový prostor: Hana Rudová, Logické programování I, 7. května 2007 26 Algoritmy pro CSP Příklad: pohled dopředu ■ Omezení: V1,V2,V3 in 1... 4, Vx# > V2, V2#=3xV3 ■ Stavový prostor: Hana Rudová, Logické programování I, 7. května 2007 28 Algoritmy pro CSP