Logické programování s omezujícími podmínkami
Constraint Logic Programming: CLP
CP: elektronické materiály
Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003.
J* http://www.ics.uci.edu/~dechter/books/
Barták R. Prednáška Omezující podmínky na MFF UK, Praha.
-i- http://kti.ms.mff.cuni.cz/~bartak/podminky/prednaska.html
M SICStus Prolog User's Manual, 2007. Kapitola o CLP(FD). a http://www.fi.muni.cz/~hanka/sicstus/doc/html/
& Príklady v distribuci SICStus Prologu: cca 45 príkladu, zdrojový kód
-i- lib/sicstus-*/library/clpfd/examples/
Hana Rudová, Logické programování I, 6. května 2010
2
Logické programování s omezujícími podmínkami
Probírané oblasti
M Obsah
úvod: od LP k CLP & základy programování
a základní algoritmy pro rešení problémů s omezujícími podmínkami
Hana Rudová, Logické programování I, 6. května 2010
3
Logické programování s omezujícími podmínkami
Probírané oblasti
M Obsah
úvod: od LP k CLP & základy programování
a základní algoritmy pro rešení problémů s omezujícími podmínkami
ii> Príbuzné prednášky na FI
s PA163 Programování s omezujícími podmínkami
-v http://www.fi.muni.cz/~hanka/cp *> PA167 Rozvrhování
-v http://www.fi.muni.cz/~hanka/rozvrhovani
zahrnuty CP techniky pro rešení rozvrhovacích problémU
Hana Rudová, Logické programování I, 6. května 2010
3
Logické programování s omezujícími podmínkami
Historie a současnost
& 1963 interaktivní grafika (Sutherland: Sketchpad)
M Polovina 80. let: logické programování omezujícími podmínkami
& Od 1990: komerCní využití
JS* Už v roce 1996: výnos rádove stovky milionů dolarU
& Aplikace - príklady
a Lufthansa: krátkodobé personální plánování
reakce na zmeny pri doprave (zpoždení letadla, ...) minimalizace zmeny v rozvrhu, minimalizace ceny
J* Nokia: automatická konfigurace sw pro mobilní telefony
Jt Renault: krátkodobé plánování výroby, funkcní od roku 1995
Hana Rudová, Logické programování I, 6. kvetna 2010
4
Logické programování s omezujícími podmínkami
Omezení (constraint)
JS> Dána
a množina (doménových) proměnných Y = {yi,... ,^^1 koneCná množina hodnot (doména) D = {D1,... ,Dk}
Omezení c na Y je podmnožina D1 x ... x Dk
a omezuje hodnoty, kterých mohou proměnné nabývat současně
Hana Rudová, Logické programování I, 6. kvetna 2010
5
Logické programování s omezujícími podmínkami
Omezení (constraint)
JS> Dána
a množina (doménových) proměnných Y = {yi,... ,^^1 koneCná množina hodnot (doména) D = {D1,... ,Dk}
Omezení c na Y je podmnožina D1 x ... x Dk
a omezuje hodnoty, kterých mohou proměnné nabývat současně
Příklad:
proměnné:
A,B
-i- domény:
{0,1} pro A
{1,2} pro B
omezení:
nebo
(A,B) g {(0,1),(0,2),(1,2)}
Hana Rudová, Logické programování I, 6. kvetna 2010
Logické programování s omezujícími podmínkami
Omezení (constraint)
JS> Dána
a množina (doménových) proměnných Y = {y^... ,^^1 koneCná množina hodnot (doména) D = {D1,... ,Dk}
Omezení c na Y je podmnožina D1 x ... x Dk
a omezuje hodnoty, kterých mohou proměnné nabývat současně
Ji Príklad:
-fc promenné: A,B
-i- domény: {0,1} pro A      {1,2} pro B
omezení: A=B      nebo      (A,B) g {(0,1),(0,2),(1,2)}
& Omezení c definováno na y1, ...yk je splneno, pokud pro d1 g D1, ...dk g Dk platí (d1,... dk) g c
Hana Rudová, Logické programování I, 6. kvetna 2010
5
Logické programování s omezujícími podmínkami
Omezení (constraint)
JS> Dána
a množina (doménových) proměnných Y = {y^... ,^^1 koneCná množina hodnot (doména) D = {D1,... ,Dk}
Omezení c na Y je podmnožina D1 x ... x Dk
a omezuje hodnoty, kterých mohou promenné nabývat soucasne
Ji Príklad:
-fc promenné: A,B
-i- domény: {0,1} pro A      {1,2} pro B
omezení: A=B      nebo      (A,B) g {(0,1),(0,2),(1,2)}
& Omezení c definováno na y1, ...yk je splneno, pokud pro d1 g D1, ...dk g Dk platí (d1,... dk) g c
-i* príklad (pokracování): omezení splneno pro (0,1), (0, 2), (1,2), není splneno pro (1,1)
Hana Rudová, Logické programování I, 6. kvetna 2010
5
Logické programování s omezujícími podmínkami
Problém splňování podmínek (CSP)
C Dána
a konečná množina proměnných X = {xi,... , xn}
it konečná množina hodnot (doména) D = {D1,... ,Dn} s> konečná množina omezení C = {c1,cm}
omezení je definováno na podmnožině X
Problém splňování podmínek je trojice (X,D,C) (constraint satisfaction problem)
Hana Rudová, Logické programování I, 6. kvetna 2010
6
Logické programování s omezujícími podmínkami
Problém splňování podmínek (CSP)
C Dána
a konečná množina proměnných X = {xi,... , xn}
it konečná množina hodnot (doména) D = {D1,... ,Dn} it konečná množina omezení C = {c1,cm} omezení je definováno na podmnožině X
Problém splňování podmínek je trojice (X,D,C) (constraint satisfaction problem)
M Príklad:
it promenne:
A,B,C
Jt domeny:
{0,1} pro A
{1,2} pro B
{0,2} pro C
omezení:
A=B, B=C
Hana Rudová, Logické programování I, 6. kvetna 2010
6
Logické programování s omezujícími podmínkami
Řešení CSP
■v
Řástecné ohodnocení proměnných (d\,dk),k < n
s* nekteré promenné mají přiřazenu hodnotu Úplné ohodnocení promenných (d\,dn) & všechny promenné mají prirazenu hodnotu
Hana Rudová, Logické programování I, 6. kvetna 2010
7
Logické programování s omezujícími podmínkami
Řešení CSP
■v
Řástecné ohodnocení promenných (di,dk),k < n s* nekteré promenné mají prirazenu hodnotu Úplné ohodnocení promenných (d1,dn) & všechny promenné mají prirazenu hodnotu Řešení CSP
-fc úplné ohodnocení promenných, které splnuje všechna omezení s (d1dn) g D1 x ... x Dn je rešení (X, D, C) pro každé a g C na xii,...xik platí (dii,...dik) g a
Hana Rudová, Logické programování I, 6. kvetna 2010
7
Logické programování s omezujícími podmínkami
Řešení CSP
■v
Cástecné ohodnocení proměnných (d1,dk),k < n s* některé proměnné mají přiřazenu hodnotu Úplné ohodnocení proměnných (d1,dn) & všechny proměnné mají přiřazenu hodnotu Řešení CSP
-fc úplné ohodnocení promenných, které spinuje všechna omezení s (didn) g Di x ... x Dn je rešení (X, D, C) pro každé ci g C na xii,...xik platí (dii,...dik) g a
Hledáme: jedno nebo
všechna rešení nebo
optimální r ešení (vzhledem k objektivní funkci)
Hana Rudová, Logické programování I, 6. kvetna 2010
7
Logické programování s omezujícími podmínkami
Příklad: jednoduchý školní rozvrh
proměnné: Jan, Petr, ... domény: (3,4, 5,6}, {3,4},... omezení: a11_distinct([Jan,Petr,...])
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, 6. kvetna 2010
8
Logické programování s omezujícími podmínkami
Příklad: jednoduchý školní rozvrh
proměnné: Jan, Petr, ...
domény: (3,4, 5,6}, {3,4},...
omězění: all_distinct([Jan,Petr,...])
částečné ohodnocení: Jan=6, Anna=5, Marie=1
úplné ohodnocení:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Mariě=6
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, 6. května 2010
8
Logické programování s omezujícími podmínkami
Příklad: jednoduchý školní rozvrh
proměnné: Jan, Petr, ...
domény: (3,4, 5,6}, (3,4},...
omězění: all_distinct([Jan,Petr,...])
částečné ohodnocení: Jan=6, Anna=5, Marie=1
úplné ohodnocení:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Mariě=6 rěšění CSP:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Marie=1
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
všechna řešení: ještě Jan=6, Petr=4, Anna=5, Ota=2, Eva=3, Marie=1
Hana Rudová, Logické programování I, 6. května 2010
8
Logické programování s omezujícími podmínkami
Príklad: jednoduchý školní rozvrh
proměnné: Jan, Petr, ... domény: (3,4, 5,6}, {3,4},... omězění: all_distinct([Jan,Petr,...]) částečné ohodnocení: Jan=6, Anna=5, Marie=1 úplné ohodnocení:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Mariě=6 rěšění CSP:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Marie=1
všechna rěšění: ještě Jan=6, Pětr=4, Anna=5, Ota=2, Eva=3, Marie=1
optimalizace: ženy uCí co nejdříve
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, 6. kvetna 2010
8
Logické programování s omezujícími podmínkami
Príklad: jednoduchý školní rozvrh
& promenné: Jan, Petr, ...
-i* domény: {3,4, 5,6}, {3,4},...
M omezení: all_distinct([Jan,Petr,...])
JS> cástecné ohodnocení: Jan=6, Anna=5, Marie=1
JS> úplné ohodnocení:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Marie=6
řešení CSP:
Jan=6, Petr=3, Anna=5, Ota=2, Eva=4, Marie=1
& všechna rešení: ješte Jan=6, Petr=4, Anna=5, Ota=2, Eva=3, Marie=1
& optimálizace: ženy ucí co nejdríve
Anna+Eva+Marie #= Cena minimalizace hodnoty promenné Cena optimální rešení: Jan=6, Petr=4, Anna=5, Ota=2, Eva=3, Marie=1
Hana Rudová, Logické programování I, 6. kvetna 2010 8 Logické programování s omezujícími podmínkami
učitel	min	max
Jan	3	6
Petr	3	4
Anna	2	5
Ota	2	4
Eva	3	4
Marie	1	6
CLPCFD) program
& Základní struktura CLP programu
1. definice proměnných a jejich domén
2. definice omezení
3. hledání rešení
Hana Rudová, Logické programování I, 6. května 2010 9 Logické programování s omezujícími podmínkami
CLPCFD) program
& Základní struktura CLP programu
1. definice proměnných a jejich domén
2. definice omezení
3. hledání rešení
& (1) a (2) deklarativní cást
modelování problému a vyjádření problému splnování podmínek
Hana Rudová, Logické programování I, 6. kvetna 2010 9 Logické programování s omezujícími podmínkami
CLPCFD) program
-i* Základní struktura CLP programu
1. definice proměnných a jejich domén
2. definice omezení
3. hledání r ešení
ü> (1) a (2) deklarativní cást
Jt modelování problému
a vyjád rení problému splnování podmínek
-i* (3) r ídící cást
& prohledávání stavového prostoru r ešení
Jt procedura pro hledání r ešení (enumeraci) se nazývá labeling
s> umožní nalézt jedno, všechna nebo optimální řešení
Hana Rudová, Logické programování I, 6. kvetna 2010 9 Logické programování s omezujícími podmínkami
Kód CLPCFD) programu
% základní struktura CLP programu so1ve( Variables ) :-
dec1are_variab1es( Variables ), domain([Jan],3,6], ...
Hana Rudová, Logické programování I, 6. května 2010
10
Logické programování s omezujícími podmínkami
Kód CLPCFD) programu
% základní struktura CLP programu
solve( Variables )
declare_variables( Variables ), post_constraints( Variables ),
domain([Jan],3,6], ... all_distinct([Jan,Petr,...])
Hana Rudová, Logické programování I, 6. května 2010
10
Logické programování s omezujícími podmínkami
Kód CLPCFD) programu
% základní struktura CLP programu solve( Variables )
declare_variables( Variables ), domain([Jan],3,6], ...
post_constraints( Variables ), all_distinct([Jan,Petr,...])
labeling( Variables ).
Hana Rudová, Logické programování I, G. kvetna 2G1G
1G
Logické programování s omezujícími podmínkami
Kód CLPCFD) programu
% základní struktura CLP programu solve( Variables ) :-
dec1are_variab1es( Variables ), domain([Jan],3,6], ...
post_constraints( Variables ), all_distinct([Ilan,Petr,...])
labelingC Variables ).
% triviální labeling labelingC [] )■ labelingC [Var|Rest]   ) :-fd_min(Var,Min),
C Var#=Min, labelingC Rest )
% výber nejmenší hodnoty z domény
Hana Rudová, Logické programování I, G. kvetna 2G1G
1G
Logické programování s omezujícími podmínkami
Kód CLP(FD) programu
% základní struktura CLP programu solve( Variables ) :-
declare_variables( Variables ), domain([Jan],3,6], ...
post_constraints( Variables ), all_distinct([Jan,Petr,...])
labeling( Variables ).
% triviální labeling labeling( [] ). labeling( [Var|Rest]   ) :-
fd_min(Var,Min), % výber nejmenší hodnoty z domény
( Var#=Min, labeling( Rest )
■
Var#>Min , labeling( [Var|Rest] )
Hana Rudová, Logické programování I, G. kvetna 2010 10 Logické programování s omezujícími podmínkami
Príklad: algebrogram
Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY různá písmena mají prirazena různé cifry s S a M nejsou 0
Hana Rudová, Logické programování I, 6. kvetna 2010
11
Logické programování s omezujícími podmínkami
Príklad: algebrogram
Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY mzná písmena mají prirazena různé cifry s S a M nejsou 0
domain([E,N,D,O,R,Y], 0, 9), domain([S,M],1,9)
Hana Rudová, Logické programování I, 6. kvetna 2010
11
Logické programování s omezujícími podmínkami
P ríklad: algebrogram
Prirad'te cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY mzná písmena mají prirazena různé cifry s S a M nejsou 0
domain([E,N,D,O,R,Y], 0, 9), domain([S,M],1,9)
1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E
#=   10000*M + 1000*O + 100*N + 10*E + Y
Hana Rudová, Logické programování I, 6. kvetna 2010
11
Logické programování s omezujícími podmínkami
Príklad: algebrogram
Prirad'te cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY mzná písmena mají prirazena různé cifry s S a M nejsou 0
domain([E,N,D,O,R,Y], 0, 9), domain([S,M],1,9)
1000*S + 100*E + 10*N + D + 1000*M + 100*0 + 10*R + E
#=   10000*M + 1000*0 + 100*N + 10*E + Y
a11_distinct( [S,E,N,D,M,0,R,Y] )
Hana Rudová, Logické programování I, 6. kvetna 2010
11
Logické programování s omezujícími podmínkami
Príklad: algebrogram
Pr i rad'te cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
SEND + MORE = MONEY rUzná písmena mají p r i razena různé cifry s S a M nejsou 0
domain([E,N,D,O,R,Y], 0, 9), domain([S,M],1,9)
1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E
#=   10000*M + 1000*O + 100*N + 10*E + Y
all_distinct( [S,E,N,D,M,O,R,Y] )
labeling( [S,E,N,D,M,O,R,Y] )
Hana Rudová, Logické programování I, 6. kvetna 2010
Logické programování s omezujícími podmínkami
Od LP k CLP I.
-í* CLP: rozšíření logického programování o omezující podmínky -í* CLP systémy se liší podle typu domény -i- CLP(a)   generický jazyk
-fc CLP(FD)   domény promenných jsou koneCné (Finite Domains) 3» CLP(R)   doménou promenných je množina reálných císel
Hana Rudová, Logické programování I, G. kvetna 2G1G
12
Logické programování s omezujícími podmínkami
Od LP k CLP I.
-í* CLP: rozšír ení logického programování o omezující podmínky -í* CLP systémy se liší podle typu domény -i- CLP(a)   generický jazyk
it CLP(FD)   domény promenných jsou konecné (Finite Domains) it CLP(R)   doménou promenných je množina reálných císel
C Cíl
it využít syntaktické a výrazové p rednosti LP dosáhnout vetší efektivity
Hana Rudová, Logické programování I, 6. kvetna 2010
12
Logické programování s omezujícími podmínkami
Od LP k CLP I.
-í* CLP: rozšírení logického programování o omezující podmínky -í* CLP systémy se liší podle typu domény it CLP(a)   generický jazyk
Jt CLP(FD)   domény promenných jsou konecné (Finite Domains) 3» CLP(R)   doménou promenných je množina reálných císel
C Cíl
& využít syntaktické a výrazové prednosti LP
dosáhnout vetší efektivity
Unifikace v LP je nahrazena splňováním podmínek
J* unifikace se chápe jako jedna z podmínek A = B
M A #< B,   A in 0..9,   domain([A,B],0,9), all_distinct([A,B,C])
Hana Rudová, Logické programování I, 6. kvetna 2010 12 Logické programování s omezujícími podmínkami
Od LP k CLP II.
Pro r ešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
£> omezení: A in 0..2, B in 0..2, B #< A
Hana Rudová, Logické programování I, 6. kvetna 2010
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
Pro řešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
£> omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
Hana Rudová, Logické programování I, 6. května 2010
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
Pro r ešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
£> omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky
Hana Rudová, Logické programování I, 6. května 2010
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
& Pro řešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
ii> Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistenCními technikami
A in 1..2, B in 0..1, B #< A
Hana Rudová, Logické programování I, 6. kvetna 2010 13 Logické programování s omezujícími podmínkami
Od LP k CLP II.
& Pro rešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
Jt omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
ii> Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistencními technikami
A in 1..2, B in 0..1, B #< A -fc po provedení A #=1      se z B #< A se odvodí:      B #= 0
Hana Rudová, Logické programování I, 6. kvetna 2010
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
JS> Pro rešení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
£> omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
iS> Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistenCními technikami
A in 1..2, B in 0..1, B #< A -fc po provedení A #=1      se z B #< A se odvodí:      B #= 0
iS» Podmínky jako výstup
kompaktní reprezentace nekonecného poctu rešení, výstup lze použít jako vstup
Hana Rudová, Logické programování I, 6. kvetna 2010
13
Logické programování s omezujícími podmínkami
Od LP k CLP II.
& Pro r ěšení podmínek se používají konzistenCní techniky
A consistency techniques, propagace omezení (constraint propagation)
it omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
& Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistenCními technikami
A in 1..2, B in 0..1, B #< A it po provedení A #=1      se z B #< A se odvodí:      B #= 0
& Podmínky jako výstup
it kompaktní reprezentace nekonecného poctu r ešení, výstup lze použít jako vstup it dotaz: A in 0..2, B in 0..2, B #< A výstup: A in 1..2, B in 0..1,
Hana Rudová, Logické programování I, 6. kvetna 2010 13 Logické programování s omezujícími podmínkami
Od LP k CLP II.
& Pro rešení podmínek se používají konzistencní techniky
A consistency techniques, propagace omezení (constraint propagation)
it omezení: A in 0..2, B in 0..2, B #< A
domény po propagaci omezení B #< A: A in 1..2, B in 0..1
ii> Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky JS> Prohledávání doplneno konzistencními technikami
Ain1..2, Bin 0..1, B #< A
it po provedení A #=1      se z B #< A se odvodí:      B #= 0
& Podmínky jako výstup
it kompaktní reprezentace nekonecného poctu řešení, výstup lze použít jako vstup it dotaz: A in 0..2, B in 0..2, B #< A výstup: A in 1..2, B in 0..1, B #< A
Hana Rudová, Logické programování I, 6. kvetna 2010 13 Logické programování s omezujícími podmínkami
Syntaxe CLP
Výber jazyka omezení CLP klauzule
jako LP klauzule, ale její telo může obsahovat omezení daného jazyka
p(X,Y)       X #< Y+1, q(X), r(X,Y,Z).
Rezolucní krok v LP
a kontrola existence nejobecnejšího unifikátoru (MGU) mezi cílem a hlavou
£ Krok odvození v CLP také zahrnuje
S kontrola konzistence aktuální množiny omezení s omezeními v tele klauzule
=> Vyvolání dvou rešiců: unifikace + rešic omezení
Hana Rudová, Logické programování I, 6. kvetna 2010
14
Logické programování s omezujícími podmínkami
OperaCní sémantika CLP
CLP výpocet cíle G
J» Store množina aktivních omezení = prostor omezení (constraint store) s» inicializace Store = 0
Jr seznamy cílů v G provádeny v obvyklém poradí a pokud narazíme na cíl s omezením c: NewStore = Store u {c} %> snažíme se splnit c vyvoláním jeho rešice pri neúspechu se vyvolá backtracking
pri úspechu se podmínky v NewStore zjednoduší propagací omezení Jt zbývající cíle jsou provádeny s upraveným NewStore
CLP výpocet cíle G je úspešný, pokud se dostaneme z iniciálního stavu {G, 0) do stavu {G',Store), kde G je prázdný cíl a Store je splnitelná.
Hana Rudová, Logické programování I, 6. kvetna 2010
15
Logické programování s omezujícími podmínkami
CLPCFD) v SICStus Prologu
Nejpoužívanejší systémy a jazyky pro CP
Swedish Institute of Computer Science: SICStus Prolog 1985
i* silná CLPCFD) knihovna, koměrCní i akademické použití
Hana Rudová, Logické programování I, 6. května 2010
17
CLP(FD) v SICStus Prologu
Nejpoužívanejší systémy a jazyky pro CP
Swedish Institute of Computer Science: SICStus Prolog 1985
i* silná CLP(FD) knihovna, komerCní i akademické použití
B IC-PARC, Imperial College London, Cisco Systems: ECL*PSe 1984
-i- široké možnosti kooperace mezi ruznými r ešicemi: konecné domény, reálná císla, repair
-fc od 2004 vlastní Cisco Systems volne dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris
Hana Rudová, Logické programování I, 6. kvetna 2010
17
CLP(FD) v SICStus Prologu
Nejpoužívanejší systémy a jazyky pro CP
Swedish Institute of Computer Science: SICStus Prolog 1985
it silná CLPCFD) knihovna, komercní i akademické použití
B IC-PARC, Imperial College London, Cisco Systems: ECL*PSe 1984
-i- široké možnosti kooperace mezi různými r ešicemi: konecné domény, reálná císla, repair
it od 2004 vlastní Cisco Systems volne dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris
JS> IBM ILOG CP Optimizer, omezující podmínky v C++ 1987
it špickový komercní sw, vznikl ve Francii, nedávno zakoupen IBM it nyní nove volne dostupný pro akademické použití
it implementace podmínek založena na objektove orientovaném programování
Hana Rudová, Logické programování I, 6. kvetna 2010 17 CLP(FD) v SICStus Prologu
Nejpoužívanejší systémy a jazyky pro CP
Swedish Institute of Computer Science: SICStus Prolog 1985
it silná CLP(FL)) knihovna, komercní i akademické použití
B IC-PARC, Imperial College London, Cisco Systems: ECL*PSe 1984
-i- široké možnosti kooperace mezi různými r ešicemi: konecné domény, reálná císla, repair
it od 2004 vlastní Cisco Systems volne dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris
JS> IBM ILOG CP Optimizer, omezující podmínky v C++ 1987
it špickový komercní sw, vznikl ve Francii, nedávno zakoupen IBM it nyní nove volne dostupný pro akademické použití
it implementace podmínek založena na objektove orientovaném programování
JS> http://www.fi.muni.cz/~hanka/bookmarks.html#tools
cca 50 odkazů na nejmznejší systémy založené na Prologu, C++, Java, Lisp, ...
Hana Rudová, Logické programování I, 6. kvetna 2010 17 CLP(FD) v SICStus Prologu
CLP(FD) v SICStus Prologu
& Vestavené predikáty jsou dostupné v separátním modulu (knihovne) :- use_modu1e(1ibrary(c1pfd)).
Obecné principy platné všude nicméne standarty jsou nedostatecné
a stejné/podobné vestavené predikáty existují i jinde s> CLP knihovny v SWI Prologu i ECLiPSe se liší
Hana Rudová, Logické programování I, 6. kvetna 2010
18
CLP(FD) v SICStus Prologu
P r íslušnost k doméne: Range termy
i& ?- domain( [A,B], 1,3). domain( +Variab1es, +Min, +Max)
A in 1..3 B in 1..3
Hana Rudová, Logické programování I, 6. kvetna 2010
19
CLP(FD) v SICStus Prologu
Príslušnost k doméne: Range termy
i& ?- domain( [A,B], 1,3). domain( +Variab1es, +Min, +Max)
A in 1..3 B in 1..3
Jfc ?- A in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
Hana Rudová, Logické programování I, 6. kvetna 2010
19
CLP(FD) v SICStus Prologu
Príslušnost k doméne: Range termy
-i* ?- domain( [A,B], 1,3). domain( +Variables, +Min, +Max)
A in 1..3 B in 1..3
B ?- a in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
& Doména reprezentována jako posloupnost intervalů celých císel
M ?- a in (1..3) \/ (8..15) \/ (5..9) \/ {100}. ?X in +Range
A in (1..3) \/ (5..15) \/ {100}
Hana Rudová, Logické programování I, 6. kvetna 2010
19
CLP(FD) v SICStus Prologu
Příslušnost k doméne: Range termy
-i* ?- domain( [A,B], 1,3). domain( +Variables, +Min, +Max)
A in 1..3 B in 1..3
Jfc ?- A in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
& Doména reprezentována jako posloupnost intervalů celých císel
M ?- a in (1..3) \/ (8..15) \/ (5..9) \/ {100}. ?X in +Range
A in (1..3) \/ (5..15) \/ {100}
Zjištení domény Range promenné Var: fd_dom(?Var,?Range)
A in 1..8, A #\= 4, fd_dom(A,Range). Range=(1..3) \/ (5..8)
Hana Rudová, Logické programování I, 6. kvetna 2010
19
CLP(FD) v SICStus Prologu
Príslušnost k doméne: Range termy
-i* ?- domain( [A,B], 1,3). domain( +Variab1es, +Min, +Max)
A in 1..3 B in 1..3
Jfc ?- A in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
& Doména reprezentována jako posloupnost intervalů celých císel
M ?- a in (1..3) \/ (8..15) \/ C5..9) \/ {100}. ?X in +Range
A in (1..3) \/ (5..15) \/ {100}
Zjištení domény Range promenné Var: fd_dom(?Var,?Range)
A in 1..8, A #\= 4, fd_dom(A,Range). Range=(1..3) \/ (5..8)
M A in 2..10, fd_dom(A,(1..3) \/ (5..8)). no
Hana Rudová, Logické programování I, 6. kvetna 2010
19
CLP(FD) v SICStus Prologu
Príslušnost k doméne: Range termy
-i* ?- domain( [A,B], 1,3). domain( +Variab1es, +Min, +Max)
A in 1..3 B in 1..3
B ?- a in 1..8, A #\= 4. ?X in +Min..+Max
A in (1..3) \/ (5..8)
& Doména reprezentována jako posloupnost intervalů celých císel
M ?- a in (1..3) \/ (8..15) \/ C5..9) \/ {100}. ?X in +Range
A in (1..3) \/ (5..15) \/ {100}
Zjištení domény Range promenné Var: fd_dom(?Var,?Range)
A in 1..8, A #\= 4, fd_dom(A,Range). Range=(1..3) \/ (5..8)
A in 2..10, fd_dom(A,(1..3) \/ (5..8)). no
& Range term: reprezentace nezávislá na implementaci
Hana Rudová, Logické programování I, 6. kvetna 2010
19
CLP(FD) v SICStus Prologu
Príslušnost k doméne: FDSet termy
C FDSet term: reprezentace závislá na implementaci
M ?- A in 1..8, A #\= 4, fd_set(A,FDSet). A in (1..3) \/ (5..8) FDSet = [[1|3],[5|8]]
fd_set(?Var,?FDSet)
Hana Rudová, Logické programování I, 6. kvetna 2010
20
CLP(FD) v SICStus Prologu
Příslušnost k doméně: FDSet termy
C FDSet term: reprezentace závislá na implementaci
M ?- A in 1..8, A #\= 4, fd_set(A,FDSet). fd_set(?Var,?FDSet)
A in (1..3) \/ (5..8) FDSet = [[1|3],[5|8]]
J ?- A in 1..8.A #\= 4, fd_set(A,FDSet),B in_set FDSet.      ?X in_set +FDSet A in (1..3) \/ (5..8) FDSet = [[1|3],[5|8]] B in (1..3) \/ (5..8)
Hana Rudová, Logické programování I, 6. kvetna 2010
20
CLP(FD) v SICStus Prologu
P r íslušnost k doméne: FDSet termy
C FDSet term: reprezentace závislá na implementaci
M ?- A in 1..8, A #\= 4, fd_set(A,FDSet). fd_set(?Var,?FDSet) A in (1..3) \/ C5..8) FDSet = [[1|3],[5|8]]
J ?- A in 1..8.A #\= 4, fd_set(A,FDSet),B in_set FDSet.      ?X in_set +FDSet A in (1..3) \/ C5..8) FDSet = [[1|3],[5|8]] B in (1..3) \/ C5..8)
& FDSet termy predstavují nízko-úrovnovou implementaci
FDSet termy nedoporuceny v programech
-fc používat pouze predikáty pro manipulaci s nimi -i- omezit použití A in_set [[1|2],[6|9]]
JS> Range termy preferovány
Hana Rudová, Logické programování I, 6. kvetna 2010 20 CLP(FD) v SICStus Prologu
Další fd_... predikáty
fdset_to_1ist(+FDset, -List) vrací do seznamu prvky FDset & 1ist_to_fdset(+List, -FDset) vrací FDset odpovídající seznamu
fd_var(?Var)   je Var doménová promenná?
fd_min(?Var,?Min)    nejmenší hodnota v doméne fd_max(?Var,?Max)    nejvetší hodnota v doméne
fd_size(?Var,?Size)   velikost domény
fd_degree(?Var,?Degree)    pocet navázaných omezení na promenné
Hana Rudová, Logické programování I, 6. kvetna 2010 21 CLP(FD) v SICStus Prologu
Další fd_... predikáty
fdset_to_list(+FDset, -List) vrací do seznamu prvky FDset & list_to_fdset(+List, -FDset) vrací FDset odpovídající seznamu
fd_var(?Var)   je Var doménová promenná?
fd_rrrin(?Var,?Min)    nejmenší hodnota v doméne fd_max(?Var,?Max)    nejvetší hodnota v doméne
fd_size(?Var,?Size)   velikost domény
fd_degree(?Var,?Degree)    pocet navázaných omezení na promenné iľ mení se behem výpoctu: pouze aktivní omezení, i odvozená aktivní omezení
Hana Rudová, Logické programování I, 6. kvetna 2010 21 CLP(FD) v SICStus Prologu
Aritmetická omezení
J* Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>=
a A + B #=< 3, A #\= (C - 4) * ( D - 5), A/2 #= 4
Jt POZOR: neplést #=< a #>= s operátory pro implikaci:   #<= #=>
Hana Rudová, Logické programování I, 6. kvetna 2010
22
CLP(FD) v SICStus Prologu
Aritmetická omezení
J> Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>=
a A + B #=< 3, A #\= (C - 4) * ( D - 5), A/2 #= 4
a POZOR: neplést #=< a #>= s operátory pro implikaci:   #<= #=>
-í* sum(Variab1es,Re1Op,Suma)
domain([A,B,C,F],1,3), sum([A,B,C],#= ,F)
Hana Rudová, Logické programování I, 6. kvetna 2010
22
CLP(FD) v SICStus Prologu
Aritmetická omezení
J* Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>=
a A + B #=< 3, A #\= (C - 4) * ( D - 5), A/2 #= 4
a POZOR: neplést #=< a #>= s operátory pro implikaci:   #<= #=>
& sum(Variables,RelOp,Suma)
domain([A,B,C,F],1,3), sum([A,B,C],#= ,F) & Variables i Suma musí být doménové promenné nebo celá císla
scalar_product(Coeffs,Variables,RelOp,ScalarProduct)
M domain([A,B,C,F],1,6), scalar_product( [1,2,3],[A,B,C],#= ,F)
iľ Variables i Value musí být doménové promenné nebo konstanty, Coeffs jsou celá císla
J* POZOR na poradí argumentu, nejprve jsou celocíselné koeficienty, pak dom. promenné
3 scalar_product(Coeffs, Variables, #= , Value, [consistency(domain)])
silnejší typ konzistence
POZOR: domény musí mít konecné hranice
Hana Rudová, Logické programování I, 6. kvetna 2010 22 CLP(FD) v SICStus Prologu
Výroková omezení, reifikace
Výroková omezení pozor na efektivitu
Jt \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ...
Hana Rudová, Logické programování I, 6. kvetna 2010
23
CLP(FD) v SICStus Prologu
Výroková omezení, reifikace
M Výroková omezení
\# negace, #/\ konjunkce, #\/ * X #> 4 #/\ Y #< 6 p ríklad:
A#\= 3, A#\= 4
A in (inf..2)\/ (5..sup)
pozor na efektivitu
disjunkce, #<=> ekvivalence, ...
A#\= 3 #/\ A#\= 4 A#=1 #\/ A#=2
A in (inf..2)\/ (5..sup) A in inf..sup
Hana Rudová, Logické programování I, 6. kvetna 2010
23
CLP(FD) v SICStus Prologu
Výroková omezení, reifikace
M Výroková omezení pozor na efektivitu
Jt \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ...
X #> 4 #/\ Y #< 6 Jt príklad:
A#\= 3, A#\= 4                          A#\= 3 #/\ A#\= 4 A#=1 #\/ A#=2
A in (inf..2)\/ (5..sup)                 A in (inf..2)\/ (5..sup) A in inf..sup
tj. propagace disjunkce A#=1 #\/ A#=2 je príliš slabá (propagacní algoritmy príliš obecné)
Hana Rudová, Logické programování I, 6. kvetna 2010
23
CLP(FD) v SICStus Prologu
Výroková omezení, reifikace
M Výroková omezení pozor na efektivitu
\# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ...
X #> 4 #/\ Y #< 6
príklad:
A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=1 #\/ A#=2
A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup
tj. propagace disjunkce A#=1 #\/ A#=2 je príliš slabá (propagacní algoritmy príliš obecné)
& Reifikace pozor na efektivitu
Constraint #<=> Bool
Bool in 0..1 v závislosti na tom, zda je Constraint splnen a príklad: A in 1..10 #<=> Bool
Hana Rudová, Logické programování I, 6. kvetna 2010
23
CLP(FD) v SICStus Prologu
Výroková omezení, reifikace
M Výroková omezení pozor na efektivitu
it \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ...
X #> 4 #/\ Y #< 6 it príklad:
A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=1 #\/ A#=2
A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup
tj. propagace disjunkce A#=1 #\/ A#=2 je p ríliš slabá (propagacní algoritmy p r íliš obecné)
& Reifikace pozor na efektivitu
it Constraint #<=> Bool
Bool in 0..1 v závislosti na tom, zda je Constraint splnen
a p r íklad: A in 1..10 #<=> Bool
it zap r edpokladu X in 3..10, Y in 1..4, Bool in 0..1
porovnej rozdíl mezi   X#<Y X#<Y #<=> Bool
Hana Rudová, Logické programování I, 6. kvetna 2010
23
CLP(FD) v SICStus Prologu
Výroková omezení, reifikace
M Výroková omezení pozor na efektivitu
it \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ...
X #> 4 #/\ Y #< 6 it príklad:
A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=1 #\/ A#=2
A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup
tj. propagace disjunkce A#=1 #\/ A#=2 je p ríliš slabá (propagacní algoritmy p r íliš obecné)
& Reifikace pozor na efektivitu
Jt Constraint #<=> Bool
Bool in 0..1 v závislosti na tom, zda je Constraint splnen
a p r íklad: A in 1..10 #<=> Bool
it zap r edpokladu X in 3..10, Y in 1..4, Bool in 0..1
porovnej rozdíl mezi   X#<Y X#<Y #<=> Bool
X= 3, Y = 4 X in 3..10, Y in 1..4, Bool in 0..1
Hana Rudová, Logické programování I, 6. kvetna 2010 23 CLP(FD) v SICStus Prologu
Príklad: reifikace
C- Presne N prvků v seznamu S je rovno X: exact1y(X,S,N)
Hana Rudová, Logické programování I, 6. kvetna 2010
24
CLP(FD) v SICStus Prologu
Príklad: reifikace
Presne N prvků v seznamu S je rovno X: exact1y(X,S,N) exact1y(_,  [], 0).
Hana Rudová, Logické programování I, 6. kvetna 2010
24
CLP(FD) v SICStus Prologu
Příklad: reifikace
Presne N prvků v seznamu S je rovno X: exact1y(X,S,N)
exact1y(_,  [], 0). exact1y(X,  [Y|L], N) :-
X #= Y #<=> B, % reifikace
Hana Rudová, Logické programování I, 6. kvetna 2010
24
CLP(FD) v SICStus Prologu
Príklad: reifikace
Presne N prvků v seznamu S je rovno X: exact1y(X,S,N)
exact1y(_,  [], 0).
exact1y(X,  [Y|L], N) :-X #= Y #<=> B, N #= M+B, exactly(X, L, M).
% reifikace
% doménová promenná místo akumulátoru
Hana Rudová, Logické programování I, 6. kvetna 2010
24
CLP(FD) v SICStus Prologu
Príklad: reifikace
Presne N prvků v seznamu S je rovno X: exact1y(X,S,N)
exact1y(_,  [], 0).
exact1y(X,  [Y|L], N) :-X #= Y #<=> B, N #= M+B, exactly(X, L, M).
% reifikace
% doménová promenná místo akumulátoru
| ?- domain([A,B,C,D,E,N],1,2), exact1y(1,[A,B,C,D,E],N),
Hana Rudová, Logické programování I, 6. kvetna 2010
24
CLP(FD) v SICStus Prologu
Příklad: reifikace
Presne N prvků v seznamu S je rovno X: exact1y(X,S,N)
exact1y(_,  [], 0).
exact1y(X,  [Y|L], N) :-X #= Y #<=> B, N #= M+B, exactly(X, L, M).
% reifikace
% doménová promenná místo akumulátoru
| ?- domain([A,B,C,D,E,N],1,2), exact1y(1,[A,B,C,D,E],N),A#< 2,
Hana Rudová, Logické programování I, 6. kvetna 2010
24
CLP(FD) v SICStus Prologu
Príklad: reifikace
Presne N prvků v seznamu S je rovno X: exact1y(X,S,N)
exact1y(_,  [], 0). exact1y(X,  [Y|L], N) :-X #= Y #<=> B,
N #= M+B,
exactly(X, L, M).
% reifikace
% doménová promenná místo akumulátoru
| ?- domain([A,B,C,D,E,N],1,2), exact1y(1,[A,B,C,D,E],N),A#< 2,B#< 2.
Hana Rudová, Logické programování I, 6. kvetna 2010
24
CLP(FD) v SICStus Prologu
Príklad: reifikace
C- Presne N prvků v seznamu S je rovno X: exact1y(X,S,N)
exact1y(_,  [], 0).
exact1y(X,  [Y|L], N) :-
X #= Y #<=> B, % reifikace
N #= M+B, % doménová promenná místo akumulátoru
exactly(X, L, M).
| ?- domain([A,B,C,D,E,N],1,2), exact1y(1,[A,B,C,D,E],N),A#< 2,B#< 2. A = 1, B = 1, C = 2, D = 2, E = 2, N = 2
Hana Rudová, Logické programování I, 6. kvetna 2010
24
CLP(FD) v SICStus Prologu
Príklad: reifikace
C- Pr esne N prvků v seznamu S je rovno X: exact1y(X,S,N)
exact1y(_,  [], 0).
exact1y(X,  [Y|L], N) :-
X #= Y #<=> B, % reifikace
N #= M+B, % doménová promenná místo akumulátoru
exactly(X, L, M).
| ?- domain([A,B,C,D,E,N],1,2), exact1y(1,[A,B,C,D,E],N),A#< 2,B#< 2. A = 1, B = 1, C = 2, D = 2, E = 2, N = 2
& Vyzkoušejte si
M greaters(X,S,N): p resne N prvku v seznamu S je vetší než X ± at1east(X,S,N): alespon N prvků v seznamu S je rovno X Jt atmost(X,S,N): nejvýše N prvků v seznamu S je rovno X
Hana Rudová, Logické programování I, 6. kvetna 2010
24
CLP(FD) v SICStus Prologu
Základní globální omezení
a11_distinct(List) M všechny promenné ruzné
cumu1ative(...), cumu1atives(...)
disjunktivní a kumulativní rozvrhování
Hana Rudová, Logické programování I, 6. kvetna 2010
25
CLP(FD) v SICStus Prologu
proměnné ruzne
a11_distinct(Variab1es), a11_different(Variab1es)
ü> Proměnné v seznamu Variab1es jsou různé
a11_distinct a a11_different se liší úrovní propagace
a a11_distinct má úplnou propagaci
s» a11_different má slabší (neúplnou) propagaci
Hana Rudová, Logické programování I, 6. kvetna 2010
26
CLP(FD) v SICStus Prologu
Všechny proměnné různé
all_distinct(Variables), a11_different(Variab1es)
Proměnné v seznamu Variables jsou různé
a11_distinct a a11_different se liší úrovní propagace
a a11_distinct má úplnou propagaci
a a11_different má slabší (neúplnou) propagaci
Príklad: uCitelé musí uCit v mzné hodiny
uCitel	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, 6. kvetna 2010
26
CLP(FD) v SICStus Prologu
Všechny promenné různé
a11_distinct(Variab1es), a11_different(Variab1es)
Promenné v seznamu Variab1es jsou různé
a11_distinct a a11_different se liší úrovní propagace
a a11_distinct má úplnou propagaci
a a11_different má slabší (neúplnou) propagaci
Príklad: ucitelé musí ucit v mzné hodiny
a11_distinct([Jan,Petr,Anna,Ota,Eva,Marie])
Jan = 6, Ota = 2, Anna = 5,
Marie = 1, Petr in 3..4, Eva in 3..4
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, 6. kvetna 2010
26
CLP(FD) v SICStus Prologu
Všechny proměnné rUzné
a11_distinct(Variab1es), a11_different(Variab1es)
Promenné v seznamu Variab1es jsou různé
a11_distinct a a11_different se liší úrovní propagace
a a11_distinct má úplnou propagaci
a a11_different má slabší (neúplnou) propagaci
Príklad: uatelé musí ucit v mzné hodiny
a11_distinct([Jan,Petr,Anna,Ota,Eva,Marie])
Jan = 6, Ota = 2, Anna = 5,
Marie = 1, Petr in 3..4, Eva in 3..4
3 a11_different([Jan,Petr,Anna,Ota,Eva,Marie]) Jan in 3..6, Petr in 3..4, Anna in 2..5, Ota in 2..4, Eva in 3..4, Marie in 1..6
ucitel	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, 6. kvetna 2010
26
CLP(FD) v SICStus Prologu
Disjunktivní rozvrhování (unární zdroj)
ifc cumu1ative([task(Start, Duration, End, 1, Id) | Tasks])
iS> Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly
Hana Rudová, Logické programování I, 6. kvetna 2010
27
CLP(FD) v SICStus Prologu
Disjunktivní rozvrhování (unární zdroj)
ifc cumu1ative([task(Start, Duration, End, 1, Id) | Tasks])
iS> Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly
a príklad s konstantami: cumu1ative([task(0,2,2,1,1), task(3,1,4,1,2), task(5,1,6,1,3)])
					
	f.				3
1      2       3       4      5 6
Hana Rudová, Logické programování I, 6. kvetna 2010
27
CLP(FD) v SICStus Prologu
Disjunktivní rozvrhování (unární zdroj)
ifc cumu1ative([task(Start, Duration, End, 1, Id) | Tasks])
iS> Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se neprekrývaly
a príklad s konstantami: cumu1ative([task(0,2,2,1,1), task(3,1,4,1,2), task(5,1,6,1,3)])
					
	f. í		2		3
12       3       4      5 6
± príklad: vytvorení rozvrhu, za predpokladu, že doba trvání hodin není stejná
Hana Rudová, Logické programování I, 6. kvetna 2010
27
CLP(FD) v SICStus Prologu
Disjunktivní rozvrhování (unární zdroj)
-í* cumulative([task(Start, Duration, End, 1, Id) | Tasks])
-í* Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly
a príklad s konstantami: cumulative([task(0,2,2,1,1), task(3,1,4,1,2), task(5,1,6,1,3)])
					
	f. í		2		3
12       3       4      5 ó
± příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná JanE#= Jan+1, PetrE#= Petr+1, AnnaE#= Anna+2,
cumulative(taskOan,1,JanE,1,1),task(Petr,1,PetrE,1,2),task(Anna,1,AnnaE,1,3), task(Ota,2,OtaE,1,4),task(Eva,2,EvaE,1,5),task(Marie,3,MarieE,1,6)])
Hana Rudová, Logické programování I, 6. kvetna 2010
27
CLP(FD) v SICStus Prologu
Kumulativní rozvrhování
& cumu1ative([task(Start,Duration,End,Demand,TaskId) | Tasks],
[1imit(Limit)])
& Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se neprekrývaly a aby celková kapacita zdroje nikdy neprekrocila Limit
Hana Rudová, Logické programování I, 6. kvetna 2010
28
CLP(FD) v SICStus Prologu
Kumulativní rozvrhování
& cumu1ative([task(Start,Duration,End,Demand,TaskId) | Tasks],
[limit(Limit)])
& Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se nepřekrývaly a aby celková kapacita zdroje nikdy neprekrocila Limit
ií> Príklad s konstantami:
cumu1ative([task(Q,4,4,1,1),task(1,2,3,2,2),task(3,3,6,2,3),task(4,2,6,1,4)],[1imit(3)])
	2		4
			3
1			
T
Hana Rudová, Logické programování I, 6. kvetna 2010 1 ^   28   ^ ^ ° u CLP(FD) v SICStus Prologu
Kumulativní rozvrhování s více zdroji
Rozvržení úloh tak, aby se nepřekrývaly a daná kapacita zdrojů nebyla překročena (limit zdroje chápán jako horní mez - bound(upper))
cumu1atives([task(Start,Duration,End,Demand,MachineId)|Tasks],
[machine(Id,Limit)|Machines],[bound(upper)])
Úlohy zadány startovním a koncovým časem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a požadovaným typem zdroje (MachineId)
Zdroje zadány identifikátorem (Id) a kapacitou (Limit)
Hana Rudová, Logické programování I, 6. kvetna 2010
29
CLP(FD) v SICStus Prologu
Kumulativní rozvrhování s více zdroji
i& Rozvržení úloh tak, aby se neprekrývaly a daná kapacita zdroju nebyla prekrocena (limit zdroje chápán jako horní mez - bound(upper))
iS> cumu1atives([task(Start,Duration,End,Demand, Machineld) |Tasks],
[machine(Id,Limit)|Machines],[bound(upper)])
& Úlohy zadány startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a požadovaným typem zdroje (Machineld)
& Zdroje zadány identifikátorem (Id) a kapacitou (Limit)
M Príklad:
?- domain([B,C],1,2),
cumu1atives([task(0,4,4,1,1),task(3,1,4,1,B), task(5,1,6,1,C)],
[machine(1,1),machine(2,1)],
[bound(upper)]). C in 1..2, B=2
Hana Rudová, Logické programování I, 6. kvetna 2010 29 CLP(FD) v SICStus Prologu