CLP(FD) - prohledávání Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnoty jsou instanciovány pri backtrackingu ve vzrůstajícím poradí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? Hana Rudová, Logické programování I, 26. dubna 2011 2 CLP(FD) Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnoty jsou instanciovány pri backtrackingu ve vzrůstajícím poradí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? labeling( [] ). labeling( [Var|Rest] ) :- % výběr nejlevější proměnné k instanciaci indomain( Var ), % výběr hodnot ve vzrUstajícím poradí labeling( Rest ). Hana Rudová, Logické programování I, 26. dubna 2011 2 CLP(FD) Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnoty jsou instanciovány pri backtrackingu ve vzrůstajícím poradí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? labeling( [] ). labeling( [Var|Rest] ) :- % výběr nejlevější proměnné k instanciaci indomain( Var ), % výběr hodnot ve vzrUstajícím poradí labeling( Rest ). labeling( Options, Variables ) ľ- A in G..2, B in G..2, B#< A, 1abe1ing([], [A,B]). Hana Rudová, Logické programování I, 26. dubna 2011 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 labeling( [] ). labeling( Variables ) :- select_variable(Variables,Var,Rest), select_value(Var,Value), Hana Rudová, Logické programování I, 26. dubna 2011 3 CLP(FD) Uspořádání hodnot a proměnných & Pri prohledávání je rozhodující uspořádání hodnot a proměnných UrCujíje heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) select_van'able(Van'ables,Var,Rest), select_value(Var,Value), ( Var #= Value, labeling( Rest ) Hana Rudová, Logické programování I, 26. dubna 2011 3 CLP(FD) Usporádání hodnot a proměnných & Pri prohledávání je rozhodující usporádání hodnot a proměnných Urcujíje hěuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) :- select_variableCVariables,Var,Rest), select_value(Var,Value), ( Var #= Value, labeling( Rest ) Var #\= Value , % nemusí dojít k instanciaci Var labeling( Variables ) % proto pokracujeme se všemi promennými vcetne Var Hana Rudová, Logické programování I, 26. dubna 2011 3 CLP(FD) Uspořádání hodnot a proměnných & Pri prohledávání je rozhodující uspořádání hodnot a proměnných UrCujíje heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) select_van'able(Van'ables,Var,Rest), select_value(Var,Value), ( Var #= Value, labeling( Rest ) Var #\= Value , % nemusí dojít k instanciaci Var labeling( Variables ) % proto pokraCujeme se všemi proměnnými vCetne Var & Statické usporádání: urCeno už pred prohledáváním JS> Dynamické usporádání: poCítá se behem prohledávání Hana Rudová, LogiCké programování I, 26. dubna 2011 3 CLP(FD) Výber hodnoty JS> Obecný princip výberu hodnoty: první úspech (succeed first) J* volíme poradí tak, abychom výber nemuseli opakovat ?- domain([A,B,C],1,2), A#=B+C. Hana Rudová, Logické programování I, 26. dubna 2011 4 CLP(FD) Výběr hodnoty JS> Obecný princip výběru hodnoty: první úspěch (succeed first) J* volíme poradí tak, abychom výběr nemuseli opakovat a ?- domain([A,B,C],1,2), A#=B+C. optimální výber A=2,B=1,C=1 je bez backtrackingu Hana Rudová, Logické programování I, 26. dubna 2011 4 CLP(FD) Výběr hodnoty JS> Obecný princip výběru hodnoty: první úspěch (succeed first) J* volíme poradí tak, abychom výběr nemuseli opakovat a ?- domain([A,B,C],1,2), A#=B+C. optimální výber A=2,B=1,C=1 je bez backtrackingu & Parametry labeling/2 ovlivnující výber hodnoty pr. labe1ing([down], Vars) -i- up: doména procházena ve vzrůstajícím poradí (default) -fc down: doména procházena v klesajícím poradí Hana Rudová, Logické programování I, 26. dubna 2011 4 CLP(FD) Výběr hodnoty JS> Obecný princip výběru hodnoty: první úspěch (succeed first) J> volíme poradí tak, abychom výběr nemuseli opakovat a ?- domain([A,B,C],1,2), A#=B+C. optimální výběr A=2,B=1,C=1 je bez backtrackingu & Parametry labeling/2 ovlivnující výběr hodnoty pr. 1abe1ing([down], Vars) -i- up: doména procházena ve vzrůstajícím poradí (default) down: doména procházena v klesajícím poradí Parametry labeling/2 rídící, jak je výběr hodnoty realizován step: volba mezi X #= M, X #\= M (default) viz drívější príklad u "Usporádání hodnot a proměnných" S enum: vícenásobná volba mezi všemi hodnotami v doméně podobně jako pri indomain/1 Hana Rudová, Logické programování I, 26. dubna 2011 4 CLP(FD) Výběr proměnné ObeCný prinCip výberu promenné: first-fail výber promenné, pro kterou je nejobtížnejší nalézt správnou hodnotu pozdejší výber hodnoty pro tuto promennou by snadneji vedl k failu A výbereme promennou s nějměnší doménou ?- domain([A,B,C],1,3), A#<3, A#=B+C. Hana Rudová, LogiCké programování I, 26. dubna 2011 5 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 ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je zaCít s výběrem A Hana Rudová, Logické programování I, 26. dubna 2011 5 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 A výbereme proměnnou s nějměnší doménou J* ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je zaCít s výběrem A Parametry labeling/2 ovlivnující výběr proměnné -i- leftmost: nejlevější (default) M 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 Hana Rudová, Logické programování I, 26. dubna 2011 5 CLP(FD) Výběr proměnné Obecný princip výběru proměnné: first-fail výber promenné, pro kterou je nejobtížnejší nalézt správnou hodnotu pozdejší výber hodnoty pro tuto promennou by snadneji vedl k failu výbereme promennou s nějměnší doménou ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je zaCít s výberem A & Parametry labeling/2 ovlivnujíCí výber promenné -i- leftmost: nejlevejší (default) M ff: s (1) nejmenší velikostí domény fd_size(Var,Size) (2) (pokud s nejmenší velikostí domény víCe, tak) nejlevejší z niCh S> ffc: s (1) nejmenší velikostí domény (2) nejvetším množstvím omezením „CekajíCíCh" na promenné fd_degree(Var,Size) (3) nejlevejší z niCh min/max: s (1) nejmenší/nejvetší hodnotou v doméne promenné (2) nejlevnejšíz niCh fd_rrnn(Var,Min)/fd_max(Var,Max) Hana Rudová, LogiCké programování I, 26. dubna 2011 5 CLP(FD) řěšění (prědpokládějmě minimalizaci) Parametry labeling/2 pro optimalizaCi: minirrrize(F)/maxirrrize(F) iľ Cena #= A+B+C, labeling([minimize(Cena)], [A,B,C]) Mětoda větví a mězí (branch&bound) -fc algoritmus, který implementuje proCeduru pro minimalizaCi (duálne pro maximalizaCi) -i- uvažujeme nejhorší možnou Cenu r ešení UB (nap r . Cena už nalezeného rešení) & poCítáme dolní odhad LB Ceny CásteCného r ešení LB je tedy nejlepší možná Cena pro rozšír ení tohoto r ešení proCházíme strom a vyžadujeme, aby prozkoumávaná vetev mela Cenu LB < UB pokud je LB > UB, tak víme, že v této vetvi není lepší rešení a od r ízneme ji p r idává se tedy inkrementálne omezení LB#= S+D, after(Ss, Ds, E). Hana Rudová, Logické programování I, 26. dubna 2011 7 CLP(FD) Príklad: kumulativní rozvrhování Vytvo rte rozvrh pro následující úlohy, tak aby nebyla p rekrocena kapacita 13 zdroje, a minimalizujte celkovou dobu trvání úloha doba trvání kapacita t1 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 t7 4 11 Hana Rudová, Logické programování I, 26. dubna 2011 schedule(Ss, End) length(Ss, 7), Ds = [16, 6, 13, 7, 5, 18, 4], Rs = [ 2, 9, 3, 7, 10, 1, 11], domain(Ss, 0, 51), domain([End], 0, 69), after(Ss, Ds, End), % koncový cas cumulative(Ss, Ds, Rs, 13), append(Ss, [End], Vars), labeling([minimize(End)], Vars). after([], [], _). after([S|Ss], [D|Ds], E) E #>= S+D, after(Ss, Ds, E). | ?- schedule(Ss, End). Ss = Ss = [0,16,9,9,4,4,0], End = 22 ? 7 CLP(FD) Algoritmy pro rěšění problému splnování podmíněk (CSP) Grafová reprezentace CSP & Reprezentace podmínek & intenzionální (matematická/logická formule) J* extenzionální (výcet k-tic kompatibilních hodnot, 0-1 matice) Hana Rudová, Logické programování I, 26. dubna 2011 9 Algoritmy pro CSP Grafová rěprězěntacě CSP Rěprězěntacě podmíněk & intenzionální (matematická/logická formule) & extenzionální (výcet k-tic kompatibilních hodnot, 0-1 matice) Graf: vrcholy, hrany (hrana spojuje dva vrcholy) Hypěrgraf: vrcholy, hrany (hrana spojuje množinu vrcholu) Reprezentace CSP pomocí hypěrgrafu podmíněk a- vrchol = proměnná, hyperhrana = podmínka Hana Rudová, Logické programování I, 26. dubna 2011 9 Algoritmy pro CSP Grafová reprezentace CSP Reprezentace podmínek & intenzionální (matematická/logická formule) J* extenzionální (výCet k-tic kompatibilních hodnot, 0-1 matice) Graf: vrcholy, hrany (hrana spojuje dva vrcholy) Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholU) Reprezentace CSP pomocí hypergrafu podmínek vrchol = promenná, hyperhrana = podmínka Cl Príklad promenné x1,...,x6 s doménou {0,1} omezení c1 : x1 + x2 + x6 = 1 c2: x1 - x3 + x4 = 1 c3 : x4 + x5 - x6 > 0 c4: x2 + x5 - x6 = 0 Hana Rudová, Logické programování I, 26. dubna 2011 3 Algoritmy pro CSP Binární CSP M Binární CSP i* CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény promenné JS> Graf podmínek pro binární CSP a není nutné uvažovat hypergraf, staCí graf (podmínka spojuje pouze dva vrcholy) Hana Rudová, Logické programování I, 26. dubna 2011 10 Algoritmy pro CSP Binární CSP M Binární CSP i* CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény proměnné JS> Graf podmínek pro binární CSP není nutné uvažovat hypergraf, stací graf (podmínka spojuje pouze dva vrcholy) & Každý CSP lze transformovat na "korespondující" binární CSP ii> Výhody a nevýhody binarizace 3 získáváme unifikovaný tvar CSP problému, rada algoritmu navržena pro binární CSP -fc bohužel ale znaCné zvetšení velikosti problému Hana Rudová, Logické programování I, 26. dubna 2011 10 Algoritmy pro CSP Binární CSP M Binární CSP i* CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény proměnné JS> Graf podmíněk pro binární CSP není nutné uvažovat hypergraf, stací graf (podmínka spojuje pouze dva vrcholy) & Každý CSP lzě transformovat na "korěspondující" binární CSP ii> Výhody a nevýhody binarizace 3 získáváme unifikovaný tvar CSP problému, rada algoritmu navržena pro binární CSP -fc bohužel ale znacné zvětšení velikosti problému JS> Nebinární podmínky a složitější propagacní algoritmy lze využít jejich sémantiky pro lepší propagaci X príklad: a11_different vs. množina binárních nerovností Hana Rudová, Logické programování I, 26. dubna 2011 10 Algoritmy pro CSP Vrcholová a hranová konzistěncě & Vrcholová konzistěncě (node consistency) NC -fc každá hodnota z aktuální domény Vi promenné splnuje všeChny unární podmínky s promennou Vi Hana Rudová, LogiCké programování I, 26. dubna 2011 11 Algoritmy pro CSP Vrcholová a hranová konzistence & Vrcholová konzistence (node consistency) NC -fc každá hodnota z aktuální domény Vi promenné splnuje všechny unární podmínky s promennou Vi & Hranová konzistence (arc consistency) AC pro binární CSP J* hrana (Vi,Vj) je hranove konzistentní, práve když pro každou hodnotu x z aktuální domény Di existuje hodnota y tak, že ohodnocení [Vi = x,Vj = y] splnuje všechny binární podmínky nad Vi,Vj. Hana Rudová, Logické programování I, 26. dubna 2011 11 Algoritmy pro CSP Vrcholová a hranová konzistěncě Vrcholová konzistěncě (node consistency) NC -fc každá hodnota z aktuální domény Vi promenné splnuje všeChny unární podmínky s promennou Vi Hranová konzistěncě (arc consistency) AC pro binární CSP J* hřana (Vi,Vj) jě hranově konzistěntní, práve když pro každou hodnotu x z aktuální domény Di existuje hodnota y tak, že ohodnoCení [Vi = x,Vj = y] splnuje všeChny binární podmínky nad Vi,Vj. a hranová konzistenCe je směrová konzistenCe hrany (Vi,Vj) nezaruCuje konzistenCi hrany (Vj,Vi) A I 3..7 A procedure revise((i,j)) Deleted := false for V x in Dl do if neexistuje y g Dj takové, že (x,y) je konzistentní then Di := Di - {x} Deleted := true end if return Deleted end revise Hana Rudová, Logické programování I, 26. dubna 2011 12 Algoritmy pro CSP Algoritmus revize hrany & Jak udělat hranu (Vi,Vj) hranově konzistentní? -í* Z domény Di vyřadím takové hodnoty x, které nejsou konzistentní s aktuální doménou Dj (pro x neexistuje žádá hodnoty y v Dj tak, aby ohodnocení Vi = x a Vj = y spinovalo všechny binární podmínky mezi Vl a Vj) JS> procedure revise((i,j)) Deleted := false for V x in Dl do if neexistuje y g Dj takové, že (x,y) je konzistentní then Di := Di - {x} Deleted := true end if return Deleted end revise M domain([Vi,V2],2,4), Vi#< V2 Hana Rudová, Logické programování I, 26. dubna 2011 12 Algoritmy pro CSP Algoritmus revize hrany & Jak udělat hranu (Vi,Vj) hranově konzistentní? -í* Z domény Di vyřadím takové hodnoty x, které nejsou konzistentní s aktuální doménou Dj (pro x neexistuje žádá hodnoty y v Dj tak, aby ohodnocení Vi = x a Vj = y spinovalo všechny binární podmínky mezi Vl a Vj) JS> procedure revise((i,j)) Deleted := false for V x in Dl do if neexistuje y g Dj takové, že (x,y) je konzistentní then Di := Di - {x} Deleted := true end if return Deleted end revise M domain([Vi, V2],2,4), Vi#< V2 revise((1,2)) smaže 4 z Di, Hana Rudová, Logické programování I, 26. dubna 2011 12 Algoritmy pro CSP Algoritmus revize hrany & Jak udelat hranu (Vi,Vj) hranove konzistentní? -í* Z domény Di vyradím takové hodnoty x, které nejsou konzistentní s aktuální doménou Dj (pro x neexistuje žádá hodnoty y v Dj tak, aby ohodnocení Vi = x a Vj = y splnovalo všechny binární podmínky mezi Vi a Vj) JS> proceduře revise((i,j)) Deleted := false for V x in Di do if neexistuje y g Dj takové, že (x,y) je konzistentní then Di := Di - {x} Deleted := true end if return Deleted end revise JS> domain([Vi, V2],2,4), Vi#< V2 revise((1,2)) smaže 4 z Di,D2 se nezmení Hana Rudová, Logické programování I, 26. dubna 2011 12 AlgoritmyproCSP Dosažění hranové konzistěncě problému JS> Jak udělat CSP hranově konzistentní? a revize je potreba opakovat, dokud se mění doména nějaké proměnné a efektivnější: opakování revizí mužeme dělat pomocí fronty pridáváme do ní hrany, jejichž konzistence mohla být narušena zmenšením domény Hana Rudová, Logické programování I, 26. dubna 2011 13 Algoritmy pro CSP Dosažení hranové konzistence problému Jak udělat CSP hranově konzistentní? a revize je potreba opakovat, dokud se mění doména nějaké proměnné a efektivnější: opakování revizí mUžeme dělat pomocí fronty pridávame do ní hrany, jejichž konzistence mohla být narušena zmenšením domény Jaké hrany presně revidovat po zmenšení domény? ty, jejichž konzistence mUže být zmenšením domény proměnné narušena jsou to hrany (i,k), které vedou do proměnné Vk se zmenšenou doménou V < V k m hranu (m, k) vedoucí z proměnné Vm, která zmenšení domény způsobila, není treba revidovat (změna se jí nedotkne) Hana Rudová, Logické programování I, 26. dubna 2011 13 Algoritmy pro CSP Algoritmus AC-3 procedure AC-3(G) ____^ Vk *^ Vm Q := {(i,j) | (i,j) £ hrany(G), í = j} % seznam hran pro revizi while Q non empty do vyber a smaž (k, m) z Q if revise((k, m)) then % pridani pouze hran, ktere Q := Q u {(i,k) g hrany(G), i = k, i = m} % dosud nejsou ve fronte end while end AC-3 Hana Rudová, Logické programování I, 26. dubna 2011 14 Algoritmy pro CSP Algoritmus AC-3 procedure AC-3(G) ____^ Vk *^ Vm Q := {(i,j) | (i,j) g hrany(G), i = j} % seznam hran pro revizi while Q non empty do vyber a smaž (k,m) z Q if revise((k,m)) then % pridani pouze hran, ktere Q := Q u {(i,k) g hrany(G), i = k, i = m} % dosud nejsou ve fronte end while end AC-3 Príklad: A Víme alespon zda r ešení existuje? NE Hana Rudová, LogiCké programování I, 26. dubna 2011 15 Algoritmy pro CSP Je hranová konzistence dostatecná? Použitím AC odstraníme mnoho nekompatibilních hodnot a Dostaneme potom rešení problému? NE %> Víme alespon zda r ešení existuje? NE domain([X,Y,Z],1,2), X#\= Y, Y#\= Z, Z#\= X a hranove konzistentní a nemá žádné r ešení Hana Rudová, Logické programování I, 26. dubna 2011 15 Algoritmy pro CSP Je hranová konzistence dostatecná? Použitím AC odstraníme mnoho nekompatibilních hodnot a Dostaneme potom rešení problému? NE %> Víme alespon zda r ešení existuje? NE domain([X,Y,Z],1,2), X#\= Y, Y#\= Z, Z#\= X a hranově konzistentní a nemá žádné r ešení Jaký je tedy význam AC? a někdy dá r ešení p rímo nějaká doména se vyprázdní ^ rešení neexistuje všechny domény jsou jednoprvkové ^ máme r ešení a v obecném p rípadě se alespon zmenší prohledávaný prostor Hana Rudová, Logické programování I, 26. dubna 2011 15 Algoritmy pro CSP k-konzistence Mají NC a AC neco spolecného? s NC: konzistence jedné promenné & AC: konzistence dvou promenných ... mužeme pokracovat Hana Rudová, Logické programování I, 26. dubna 2011 16 Algoritmy pro CSP k-konzistence Mají NC a AC něco společného? s NC: konzistence jedné proměnné & AC: konzistence dvou proměnných ... mUžeme pokračovat CSP je k-konzistentní práve tehdy, když můžeme libovolné konzistentní ohodnocení (k-1) rUzných promenných rozšířit do libovolné k-té promenné Hana Rudová, Logické programování I, 26. dubna 2011 16 Algoritmy pro CSP k-konzistence Mají NC a AC neco spoleCného? s> NC: konzistence jedné proměnné & AC: konzistence dvou promenných ... mUžeme pokracovat CSP je k-konzistěntní práve tehdy, když mUžeme libovolné konzistentní ohodnocení (k-1) rUzných promenných rozšířit do libovolné k-té promenné 1,2,3 1,2,3 1,2,3 4 -í* Pro obecné CSP, tedy i pro nebinární podmínky Hana Rudová, Logické programování I, 26. dubna 2011 16 4-konzistentní graf Algoritmy pro CSP Silná k-konzistěncě 3-konzistentní graf 1,2 1,2 1,2,3 není 2-konzistentní Hana Rudová, LogiCké programování I, 26. dubna 2011 17 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1,1) lze rozšírit na (1,1,1) (2, 2) lze rozšírit na (2, 2,2) 1,2 1,2 1,2,3 není 2-konzistentní (3) nelze rozšírit (1, 3) ani (2, 3) nejsou konzistentní dvojice (nerozširujeme je) Hana Rudová, Logické programování I, 26. dubna 2011 17 Algoritmy pro CSP Silná k-konzistěncě 3-konzistentní graf (1,1) lze rozšír it na (1,1,1) (2, 2) lze rozšír it na (2, 2,2) 1,2 1,2 1,2,3 není 2-konzistentní (3) nelze rozšír it (1, 3) ani (2, 3) nejsou konzistentní dvojiCe (nerozši r ujeme je) & CSPje silně k-konzistěntní práve 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, 26. dubna 2011 17 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1,1) lze rozšír it na (1,1,1) 1,2 1,2 1,2,3 není 2-konzistentní (3) nelze rozšír it (2, 2) lze rozšír it na (2, 2,2) (1, 3) ani (2, 3) nejsou konzistentní dvojice (nerozši r ujeme je) & CSPje silne 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, 26. dubna 2011 17 Algoritmy pro CSP Konzistence pro nalezení rešení Máme-li graf s n vrcholy, jak silnou konzistenci potrebujeme, abychom prímo našli rešení? a silná n-konzistence je nutná pro graf s n vrcholy Hana Rudová, Logické programování I, 26. dubna 2011 18 Algoritmy pro CSP Konzistěncě pro nalězění řěšění Máme-li graf s n vrCholy, jak silnou konzistenCi potrebujeme, abyChom p rímo našli rešení? ifc silná n-konzistenCe je nutná pro graf s n vrCholy n-konzistenCe nestaCí (viz p r edChozí p ríklad) Hana Rudová, LogiCké programování I, 26. dubna 2011 18 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í? a silná n-konzistence je nutná pro graf s n vrcholy n-konzistence nestací (viz predchozí príklad) silná k-konzistence pro k speCiální typy konzistenCe pro globální omezení ±* viz all_distinct a konzistenCe mezí propagaCe pouze p r i zmene nejmenší a nejvetší hodnoty v doméne promenné C- Pro různé podmínky lze použít mzný druh konzistenCe & A# Propagaci pres globální podmínku rešíme speciálním algoritmem navrženým pro danou podmínku C Príklady: M all_different omezení: hodnoty všech promenných různé serialized omezení: rozvržení úloh zadaných startovním casem a dobou trvání tak, aby se neprekrývaly Hana Rudová, Logické programování I, 26. dubna 2011 21 Algoritmy pro CSP Propagace pro all_distinct -I U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 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, 26. dubna 2011 22 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) ucitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 26. dubna 2011 22 Algoritmy pro CSP Propagace pro all_distinct -I U = {X2, X4, X5}, dom(U) = {2,3,4} nelze pro X1, X1 in 5..6, X3 = 5, & Konzistence: V[X\,... ,Xk} 2, 3, 4}: X3, X6 X6 in {1} \/ (5..6) c V : card{Di u • • • u Dk} > k 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, 26. dubna 2011 22 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max {2,3,4} nelze pro X1, X3, X6 Jan 3 6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Petr 4 Konzistence: \/{X1,.. .,Xk} c V : card{D1 u • • • u Dk} > k Anna 2 5 stací hledat Hallův interval I: velikost intervalu I je rovna Ota 4 poctu promenných, jejichž doména je v I Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 26. dubna 2011 22 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: V{X1,.. .,Xk} c V : card{D1 u • • • u Dk} > k stací hledat Hallův interval I: velikost intervalu I je rovna poctu proměnných, jejichž doména je v I Inferencní pravidlo U = {X1,...,Xk}, dom(U) = {D1 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, 26. dubna 2011 22 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: V{X1,.. .,Xk} c V : card{D1 u • • • u Dk} > k stací hledat Hallův interval I: velikost intervalu I je rovna poctu proměnných, jejichž doména je v I Inferencní pravidlo U = {X1,...,Xk}, dom(U) = {D1 u • • • u Dk} card(U) = card(dom(U)) => Vv e dom(U), VX e (V - U),X = v s» hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné ucitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 26. dubna 2011 22 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: \/{Xi,.. .,Xk} c V : card{Di u • • • u Dk} > k stací hledat Hallův interval I: velikost intervalu I je rovna poctu proměnných, jejichž doména je v I InferenCní pravidlo U = {Xu...,Xk}, dom(U) = {Di u • • • u Dk} card(U) = card(dom(U)) => Vv g dom(U), VX g (V - U),X = v a hodnoty v Hallove intervalu jsou pro ostatní promenné nedostupné učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Složitost: O(2n) - hledání všech podmnožin množiny n proměnných (naivní) Hana Rudová, Logické programování I, 26. dubna 2011 22 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: \/{Xi,.. .,Xk} c V : card{D1 u • • • u Dk} > k stací hledat Hallův interval I: velikost intervalu I je rovna poctu proměnných, jejichž doména je v I Inferencní pravidlo U = {Xu...,Xk}, dom(U) = {Di u • • • u Dk} card(U) = card(dom(U)) => Vv g dom(U), VX g (V - U),X = v s» hodnoty v Hallove intervalu jsou pro ostatní promenné nedostupné Složitost: O(2n) - hledání všech podmnožin množiny n proměnných (naivní) O(nlogn) - kontrola hranicních bodu Hallových intervalu (1998) 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, 26. dubna 2011 22 Algoritmy pro CSP