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, 26. dubna 2011 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, 26. dubna 201 1 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, 26. dubna 201 1
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, 26. dubna 2011 5 CLP(FD)
Příklad: kumulativní rozvrhování
Vytvořte rozvrh pro následující úlohy, tak aby nebyla překročena kapacita 1 3 zdroje, a minimalizujte celkovou dobu trvání
úloha	doba trvání	kapacita
tl	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
scheduleCSs, End) :-TengthCSs, 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), afterCSs, Ds, End),      % koncový čas cumulativeCSs , Ds, Rs , 13), appendCSs,  [End], Vars), labe]ing([minimize(End)], Vars).
after([],  [] , _) . after([S|Ss], [D|Ds], E) :-
E #>= S+D, afterCSs, Ds, E).
| ?-   scheduleCSs, End).
Ss = Ss = [0,16,9,9,4,4,0], End = 22 ?
7 CLP(FD)
Hledání optimálního řešení (předpokládejme minimalizaci)
Parametry labeling/2 pro optimalizaci: minimize(F)/maximize(F)
■ Cena #= A+B+C, ]abe]ing([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#<UB pro snižující se UB tak, jak nalézáme kvalitnější řešení
Hana Rudová, Logické programování I, 26. dubna 201 1 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)
Graf: vrcholy, hrany (hrana spojuje dva vrcholy) Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) Reprezentace CSP pomocí hypergrafu podmínek
■ vrchol = proměnná, hyperhrana = podmínka
Hana Rudová, Logické programování I, 26. dubna 2011 9 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: all_different vs. množina binárních nerovností
Hana Rudová, Logické programování I, 26. dubna 201 1 10 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, V, = y] splňuje všechny binární podmínky nad Vu V,.
■ hranová konzistence je směrová
■ konzistence hrany (Ví, Vj) nezaručuje konzistenci hrany (Vj,Ví)
» l„     I A<B rr—ti „      . rr—n «<D i——-i _      . r-—-i n<D i——-i _
A|3..7|<= = ŕj1-5| B   A|3..4|<--J|1..5| B   A|3..4|«    ft|4..5| B
A<B
A<B
konzistence (A,B)     konzistence (A,B) i (B,A) ■ CSP je hranově konzistentní, právě když
jsou všechny jeho hrany (v obou směrech) hranově konzistentní
Hana Rudová, Logické programování I, 26. dubna 2011
Algoritmy pro CSP
Algoritmus revize hrany
Jak udělat hranu (Ví, 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 j tak, aby ohodnocení Ví = x a Vj■ = y splňovalo všechny binární podmínky mezi Ví a V,)
proceduře revise((í,j)) Deleted := false for V x in Dí do
if neexistuje y e Dj takové, že (x,y) je konzistentní
then Dí := Dí - {x} Deleted := true
end if return Deleted end revise
domai n( [Vi, V2I , 2 ,4) , Vi#< V2     revise((l,2)) smaže 4 z Di,Ľ2 se nezmění
Hana Rudová, Logické programování I, 26. dubna 201 1
Algoritmy pro CSP
Dosažení hranové konzistence problému
Jak udělat CSP hranově konzistentní?
■ revize je potřeba opakovat, dokud se mění doména nějaké proměnné
■ efektivnější: opakování revizí můžeme dělat pomocí fronty
■ přidáváme do ní hrany, jejichž konzistence mohla být narušena zmenšením domény
Jaké hrany přesně revidovat po zmenšení domény?
■ ty, jejichž konzistence může být zmenšením domény proměnné narušena jsou to hrany (i, fe), které vedou do proměnné     se zmenšenou doménou
hranu (m,k) vedoucí z proměnné Vm, která zmenšení domény způsobila, není třeba revidovat (změna sejí nedotkne)
Hana Rudová, Logické programování I, 26. dubna 2011
Algoritmy pro CSP
Algoritmus AC-3
v; <   > v
1 proceduře AC-3CC) Q := {(íij)  I (í.j) e hranyCC), í £ j}      % seznam hran pro revizi while Q non empty do
vyber a smaž (fc,m) z Q
if revise((fc,m)) then % přidáni pouze hran, které
Q := Q u {(í, k)  e hrany(G), í 4= k, íj=m}      % dosud nejsou ve fronte end while end AC-3
A<B, B<C:  (3. .7,1..5,1..5) - (3■.4,1..5,1.■5) -
(3..4,4^5,1..5) - (3.-4,4,1^5) - (3^4,4,5) ~* (3,4,5)
1 Technika AC-3 je dnes asi nejpoužívánější, ale stále není optimální
1 Jaké budou domény A,B,C po AC-3 pro: domain([A,B,C] ,1,10), A #= B + 1, C #< B
Hana Rudová, Logické programování I, 26. dubna 201 1 14 Algoritmy pro CSP
Je hranová konzistence dostatečná?
Použitím AC odstraníme mnoho nekompatibilních hodnot
■ Dostaneme potom řešení problému? NE
■ Víme alespoň zda řešení existuje? NE domain([X,Y,Z],1,2), X#\= Y, Y#\= Z, Z#\= X
■ hranově konzistentní
■ nemá žádné řešení Jaký je tedy význam AC?
■ někdy dá řešení přímo
■ nějaká doména se vyprázdní => řešení neexistuje
■ všechny domény jsou jednoprvkové => máme řešení
■ v obecném případě se alespoň zmenší prohledávaný prostor
Hana Rudová, Logické programování I, 26. dubna 2011 15 Algoritmy pro CSP
k-konzistence
■ Mají NC a AC něco společného?
■ NC: konzistence jedné proměnné
■ AC: konzistence dvou proměnných "... můžeme pokračovat
■ CSPje k-konzistentní právě tehdy, když můžeme libovolné konzistentní ohodnocení (k-1) různých proměnných rozšířit do libovolné k-té proměnné
4-konzistentní graf
■ Pro obecné CSP, tedy i pro nebinární podmínky
Hana Rudová, Logické programování I, 26. dubna 201 1 16 Algoritmy pro CSP
Silná k-konzistence
Konzistence pro nalezení řešení
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
■ Silná k-konzistence => k-konzistence
■ Silná k-konzistence => j-konzistence V j < k
■ k-konzistence =fr silná k-konzistence
■ NC = silná 1 -konzistence = 1 -konzistence
■ AC = (silná) 2-konzistence
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<n také nestačí
1,2.....n-1
1,2.....n-1
graf s n vrcholy domény 1 ..(n-1)
silně k-konzistentní pro každé k<n přesto nemá řešení
Hana Rudová, Logické programování I, 26. dubna 2011
Algoritmy pro CSP
Hana Rudová, Logické programování I, 26. dubna 201 1
Algoritmy pro CSP
Řešení nebinárních podmínek
■ k-konzistence má exponenciální složitost, v reálu se nepoužívá
■ 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 xeD; existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí
■A + B #= C, A in 1..3, B in 2..4, C in 3..7je obecně hranově konzistentní
■ Využívá se sémantika podmínek
■ speciální typy konzistence pro globální omezení
■ viz all_distinct
■ 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: hranová konzistence, konzistence mezí
Hana Rudová, Logické programování I, 26. dubna 2011 19 Algoritmy pro CSP
Konzistenční algoritmus pro nebinární podmínky
■ Algoritmus s frontou proměnných (někdy též nazýván AC-8)
■ opakovaně se provádí revize podmínek, dokud se mění domény proceduře Nonbinary-AC-3-with-Variables((V,D,C))
Q := V
while Q non empty do
vyber a smaž VjGQ for V C takové, že Vj e scope(C) do W := revise (V,, C)
// W je množina proměnných jejichž, doména se změnila i f 3 Ví e w taková, že Dí = 0 then return fail Q := Q u {w} end   Non-binary-consistency
■ rozsah omezení scope(C): množina proměnných, na nichž je C definováno
■ Implementace: u každé proměnné je seznam vybraných podmínek pro propagaci,
REVISE procedury pro tyto podmínky definuje uživatel v závislosti na typu podmínky
Hana Rudová, Logické programování I, 26. dubna 201 1
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, 26. dubna 2011
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, 26. dubna 201 1
Algoritmy pro CSP