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, 30. dubna 2013 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, 30. dubna 2013 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, 3G. dubna 2G13 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, 30. dubna 2013 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, 30. dubna 2013 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, 30. dubna 2013 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, 30. dubna 2013 3 CLP(FD) Výber hodnoty JS> Obecný princip výběru hodnoty: první úspech (succeed first) j* volíme poradí tak, abychom výběr nemuseli opakovat ?- domain([A,B,C],1,2), A#=B+C. Hana Rudová, Logické programování I, 30. dubna 2013 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, 30. dubna 2013 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. labeling([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, 30. dubna 2013 4 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 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. labeling([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í C- Parametry labeling/2 rídící, jak je výber hodnoty realizován J- step: volba mezi X #= M, X #\= M (default) viz drívejší príklad u "Usporádání hodnot a promenných" 3» enum: vícenásobná volba mezi všemi hodnotami v doméne podobne jako pri indomain/1 Hana Rudová, Logické programování I, 30. dubna 2013 4 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 ?- domain([A,B,C],1,3), A#<3, A#=B+C. Hana Rudová, Logické programování I, 30. dubna 2013 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, 30. dubna 2013 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, 30. dubna 2013 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 & 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 -fc ffc: s (1) nejmenší velikostí domény (2) největším množstvím omezením „cekajících" na proměnné fd_degree(Var,Size) (3) nejlevější z nich J* min/max: s (1) nějmenší/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) řešení (předpokládejme minimalizaci) Parametry labeling/2 pro optimalizaci: minirrrize(F)/maxirrrize(F) iľ Cena #= A+B+C, labeling([minimize(Cena)], [A,B,C]) Metoda vetví a mezí (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# 0 c4: x2 + x5 - x6 = 0 Hana Rudová, Logické programování I, 30. dubna 2013 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 proměnné JS> Graf podmínek pro binární CSP není nutné uvažovat hypergraf, stací graf (podmínka spojuje pouze dva vrcholy) Hana Rudová, Logické programování I, 30. dubna 2013 9 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, 30. dubna 2013 9 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 lzě 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é 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 i. príklad: all_distinct vs. množina binárních nerovností Hana Rudová, Logické programování I, 30. dubna 2013 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í Hana Rudová, Logické programování I, 30. dubna 2013 10 Algoritmy pro CSP Vrcholová a hranová konzistence & Vrcholová konzistence (node consistency) NC it každá hodnota z aktuální domény Ví proměnné splnuje všechny unární podmínky s proměnnou Ví & Hranová konzistence (arc consistency) AC pro binární CSP J* hrana (Ví,Vj) je hranove 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] splnuje všechny binární podmínky nad Ví,Vj. Hana Rudová, Logické programování I, 30. dubna 2013 10 Algoritmy pro CSP Vrcholová a hranová konzistence Vrcholová konzistence (node consistency) NC -fc každá hodnota z aktuální domény Vi proměnné splnuje všechny unární podmínky s proměnnou Vi Hranová konzistence (arc consistency) AC pro binární CSP J* hrana (Vi,Vj) je hranove konzistentní, právě 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 smerová 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, 30. dubna 2013 11 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, 30. dubna 2013 11 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, 30. dubna 2013 11 Algoritmy pro CSP Algoritmus revize hrany & Jak udělat hranu (Vi,Vj) hranově 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 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 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, 30. dubna 2013 11 Algoritmy pro CSP Dosažení hranové konzistence problému Jak udělat CSP hranově konzistentní? Jt revize je potreba opakovat, dokud se mění doména nějaké proměnné s> 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 Hana Rudová, Logické programování I, 30. dubna 2013 12 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, 30. dubna 2013 12 Algoritmy pro CSP Algoritmus AG-B 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, 30. dubna 2013 Algoritmy pro CSP Algoritmus AC-3 procedure AC-3(G) ____^ Vk *^ Vm Q : = ) I ) g 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 {(í,k) g hrany(G), í = k, í = 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, 30. dubna 2013 14 Algoritmy pro CSP Jě hranová konzistěncě dostatěCná? 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í Hana Rudová, Logické programování I, 30. dubna 2013 14 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í Jaký je tedy význam AC? a nekdydár ešení p rímo nejaká 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ípade se alespon zmenší prohledávaný prostor Hana Rudová, Logické programování I, 30. dubna 2013 14 Algoritmy pro CSP k-konzistence Mají NC a AC neco spolecného? s NC: konzistence jedné promenné & AC: konzistence dvou proměnných ... mužeme pokracovat Hana Rudová, Logické programování I, 30. dubna 2013 15 Algoritmy pro CSP k-konzistence Mají NC a AC neco spoleCného? s> NC: konzistence jedné proměnné & AC: konzistence dvou proměnných ... mUžeme pokracovat CSP je k-konzistentní práve tehdy, když můžeme libovolné konzistentní ohodnocení (k-1) rUzných proměnných rozšířit do libovolné k-té promenné Hana Rudová, Logické programování I, 30. dubna 2013 15 Algoritmy pro CSP k-konzistěncě 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ž 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, 30. dubna 2013 15 4-konzistentní graf Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf 1,2 1,2 1,2,3 není 2-konzistentní Hana Rudová, Logické programování I, 30. dubna 2013 16 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, 30. dubna 2013 16 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) & CSP je silne k-konzistentní 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, 30. dubna 2013 16 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1,1) lze rozšírit na (1,1,1) 1,2 1,2 1,2,3 není 2-konzistentní (3) nelze rozšírit (2, 2) lze rozšírit na (2, 2,2) (1, 3) ani (2, 3) nejsou konzistentní dvojice (nerozširujeme je) & CSPje silne k-konzistentní 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 & NC = silná 1-konzistence = 1-konzistence & AC = (silná) 2-konzistence Hana Rudová, Logické programování I, 30. dubna 2013 16 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, 30. dubna 2013 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 řešení? a silná n-konzistence je nutná pro graf s n vrcholy n-konzistence nestac (viz predchozí príklad) Hana Rudová, Logické programování I, 30. dubna 2013 17 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