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. M http://www.ics.uci.edu/~dechter/books/ -• Barták R. Přednáška Omezující podmínky na MFF UK, Praha. M http://kti.ms.mff.cuni.cz/~bartak/podminky/prednaska.html -• SICStus Prolog User's Manual, 2004. Kapitola o CLP(FD). M http://www.fi.muni.cz/~hanka/sicstus/doc/html/ -• Příklady v distribuci SICStus Prologu: cca 25 příkladů, zdrojový kód M ai sa:/software/si cstus-3.10.1/1 i b/si cstus-3.10.1/1 i brary/clpfd/examples/ M Constraint Programming Online 3 http://si ash.math.uni pd.i t/cp/i ndex.php Hana Rudová, Logické programování I, 1 7. dubna 2009 2 Logické programování s omezujícími podmínkami Probírané oblasti -• Obsah * úvod: od LP k CLP M základy programování M základní algoritmy pro řešení problémů s omezujícími podmínkami Hana Rudová, Logické programování I, 1 7. dubna 2009 3 Logické programování s omezujícími podmínkami Probírané oblasti -• Obsah * úvod: od LP k CLP M základy programování M základní algoritmy pro řešení problémů s omezujícími podmínkami -• Příbuzné přednášky na Fl M PA163 Programování s omezujícími podmínkami ± http://www.fi.muni.cz/~hanka/cp M PA1 67 Rozvrhování -i* http://www.fi .muni . cz/~hanka/rozvrhovani ± zahrnuty CP techniky pro řešení rozvrhovacích problémů Hana Rudová, Logické programování I, 1 7. dubna 2009 3 Logické programování s omezujícími podmínkami Historie a současnost -• 1963 interaktivní grafika (Sutherland: Sketchpad) 3 Polovina 80. let: logické programování omezujícími podmínkami M Od 1990: komerční využití -• Už v roce 1996: výnos řádově stovky milionů dolarů -• Aplikace - příklady -• Lufthansa: krátkodobé personální plánování «£< reakce na změny při dopravě (zpoždění letadla, ...) «i* minimalizace změny v rozvrhu, minimalizace ceny 3 Nokia: automatická konfigurace sw pro mobilní telefony 3 Renault: krátkodobé plánování výroby, funkční od roku 1995 Hana Rudová, Logické programování I, 1 7. dubna 2009 4 Logické programování s omezujícími podmínkami Omezení (constraint) -• Dána M množina (doménových) proměnných Y = {yi,... ,3/jJ 3 konečná množina hodnot (doména) D = {D\,... ,Dfc} Omezení c na Y je podmnožina D\ x ... x Dk M omezuje hodnoty, kterých mohou proměnné nabývat současně Hana Rudová, Logické programování I, 1 7. dubna 2009 5 Logické programování s omezujícími podmínkami Omezení (constraint) -• Dána M množina (doménových) proměnných Y = {yi,... ,3/jJ 3 konečná množina hodnot (doména) D = {D\,... ,Dfc} Omezení c na Y je podmnožina D\ x ... x Dk M omezuje hodnoty, kterých mohou proměnné nabývat současně -• Příklad: -• proměnné: A,B M domény: {0,1} pro A {1,2} pro B .•omezení: A^B nebo (A,B) g {(0,1),(0,2),(1,2)} Hana Rudová, Logické programování I, 1 7. dubna 2009 5 Logické programování s omezujícími podmínkami Omezení (constraint) -• Dána M množina (doménových) proměnných Y = {yi,... ,yk) 3 konečná množina hodnot (doména) D = {D\,... ,Dk\ Omezení c na Y je podmnožina D\ x ... x Dk M omezuje hodnoty, kterých mohou proměnné nabývat současně -• Příklad: -• proměnné: A,B M 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 yi,.. .yk je splněno, pokud pro d\ e D\, ...dk e Dk platí (d\,... dk) e c Hana Rudová, Logické programování I, 1 7. dubna 2009 5 Logické programování s omezujícími podmínkami Omezení (constraint) -• Dána M množina (doménových) proměnných Y = {yi,... ,yk) 3 konečná množina hodnot (doména) D = {D\,... ,Dk\ Omezení c na Y je podmnožina D\ x ... x Dk M omezuje hodnoty, kterých mohou proměnné nabývat současně -• Příklad: -• proměnné: A,B M 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 yi,.. .yk je splněno, pokud pro d\ e D\, ...dk e Dk platí (d\,... dk) e c M příklad (pokračování): omezení splněno pro (0,1), (0, 2), (1,2), není splněno pro (1,1) Hana Rudová, Logické programování I, 1 7. dubna 2009 5 Logické programování s omezujícími podmínkami Problém splňování podmínek (CSP) -• Dána M konečná množina proměnných X = {xi,... ,xn} M konečná množina hodnot (doména) D = {Di,... ,Dn} «• konečná množina omezení C = {ci,..., 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, 1 7. dubna 2009 6 Logické programování s omezujícími podmínkami Problém splňování podmínek (CSP) -• Dána M konečná množina proměnných X = {xi,... ,xn} M konečná množina hodnot (doména) D = {Di,... ,Dn} «• konečná množina omezení C = {ci,..., 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: M proměnné: A,B,C .•domény: {0,1} pro A {1,2} pro B {0,2} pro C M omezení: A^B, B^C Hana Rudová, Logické programování I, 1 7. dubna 2009 6 Logické programování s omezujícími podmínkami Řešení CSP -• Částečné ohodnocení proměnných (du..., du), k < n M některé proměnné mají přiřazenu hodnotu M Úplné ohodnocení proměnných (du ..., dn) M všechny proměnné mají přiřazenu hodnotu Hana Rudová, Logické programování I, 1 7. dubna 2009 7 Logické programování s omezujícími podmínkami Řešení CSP -• Částečné ohodnocení proměnných (du..., du), k < n M některé proměnné mají přiřazenu hodnotu M Úplné ohodnocení proměnných (du ..., dn) M všechny proměnné mají přiřazenu hodnotu M Řešení CSP M úplné ohodnocení proměnných, které splňuje všechna omezení -• (du ■ ■ ■, dn) g Di x ... x Dn je řešení (X, D, C) * pro každé d e C na Xix,...Xik platí (di^.-.d^) e c* Hana Rudová, Logické programování I, 1 7. dubna 2009 7 Logické programování s omezujícími podmínkami Řešení CSP -• Částečné ohodnocení proměnných (du..., du), k < n M některé proměnné mají přiřazenu hodnotu M Úplné ohodnocení proměnných (du ..., dn) M všechny proměnné mají přiřazenu hodnotu M Řešení CSP M úplné ohodnocení proměnných, které splňuje všechna omezení -• (du ■ ■ ■, dn) g Di x ... x Dn je řešení (X, D, C) * pro každé d g C na Xix,...Xik platí (di^.-.d^) g Cí -• Hledáme: jedno nebo všechna řešení nebo optimální řešení (vzhledem k objektivní funkci) Hana Rudová, Logické programování I, 1 7. dubna 2009 7 Logické programování s omezujícími podmínkami Příklad: jednoducl M proměnné: Jan, Petr, ... M domény: {3,4, 5,6}, {3,4},... M omezení: al l_di sti net([Jan, Petr, . Hana Rudová, Logické programování I, 1 7. dubna 2009 8 hý školní rozvrh ]) učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 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í: al l_di sti net([Jan, Petr, . . . ]) částečné ohodnocení: Jan=6, Anna=5, Marie=l úplné ohodnocení: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=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, 1 7. dubna 2009 Logické programování s omezujícími podmínkami Příklad: jednoduchý školní rozvrh M proměnné: Jan, Petr, ... M domény: {3,4, 5,6}, {3,4},... -• omezení: al l_di sti net([Jan, Petr, . . . ]) «• částečné ohodnocení: Jan=6, Anna=5, Marie=l M úplné ohodnocení: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=6 M řešení CSP: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=l -• všechna řešení: ještě Jan=6, Petr=4, Anna=5, 0ta=2, Eva-3, Marie=l 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, 1 7. dubna 2009 8 Logické programování s omezujícími podmínkami Příklad: jednoduchý školní rozvrh M proměnné: Jan, Petr, ... M domény: {3,4, 5,6}, {3,4},... -• omezení: al l_di sti net([Jan, Petr, . . . ]) «• částečné ohodnocení: Jan=6, Anna=5, Marie=l M úplné ohodnocení: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=6 M řešení CSP: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=l -• všechna řešení: ještě Jan=6, Petr=4, Anna=5, 0ta=2, Eva-3, Marie=l -• optimalizace: ženy učí 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, 1 7. dubna 2009 8 Logické programování s omezujícími podmínkami Příklad: jednoduchý školní rozvrh M proměnné: Jan, Petr, ... M domény: {3,4, 5,6}, {3,4},... -• omezení: al l_di sti net([Jan, Petr, . . . ]) «• částečné ohodnocení: Jan=6, Anna=5, Marie=l M úplné ohodnocení: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=6 M řešení CSP: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=l -• všechna řešení: ještě Jan=6, Petr=4, Anna=5, 0ta=2, Eva-3, Marie=l -• optimalizace: ženy učí co nejdříve Anna+Eva+Marie #= Cena minimalizace hodnoty proměnné Cena optimální řešení: Jan=6, Petr=4, Anna=5, 0ta=2, Eva=3, Marie=l Hana Rudová, Logické programování I, 1 7. dubna 2009 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 CLP(FD) program -• Základní struktura CLP programu 1. definice proměnných a jejich domén 2. definice omezení 3. hledání řešení Hana Rudová, Logické programování I, 1 7. dubna 2009 9 Logické programování s omezujícími podmínkami CLP(FD) program -• Základní struktura CLP programu 1. definice proměnných a jejich domén 2. definice omezení 3. hledání řešení -• (1) a (2) deklarativní část 3 modelování problému M vyjádření problému splňování podmínek Hana Rudová, Logické programování I, 1 7. dubna 2009 9 Logické programování s omezujícími podmínkami CLP(FD) program -• Základní struktura CLP programu 1. definice proměnných a jejich domén 2. definice omezení 3. hledání řešení -• (1) a (2) deklarativní část 3 modelování problému M vyjádření problému splňování podmínek -• (3) řídící část •• prohledávání stavového prostoru řešení 3 procedura pro hledání řešení (enumeraci) se nazývá labeling 3 umožní nalézt jedno, všechna nebo optimální řešení Hana Rudová, Logické programování I, 1 7. dubna 2009 9 Logické programování s omezujícími podmínkami Kód CLP(FD) programu % základní struktura CLP programu sol ve( Variables ) :- declare_variables( Variables ), domain ([Jan] ,3,6], Hana Rudová, Logické programování I, 1 7. dubna 2009 10 Logické programování s omezujícími podmínkami Kód CLP(FD) programu % základní struktura CLP programu sol ve( Variables ) :- declare_variables( Variables ), domain ([Jan] ,3,6], ... post_constraints( Variables ), all_distinct([Jan,Petr,...]) Hana Rudová, Logické programování I, 1 7. dubna 2009 10 Logické programování s omezujícími podmínkami Kód CLP(FD) programu % základní struktura CLP programu sol ve( Variables ) :- declare_variables( Variables ), domain ([Jan] ,3,6], ... post_constraints( Variables ), all_distinct([Jan,Petr,...]) labelingC Variables ). Hana Rudová, Logické programování I, 1 7. dubna 2009 1 0 Logické programování s omezujícími podmínkami Kód CLP(FD) % základní struktura CLP programu sol ve( Variables ) :- declare_variables( Variables ) post_constraints( Variables ), labelingC Variables ). % triviální labeling labelingC [] ). labelingC [Var|Rest] ) :- fd_minCVar,Min), C Var#=Min, labelingC Rest ) Hana Rudová, Logické programování I, 1 7. dubna 2009 10 programu domain([Jan],3,6], ... all _ch'sti net ([Jan, Petr, . . .]) % výběr nejmenší hodnoty z domény Logické programování s omezujícími podmínkami Kód CLP(FD) programu % základní struktura CLP programu sol ve( Variables ) :- declare_variables( Variables ), post_constraints( Variables ), labelingC Variables ). % triviální labeling labelingC [] ). labelingC [Var|Rest] ) :- fd_minCVar,Min) , % výběr nejmenší hodnoty z domény C Var#=Min, labelingC Rest ) ■ Var#>Min , labelingC [Var|Rest] ) ). domain([Jan],3,6], ... all _ch'sti net ([Jan, Petr, . . .]) Hana Rudová, Logické programování I, 1 7. dubna 2009 10 Logické programování s omezujícími podmínkami Příklad: algebrogram -• Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: M SEND + MORE= MONEY M různá písmena mají přiřazena různé cifry i SaM nejsou 0 Hana Rudová, Logické programování I, 1 7. dubna 2009 1 1 Logické programování s omezujícími podmínkami Příklad: algebrogram -• Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: M SEND + MORE= MONEY M různá písmena mají přiřazena různé cifry i SaM nejsou 0 -• domain([E,N,D,0,R,Y], 0, 9), domain([S,M],1,9) Hana Rudová, Logické programování I, 1 7. dubna 2009 1 1 Logické programování s omezujícími podmínkami Příklad: algebrogram -• Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: M SEND + MORE= MONEY M různá písmena mají přiřazena různé cifry i SaM nejsou 0 M domain([E,N,D,0,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 Hana Rudová, Logické programování I, 1 7. dubna 2009 1 1 Logické programování s omezujícími podmínkami Příklad: algebrogram -• Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: M SEND + MORE= MONEY M různá písmena mají přiřazena různé cifry i SaM nejsou 0 M domain([E,N,D,0,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 -• all_distinct( [S,E,N,D,M,0,R,Y] ) Hana Rudová, Logické programování I, 1 7. dubna 2009 1 1 Logické programování s omezujícími podmínkami Příklad: algebrogram -• Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: M SEND + MORE= MONEY M různá písmena mají přiřazena různé cifry i SaM nejsou 0 M domain([E,N,D,0,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 -• all_distinct( [S,E,N,D,M,0,R,Y] ) -• labelingC [S,E,N,D,M,0,R,Y] ) Hana Rudová, Logické programování I, 1 7. dubna 2009 1 1 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 3 CLP(J4.) generický jazyk 3 CLP(FD) domény proměnných jsou konečné (Finite Domains) 3 CLP(M) doménou proměnných je množina reálných čísel Hana Rudová, Logické programování I, 1 7. dubna 2009 1 2 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 3 CLP(J4.) generický jazyk 3 CLP(FD) domény proměnných jsou konečné (Finite Domains) 3 CLP(M) doménou proměnných je množina reálných čísel -• Cíl 3 využít syntaktické a výrazové přednosti LP 3 dosáhnout větší efektivity Hana Rudová, Logické programování I, 1 7. dubna 2009 12 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 3 CLP(J4.) generický jazyk 3 CLP(FD) domény proměnných jsou konečné (Finite Domains) 3 CLP(M) doménou proměnných je množina reálných čísel -• Cíl 3 využít syntaktické a výrazové přednosti LP 3 dosáhnout větší efektivity -• Unifikace v LP je nahrazena splňováním podmínek 3 unifikace se chápe jako jedna z podmínek 3 A = B 3 A #< B, A in 0..9, domain([A, B] ,0,9), all_distinct([A,B,C]) Hana Rudová, Logické programování I, 1 7. dubna 2009 1 2 Logické programování s omezujícími podmínkami Od LP k CLP II. -• Pro řešení podmínek se používají konzistenční techniky -• consistency techniques, propagace omezení (constraint propagation) M omezení: A in 0..2, B in 0..2, B #< A Hana Rudová, Logické programování I, 1 7. dubna 2009 1 3 Logické programování s omezujícími podmínkami Od LP k CLP II. -• Pro řešení podmínek se používají konzistenční techniky -• consistency techniques, propagace omezení (constraint propagation) M 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, 1 7. dubna 2009 13 Logické programování s omezujícími podmínkami Od LP k CLP II. -• Pro řešení podmínek se používají konzistenční techniky -• consistency techniques, propagace omezení (constraint propagation) M 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 3 Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky Hana Rudová, Logické programování I, 1 7. dubna 2009 1 3 Logické programování s omezujícími podmínkami Od LP k CLP II. -• Pro řešení podmínek se používají konzistenční techniky -• consistency techniques, propagace omezení (constraint propagation) M 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 3 Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky -0 Prohledávání doplněno konzistenčními technikami M A in 1. .2, B in 0. .1, B #< A Hana Rudová, Logické programování I, 1 7. dubna 2009 13 Logické programování s omezujícími podmínkami Od LP k CLP II. -• Pro řešení podmínek se používají konzistenční techniky -• consistency techniques, propagace omezení (constraint propagation) M 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 3 Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky -0 Prohledávání doplněno konzistenčními technikami M A in 1. .2, B in 0. .1, B #< A 3 po provedení A #= 1 se z B #< A se odvodí: B #= 0 Hana Rudová, Logické programování I, 1 7. dubna 2009 1 3 Logické programování s omezujícími podmínkami Od LP k CLP II. -• Pro řešení podmínek se používají konzistenční techniky -• consistency techniques, propagace omezení (constraint propagation) M 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 3 Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky -0 Prohledávání doplněno konzistenčními technikami M A in 1. .2, B in 0. .1, B #< A 3 po provedení A #= 1 se z B #< A se odvodí: B #= 0 -• Podmínky jako výstup 3 kompaktní reprezentace nekonečného počtu řešení, výstup lze použít jako vstup Hana Rudová, Logické programování I, 1 7. dubna 2009 1 3 Logické programování s omezujícími podmínkami Od LP k CLP II. -• Pro řešení podmínek se používají konzistenční techniky -• consistency techniques, propagace omezení (constraint propagation) M 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 3 Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky -0 Prohledávání doplněno konzistenčními technikami M A in 1. .2, B in 0. .1, B #< A 3 po provedení A #= 1 se z B #< A se odvodí: B #= 0 -• Podmínky jako výstup 3 kompaktní reprezentace nekonečného počtu řešení, výstup lze použít jako vstup -• 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, 1 7. dubna 2009 1 3 Logické programování s omezujícími podmínkami Od LP k CLP II. -• Pro řešení podmínek se používají konzistenční techniky -• consistency techniques, propagace omezení (constraint propagation) M 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 3 Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky -0 Prohledávání doplněno konzistenčními technikami M A in 1. .2, B in 0. .1, B #< A 3 po provedení A #= 1 se z B #< A se odvodí: B #= 0 -• Podmínky jako výstup 3 kompaktní reprezentace nekonečného počtu řešení, výstup lze použít jako vstup -• 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, 1 7. dubna 2009 1 3 Logické programování s omezujícími podmínkami Syntaxe CLP -• Výběr jazyka omezení M CLP klauzule jako LP klauzule, ale její tělo může obsahovat omezení daného jazyka p(X,Y) :- X #< Y+l, q(X), r(X,Y,Z). -• Rezoluční krok v LP M kontrola existence mgu mezi cílem a hlavou -• Krok odvození v CLP také zahrnuje -• kontrola konzistence aktuální množiny omezení s omezeními v těle klauzule => Vyvolání dvou řešičů: unifikace + řešič omezení Hana Rudová, Logické programování I, 1 7. dubna 2009 14 Logické programování s omezujícími podmínkami Operační sémantika CLP -• CLP výpočet cíle G M Store množina aktivních omezení = prostor omezení (constraint store) M inicializace Store = 0 3 seznamy cílů v G prováděny v obvyklém pořadí -• pokud narazíme na cíl s omezením c: NewStore = Store u {c} M snažíme se splnit c vyvoláním jeho řešiče s* při neúspěchu se vyvolá backtracking s* při úspěchu se podmínky v NewStore zjednoduší propagací omezení 3 zbývající cíle jsou prováděny s upraveným NewStore M CLP výpočet cíle G je úspěš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, 1 7. dubna 2009 15 Logické programování s omezujícími podmínkami CLP(FD) v SICStus Prologu Nejpoužívanější systémy a jazyky pro CP -• Swedish Institute of Computer Science: SICStus Prolog 1 985 -• silná CLP(FD) knihovna, komerční i akademické použití pro širokou škálu platforem Hana Rudová, Logické programování I, 17. dubna 2009 17 CLP(FD) v SICStus Prologu Nejpoužívanější systémy a jazyky pro CP -• Swedish Institute of Computer Science: SICStus Prolog 1 985 -• silná CLP(FD) knihovna, komerční i akademické použití pro širokou škálu platforem M IC-PARC, Imperial College London, Cisco Systems: ECL*PSe 1 984 M široké možnosti kooperace mezi různými řešičemi: konečné domény, reálná čísla, repai r -• od 2004 vlastní Cisco Systems volně dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris Hana Rudová, Logické programování I, 1 7. dubna 2009 17 CLP(FD) v SICStus Prologu Nejpoužívanější systémy a jazyky pro CP -• Swedish Institute of Computer Science: SICStus Prolog 1 985 -• silná CLP(FD) knihovna, komerční i akademické použití pro širokou škálu platforem M IC-PARC, Imperial College London, Cisco Systems: EClJPS6 1 984 M široké možnosti kooperace mezi různými řešičemi: konečné domény, reálná čísla, repai r -• od 2004 vlastní Cisco Systems volně dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris -• ILOG, omezující podmínky v C++ 1987 M komerční společnost, vznik ve Francie, nyní rozšířená po celém světě M implementace podmínek založena na objektově orientovaném programování Hana Rudová, Logické programování I, 1 7. dubna 2009 17 CLP(FD) v SICStus Prologu Nejpoužívanější systémy a jazyky pro CP -• Swedish Institute of Computer Science: SICStus Prolog 1 985 -• silná CLP(FD) knihovna, komerční i akademické použití pro širokou škálu platforem M IC-PARC, Imperial College London, Cisco Systems: EClJPS6 1 984 M široké možnosti kooperace mezi různými řešičemi: konečné domény, reálná čísla, repai r -• od 2004 vlastní Cisco Systems volně dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris -• ILOG, omezující podmínky v C++ 1987 M komerční společnost, vznik ve Francie, nyní rozšířená po celém světě M implementace podmínek založena na objektově orientovaném programování M http://www.fi.muni.cz/~hanka/bookmarks.html#tools -• cca 50 odkazů na nejrůznější systémy: Prolog, C++, Java, Lisp, ... M COSYTEC: CHIP, ProloglA: Prolog IV, Siemens: IF Prolog, akademický: Mozart (objektově orientované, deklarativní programování, concurrency), ... Hana Rudová, Logické programování I, 17. dubna 2009 17 CLP(FD) v SICStus Prologu CLP(FD) v SICStus Prologu -• CLP není dostupné v SWI Prologu -• CLP knihovna v ECLiPSe se liší -• Vestavěné predikáty jsou dostupné v separátním modulu (knihovně) :- use_module(library(clpfd)). -• Obecné principy platné všude -• Stejné/podobné vestavěné predikáty existují i jinde Hana Rudová, Logické programování I, 1 7. dubna 2009 18 CLP(FD) v SICStus Prologu Příslušnost k doméně: Range termy M ?- domainC [A,B], 1,3). domain( +Variables, +Min, +Max) A in 1. . 3 B in 1..3 Hana Rudová, Logické programování I, 17. dubna 2009 19 CLP(FD) v SICStus Prologu Příslušnost k doméně: Range termy M ?- domainC [A,B], 1,3). domain( +Variables, +Min, +Max) A in 1. . 3 B in 1..3 i ?- Ain 1..8, A#\=4. ?X in +Min. .+Max A in (1..3) \/ (5..8) Hana Rudová, Logické programování I, 1 7. dubna 2009 19 CLP(FD) v SICStus Prologu Příslušnost k doméně: Range termy M ?- domainC [A,B], 1,3). domain( +Variables, +Min, +Max) A in 1. . 3 B in 1..3 i ?- Ain 1..8, A#\=4. ?X in +Min. .+Max A in (1..3) \/ (5..8) -• Doména reprezentována jako posloupnost intervalů celých čísel -• ?- 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, 1 7. dubna 2009 19 CLP(FD) v SICStus Prologu Příslušnost k doméně: Range termy M ?- domainC [A,B], 1,3). domain( +Variables, +Min, +Max) A in 1. . 3 B in 1..3 i ?- Ain 1..8, A#\=4. ?X in +Min. .+Max A in (1..3) \/ (5..8) -• Doména reprezentována jako posloupnost intervalů celých čísel -• ?- A in (1..3) \/ (8..15) \/ (5..9) \/ {100}. ?X in +Range A in (1..3) \/ (5..15) \/ {100} M Zjištění domény Range proměnné Var: fd_dom(?Var,?Range) 3 A in 1..8, A #\= 4, fd_dom(A,Range). Range=(1..3) \/ (5..8) Hana Rudová, Logické programování I, 1 7. dubna 2009 19 CLP(FD) v SICStus Prologu Příslušnost k doméně: Range termy M ?- domainC [A,B], 1,3). domain( +Variables, +Min, +Max) A in 1. . 3 B in 1..3 i ?- Ain 1..8, A#\=4. ?X in +Min. .+Max A in (1..3) \/ (5..8) -• Doména reprezentována jako posloupnost intervalů celých čísel -• ?- A in (1..3) \/ (8..15) \/ (5..9) \/ {100}. ?X in +Range A in (1..3) \/ (5..15) \/ {100} M Zjištění domény Range proměnné 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,(l..3) \/ (5..8)). no Hana Rudová, Logické programování I, 1 7. dubna 2009 19 CLP(FD) v SICStus Prologu Příslušnost k doméně: Range termy ?- domainC [A,B], 1,3). domain( +Variables, +Min, +Max) A in 1..3 B in 1..3 ?- 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 čísel ?- A in (1..3) \/ (8..15) \/ (5..9) \/ {100}. ?X in +Range A in (1..3) \/ (5..15) \/ {100} Zjištění domény Range proměnné Var: fd_dom(?Var,?Range) «• A in 1..8, A #\= 4, fd_dom(A,Range). Range=(1..3) \/ (5..8) 3 A in 2..10, fd_dom(A,(l..3) \/ (5..8)). no Range term: reprezentace nezávislá na implementaci Hana Rudová, Logické programování I, 1 7. dubna 2009 19 CLP(FD) v SICStus Prologu Příslušnost k doméně: FDSet termy -• 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 = [[113],[5|8]] Hana Rudová, Logické programování I, 1 7. dubna 2009 20 CLP(FD) v SICStus Prologu Příslušnost k doméně: FDSet termy -• 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 = [[113],[5|8]] J ?- A in 1..8,A#\=4, fd_set(A,FDSet),B in_set FDSet. ?X i n_set +FDSet A in (1..3) \/ (5..8) FDSet = [[113],[5|8]] B in (1..3) \/ (5..8) Hana Rudová, Logické programování I, 1 7. dubna 2009 20 CLP(FD) v SICStus Prologu Příslušnost k doméně: FDSet termy -• 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 = [[113],[5|8]] J ?- A in 1..8,A#\=4, fd_set(A,FDSet),B in_set FDSet. ?X i n_set +FDSet A in (1..3) \/ (5..8) FDSet = [[113],[5|8]] B in (1..3) \/ (5..8) M FDSet termy představují nízko-úrovňovou implementaci M FDSet termy nedoporučeny v programech 3 používat pouze predikáty pro manipulaci s nimi ^ omezit použití A in_set [[1| 2] , [6| 9]] «• Range termy preferovány Hana Rudová, Logické programování I, 17. dubna 2009 20 CLP(FD) v SICStus Prologu Další fcL. . . predikáty -• fdset_to_list(+FDset, -List) vrací do seznamu prvky FDset M list_to_fdset(+List, -FDset) vrací FDset odpovídající seznamu -• fd_var(?Var) je Var doménová proměnná? -• fd_min(?Var ,?Min) nejmenší hodnota v doméně -• fd_max(?Var,?Max) největší hodnota v doméně M fd_size(?Var,?Size) velikost domény -• fd_degree(?Var ,?Degree) počet navázaných omezení na proměnné Hana Rudová, Logické programování I, 1 7. dubna 2009 21 CLP(FD) v SICStus Prologu Další fcL. . . predikáty -• fdset_to_list(+FDset, -List) vrací do seznamu prvky FDset M list_to_fdset(+List, -FDset) vrací FDset odpovídající seznamu -• fd_var(?Var) je Var doménová proměnná? -• fd_min(?Var ,?Min) nejmenší hodnota v doméně -• fd_max(?Var,?Max) největší hodnota v doméně M fd_size(?Var,?Size) velikost domény -• fd_degree(?Var ,?Degree) počet navázaných omezení na proměnné 3 mění se během výpočtu: pouze aktivní omezení, i odvozená aktivní omezení Hana Rudová, Logické programování I, 1 7. dubna 2009 21 CLP(FD) v SICStus Prologu Aritmetická omezení -• Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>= M A + B #=< 3, A #\= (C - 4) * ( D - 5) , A/2 #= 4 Hana Rudová, Logické programování I, 1 7. dubna 2009 22 CLP(FD) v SICStus Prologu Aritmetická omezení -• Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>= -• A + B #=< 3, A #\= (C - 4) * ( D - 5) , A/2 #= 4 -• sum(Variables,RelOp,Suma) -• domain ([A, B, C, F] ,1,3) , sum([A,B,C],#= ,F) Hana Rudová, Logické programování I, 1 7. dubna 2009 22 CLP(FD) v SICStus Prologu Aritmetická omezení -• Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>= -• A + B #=< 3, A #\= (C - 4) * ( D - 5) , A/2 #= 4 -• sum(Variables,RelOp,Suma) -• domain ([A, B, C, F] ,1,3) , sum([A,B,C],#= ,F) -• scalar_product(Coeffs,Variables,RelOp,ScalarProduct) 3 domain([A,B,C,F],1,6), scalar_product( [1,2,3],[A,B,C],#= ,F) Hana Rudová, Logické programování I, 1 7. dubna 2009 22 CLP(FD) v SICStus Prologu Výroková omezení, reifikace -• Výroková omezení pozor na efektivitu -• \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ... ^ X #> 4 #/\ Y #< 6 Hana Rudová, Logické programování I, 1 7. dubna 2009 23 CLP(FD) v SICStus Prologu Výroková omezení, reifikace -• Výroková omezení pozor na efektivitu -• \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ... ^ X #> 4 #/\ Y #< 6 «• za předpokladu A in 1. .4: A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=l #\/ A#=2 A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup Hana Rudová, Logické programování I, 1 7. dubna 2009 23 CLP(FD) v SICStus Prologu Výroková omezení, reifikace -• Výroková omezení pozor na efektivitu -• \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ... ^ X #> 4 #/\ Y #< 6 «• za předpokladu A in 1. .4: A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=l #\/ A#=2 A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup tj. propagace disjunkce A#=l #\/ A#=2 je příliš slabá (propagační algoritmy příliš obecné) Hana Rudová, Logické programování I, 1 7. dubna 2009 23 CLP(FD) v SICStus Prologu Výroková omezení, reifikace -• Výroková omezení pozor na efektivitu -• \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ... ^ X #> 4 #/\ Y #< 6 «• za předpokladu A in 1. .4: A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=l #\/ A#=2 A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup tj. propagace disjunkce A#=l #\/ A#=2 je příliš slabá (propagační algoritmy příliš obecné) M Reifikace pozor na efektivitu M Constraint #<=> Bool Bool in 0. .1 v závislosti na tom, zda je Constraint splněn M příklad: A in 1..10 #<=> Bool Hana Rudová, Logické programování I, 1 7. dubna 2009 23 CLP(FD) v SICStus Prologu Výroková omezení, reifikace Výroková omezení pozor na efektivitu -• \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ... ^ X #> 4 #/\ Y #< 6 «• za předpokladu A in 1. .4: A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=l #\/ A#=2 A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup tj. propagace disjunkce A#=l #\/ A#=2 je příliš slabá (propagační algoritmy příliš obecné) Reifikace pozor na efektivitu M Constraint #<=> Bool Bool in 0. .1 v závislosti na tom, zda je Constraint splněn M příklad: A in 1..10 #<=> Bool M za předpokladu X in 3.. 10, Y in 1..4, Bool in 0..1 porovnej rozdíl mezi X# Bool Hana Rudová, Logické programování I, 1 7. dubna 2009 23 CLP(FD) v SICStus Prologu Výroková omezení, reifikace -• Výroková omezení pozor na efektivitu -• \# negace, #/\ konjunkce, #\/ disjunkce, #<=> ekvivalence, ... ^ X #> 4 #/\ Y #< 6 «• za předpokladu A in 1. .4: A#\= 3, A#\= 4 A#\= 3 #/\ A#\= 4 A#=l #\/ A#=2 A in (inf..2)\/ (5..sup) A in (inf..2)\/ (5..sup) A in inf..sup tj. propagace disjunkce A#=l #\/ A#=2 je příliš slabá (propagační algoritmy příliš obecné) M Reifikace pozor na efektivitu M Constraint #<=> Bool Bool in 0. .1 v závislosti na tom, zda je Constraint splněn M příklad: A in 1..10 #<=> Bool M za předpokladu X in 3.. 10, Y in 1..4, Bool in 0..1 porovnej rozdíl mezi X# Bool X= 3, Y = 4 X in 3..10, Yin 1..4, Bool in 0..1 Hana Rudová, Logické programování I, 17. dubna 2009 23 CLP(FD) v SICStus Prologu Příklad: reifikace -• Přesně N prvků v seznamu S je rovno X: exactly(X,S,N) Hana Rudová, Logické programování I, 17. dubna 2009 24 CLP(FD) v SICStus Prologu Příklad: reifikace -• Přesně N prvků v seznamu S je rovno X: exactly(X,S,N) exactly(_, [], 0). Hana Rudová, Logické programování I, 1 7. dubna 2009 24 CLP(FD) v SICStus Prologu Příklad: reifikace -• Přesně N prvků v seznamu S je rovno X: exactly(X,S,N) exactly(_, [], 0). exactly(X, [Y|L], N) :- X #= Y #<=> B, % reifikace Hana Rudová, Logické programování I, 1 7. dubna 2009 24 CLP(FD) v SICStus Prologu Příklad: reifikace -• Přesně N prvků v seznamu S je rovno X: exactly(X,S,N) exactly(_, [], 0). exactly(X, [Y|L], N) :- X #= Y #<=> B, % reifikace N #= M+B, % doménová proměnná místo akumulátoru exactly(X, L, M). Hana Rudová, Logické programování I, 1 7. dubna 2009 24 CLP(FD) v SICStus Prologu Příklad: reifikace -• Přesně N prvků v seznamu S je rovno X: exactly(X,S,N) exactly(_, [], 0). exactly(X, [Y|L], N) :- X #= Y #<=> B, % reifikace N #= M+B, % doménová proměnná místo akumulátoru exactly(X, L, M). M | ?- domain([A,B,C,D,E,N],1,2), exactlyCl,[A,B,C,D,E],N), Hana Rudová, Logické programování I, 1 7. dubna 2009 24 CLP(FD) v SICStus Prologu Příklad: reifikace -• Přesně N prvků v seznamu S je rovno X: exactly(X,S,N) exactly(_, [], 0). exactly(X, [Y|L], N) :- X #= Y #<=> B, % reifikace N #= M+B, % doménová proměnná místo akumulátoru exactly(X, L, M). M | ?- domain([A,B,C,D,E,N],1,2), exactlyCl,[A,B,C,D,E],N),A#< 2, Hana Rudová, Logické programování I, 1 7. dubna 2009 24 CLP(FD) v SICStus Prologu Příklad: reifikace -• Přesně N prvků v seznamu S je rovno X: exactly(X,S,N) exactly(_, [], 0). exactly(X, [Y|L], N) :- X #= Y #<=> B, % reifikace N #= M+B, % doménová proměnná místo akumulátoru exactly(X, L, M). M | ?- domain([A,B,C,D,E,N],1,2), exactlyCl,[A,B,C,D,E],N),A#< 2,B#< 2. Hana Rudová, Logické programování I, 1 7. dubna 2009 24 CLP(FD) v SICStus Prologu Příklad: reifikace -• Přesně N prvků v seznamu S je rovno X: exactly(X,S,N) exactly(_, [], 0). exactly(X, [Y|L], N) :- X #= Y #<=> B, % reifikace N #= M+B, % doménová proměnná místo akumulátoru exactly(X, L, M). M | ?- domain([A,B,C,D,E,N],1,2), exactlyCl,[A,B,C,D,E],N),A#< 2,B#< 2. A=l, B=l, C=2, D=2, E=2, N=2 Hana Rudová, Logické programování I, 1 7. dubna 2009 24 CLP(FD) v SICStus Prologu Příklad: reifikace -• Přesně N prvků v seznamu S je rovno X: exactly(X,S,N) exactly(_, [], 0). exactly(X, [Y|L], N) :- X #= Y #<=> B, % reifikace N #= M+B, % doménová proměnná místo akumulátoru exactly(X, L, M). M | ?- domain([A,B,C,D,E,N],1,2), exactlyCl,[A,B,C,D,E],N),A#< 2,B#< 2. A=l, B=l, C=2, D=2, E=2, N=2 -• Vyzkoušejte si M greaters(X,S,N): přesně N prvků v seznamu S je větší než X -• atleast(X,S,N): alespoň N prvků v seznamu S je rovno X M atmost(X,S,N): nejvýše N prvků v seznamu S je rovno X Hana Rudová, Logické programování I, 1 7. dubna 2009 24 CLP(FD) v SICStus Prologu Základní kombinatorická omezení -• element(N,List,X) -• omezení na konkrétní prvek seznamu M global_cardinality(l_ist, [Key-Count I _ ]) * omezení na počet prvků daného typu v seznamu Hana Rudová, Logické programování I, 17. dubna 2009 25 CLP(FD) v SICStus Prologu Základní kombinatorická omezení -• element(N,List,X) -• omezení na konkrétní prvek seznamu M global_cardinality(l_ist, [Key-Count I _ ]) 3 omezení na počet prvků daného typu v seznamu -• all_distinet(List) 3 všechny proměnné různé Hana Rudová, Logické programování I, 17. dubna 2009 25 CLP(FD) v SICStus Prologu Základní kombinatorická omezení -• element(N,List,X) -• omezení na konkrétní prvek seznamu M global_cardinality(List, [Key-Count I _ ]) 3 omezení na počet prvků daného typu v seznamu -• all_distinet(List) 3 všechny proměnné různé -• serialized(Starts,Durations) M disjunktivní rozvrhování -• disjoint2(Rectangles) -• nepřekrývání obdélníků M cumulative(Starts,Durations,Resources,Limit) M kumulativní rozvrhování Hana Rudová, Logické programování I, 17. dubna 2009 25 CLP(FD) v SICStus Prologu Výskyty prvků v seznamu -• element(N,List,X) M N-tý prvek v seznamu Li st je roven X M | ?- A in 2..10, B in 1..3, elementC N, [A,B], X ), Hana Rudová, Logické programování I, 17. dubna 2009 26 CLP(FD) v SICStus Prologu Výskyty prvků v seznamu -• element(N,List,X) M N-tý prvek v seznamu Li st je roven X 3 I ?- A in 2..10, B in 1..3, elementC N, [A,B], X ), X#< 2. B= 1, N = 2,X= 1, Ain 2..10 Hana Rudová, Logické programování I, 1 7. dubna 2009 26 CLP(FD) v SICStus Prologu Výskyty prvků v seznamu -• element(N,List,X) M N-tý prvek v seznamu Li st je roven X 3 I ?- A in 2..10, B in 1..3, elementC N, [A,B], X ), X#< 2. B= 1, N = 2,X= 1, Ain 2..10 -• global_cardinality(l_ist, KeyCounts) M pro každý prvek Key-Count seznamu KeyCounts platí: Count prvků seznamu List se rovná klíči Key M každé Key je celé číslo a vyskytuje se mezi klíči maximálně jednou Hana Rudová, Logické programování I, 1 7. dubna 2009 26 CLP(FD) v SICStus Prologu Výskyty prvků v seznamu -• element(N,List,X) M N-tý prvek v seznamu Li st je roven X 3 I ?- A in 2..10, B in 1..3, elementC N, [A,B], X ), X#< 2. B= 1, N = 2,X= 1, Ain 2..10 -• global_cardinality(l_ist, KeyCounts) M pro každý prvek Key-Count seznamu KeyCounts platí: Count prvků seznamu List se rovná klíči Key M každé Key je celé číslo a vyskytuje se mezi klíči maximálně jednou M global_cardinality(S, [X-N] ) je obdobné omezení exactly(X,S,N) Hana Rudová, Logické programování I, 1 7. dubna 2009 26 CLP(FD) v SICStus Prologu Výskyty prvků v seznamu -• element(N,List,X) M N-tý prvek v seznamu Li st je roven X 3 I ?- A in 2..10, B in 1..3, elementC N, [A,B], X ), X#< 2. B= 1, N = 2,X= 1, Ain 2..10 -• global_cardinality(l_ist, KeyCounts) M pro každý prvek Key-Count seznamu KeyCounts platí: Count prvků seznamu List se rovná klíči Key M každé Key je celé číslo a vyskytuje se mezi klíči maximálně jednou M global_cardinality(S, [X-N] ) je obdobné omezení exactly(X,S,N) M | ?- A in 1..3, B in 1..3, global_cardinality( [A,B], [l-N,2-2]). Hana Rudová, Logické programování I, 1 7. dubna 2009 26 CLP(FD) v SICStus Prologu Výskyty prvků v seznamu -• element(N,List,X) M N-tý prvek v seznamu Li st je roven X 3 I ?- A in 2..10, B in 1..3, elementC N, [A,B], X ), X#< 2. B= 1, N = 2,X= 1, Ain 2..10 -• global_cardinality(l_ist, KeyCounts) M pro každý prvek Key-Count seznamu KeyCounts platí: Count prvků seznamu List se rovná klíči Key M každé Key je celé číslo a vyskytuje se mezi klíči maximálně jednou M global_cardinality(S, [X-N] ) je obdobné omezení exactly(X,S,N) M | ?- A in 1..3, B in 1..3, global_cardinality( [A,B], [l-N,2-2]). A=2, B=2, N=0 Hana Rudová, Logické programování I, 1 7. dubna 2009 26 CLP(FD) v SICStus Prologu Příklad: rozvrhování zaměstnanců -• vytvoření rozvrhu pro zaměstnance pracující na směny 3 A = {R,D,N,Z,V} ráno, den, noc, záloha, volno •• P = {Petr, Pavel , Marie, . . .} M W = {Po,Út,St,Čt,...} Po Út St Čt ... Petr R N v R Pavel R Z R N Marie N V D D ... Hana Rudová, Logické programování I, 1 7. dubna 2009 27 CLP(FD) v SICStus Prologu Příklad: rozvrhování zaměstnanců -• vytvoření rozvrhu pro zaměstnance pracující na směny 3 A = {R,D,N,Z,V} ráno, den, noc, záloha, volno •• P = {Petr, Pavel , Marie, . . .} M W = {Po,Út,St,Čt,...} -• matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... Po Út St Čt ... Petr R N v R Pavel R Z R N Marie N V D D ... Hana Rudová, Logické programování I, 1 7. dubna 2009 27 CLP(FD) v SICStus Prologu Příklad: rozvrhování zaměstnanců -• vytvoření rozvrhu pro zaměstnance pracující na směny 3 A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno •• P = {Petr, Pavel , Marie, . . .} M W = {Po,Út,St,Čt,...} -• matice doménových proměnných: PetrPo, PetrUt, ..., PavelPo,... Po Út St Čt ... Petr R N v R Pavel R Z R N Marie N V D D ... Hana Rudová, Logické programování I, 1 7. dubna 2009 27 CLP(FD) v SICStus Prologu Příklad: rozvrhování zaměstnanců -• vytvoření rozvrhu pro zaměstnance pracující na směny 3 A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno •• P = {Petr, Pavel , Marie, . . .} M W = {Po,Út,St,Čt,...} -• matice doménových proměnných: PetrPo, Petrllt, ..., PavelPo,... -• každý den: minimální a maximální počet zaměstnanců každou směnu Po Út St Čt ... Petr R N v R Pavel R Z R N Marie N V D D ... Hana Rudová, Logické programování I, 1 7. dubna 2009 27 CLP(FD) v SICStus Prologu Příklad: rozvrhování zaměstnanců -• vytvoření rozvrhu pro zaměstnance pracující na směny 3 A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno •• P = {Petr, Pavel , Marie, . . .} M W = {Po,Út,St,Čt,...} -• matice doménových proměnných: PetrPo, Petrllt, ..., PavelPo,... -• každý den: minimální a maximální počet zaměstnanců každou směnu Rl in MinRanol..MaxRanol, Dl in MinDenl..MaxDenl, ... Po Út St Čt ... Petr R N v R Pavel R Z R N Marie N V D D ... Hana Rudová, Logické programování I, 1 7. dubna 2009 27 CLP(FD) v SICStus Prologu Příklad: rozvrhování zaměstnanců -• vytvoření rozvrhu pro zaměstnance pracující na směny 3 A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno •• P = {Petr, Pavel , Marie, . . .} M W = {Po,Út,St,Čt,...} -• matice doménových proměnných: PetrPo, Petrllt, ..., PavelPo,... -• každý den: minimální a maximální počet zaměstnanců každou směnu Rl in MinRanol..MaxRanol, Dl in MinDenl..MaxDenl, ... global_cardinality( [PetrPo,Pavel Po,MariePo,...], [1-R1.2-D1,...,5-V1] ) Po Út St Čt ... Petr R N v R Pavel R Z R N Marie N V D D ... Hana Rudová, Logické programování I, 1 7. dubna 2009 27 CLP(FD) v SICStus Prologu Příklad: rozvrhování zaměstnanců -• vytvoření rozvrhu pro zaměstnance pracující na směny 3 A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno •• P = {Petr, Pavel , Marie, . . .} M W = {Po,Út,St,Čt,...} -• matice doménových proměnných: PetrPo, Petrllt, ..., PavelPo,... -• každý den: minimální a maximální počet zaměstnanců každou směnu Rl in MinRanol..MaxRanol, Dl in MinDenl..MaxDenl, ... global_cardinality( [PetrPo,Pavel Po,MariePo,...], [1-R1.2-D1,...,5-V1] ) -• pro každého zaměstnance: minimální a maximální počet typu směny za týden Po Út St Čt ... Petr R N v R Pavel R Z R N Marie N V D D ... Hana Rudová, Logické programování I, 1 7. dubna 2009 27 CLP(FD) v SICStus Prologu Příklad: rozvrhování zaměstnanců -• vytvoření rozvrhu pro zaměstnance pracující na směny 3 A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno •• P = {Petr, Pavel , Marie, . . .} M W = {Po,Út,St,Čt,...} -• matice doménových proměnných: PetrPo, Petrllt, ..., PavelPo,... -• každý den: minimální a maximální počet zaměstnanců každou směnu Rl in MinRanol..MaxRanol, Dl in MinDenl..MaxDenl, ... global_cardinality( [PetrPo,Pavel Po,MariePo,...], [1-R1.2-D1,...,5-V1] ) -• pro každého zaměstnance: minimální a maximální počet typu směny za týden R2 in MinRano2..MaxRano2, D2 in MinDen2..MaxDen2, ... Hana Rudová, Logické programování I, 17. dubna 2009 27 CLP(FD) v SICStus Prologu Po Út St Čt ... Petr R N v R Pavel R Z R N Marie N V D D ... Příklad: rozvrhování zaměstnanců -• vytvoření rozvrhu pro zaměstnance pracující na směny 3 A = {R,D,N,Z,V} = {1,2,3,4,5} ráno, den, noc, záloha, volno •• P = {Petr, Pavel , Marie, . . .} M W = {Po,Út,St,Čt,...} -• matice doménových proměnných: PetrPo, Petrllt, ..., PavelPo,... -• každý den: minimální a maximální počet zaměstnanců každou směnu Rl in MinRanol..MaxRanol, Dl in MinDenl..MaxDenl, ... global_cardinality( [PetrPo,Pavel Po,MariePo,...], [1-R1.2-D1,...,5-V1] ) -• pro každého zaměstnance: minimální a maximální počet typu směny za týden R2 in MinRano2..MaxRano2, D2 in MinDen2..MaxDen2, ... global_cardinality( [PetrPo, Petrllt, ..., PetrNe] , [1-R2 , 2-D2 , . . . , 5-V2] ) Hana Rudová, Logické programování I, 17. dubna 2009 27 CLP(FD) v SICStus Prologu Po Út St Čt ... Petr R N v R Pavel R Z R N Marie N V D D ... Všechny proměnné různé -• all_distinct(Variables), all_different(Variables) -• Proměnné v seznamu Variables jsou různé M all_distinct a all_different se liší úrovní propagace M all_distinct má úplnou propagaci M all_different má slabší (neúplnou) propagaci Hana Rudová, Logické programování I, 1 7. dubna 2009 28 CLP(FD) v SICStus Prologu Všechny proměnné různé all_di sti net(Vari ables), all_di fferent(Vari ables) Proměnné v seznamu Variables jsou různé all_distinct a all_different se liší úrovní propagace M all_distinct má úplnou propagaci M all_different má slabší (neúplnou) propagaci Příklad: učitelé musí učit v různé hodiny 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, 1 7. dubna 2009 28 CLP(FD) v SICStus Prologu Všechny proměnné různé -• all_distinct(Variables), all_different(Variables) -• Proměnné v seznamu Variables jsou různé M all_distinct a all_different se liší úrovní propagace M all_distinct má úplnou propagaci M all_different má slabší (neúplnou) propagaci -• Příklad: učitelé musí učit v různé hodiny -• all_distinct([Ilan, Petr,Anna,Ota, Eva,Marie]) Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr in 3..4, Eva in 3..4 Hana Rudová, Logické programování I, 17. dubna 2009 28 CLP(FD) v SICStus Prologu učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Všechny proměnné různé -• all_distinct(Variables), all_different(Variables) -• Proměnné v seznamu Variables jsou různé M all_distinct a all_different se liší úrovní propagace M all_distinct má úplnou propagaci M all_different má slabší (neúplnou) propagaci -• Příklad: učitelé musí učit v různé hodiny -• all_distinct([Jan, Petr,Anna,Ota, Eva,Marie]) Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr in 3..4, Eva in 3..4 M all_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 Hana Rudová, Logické programování I, 17. dubna 2009 28 CLP(FD) v SICStus Prologu učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Disjunktivní rozvrhování -• serialized(Starts,Durations) M Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Durations) tak, aby se nepřekrývaly Hana Rudová, Logické programování I, 1 7. dubna 2009 29 CLP(FD) v SICStus Prologu Disjunktivní rozvrhování sen" al i zed (Starts, Durati ons) Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Durations) tak, aby se nepřekrývaly příklad s konstantami: serial i zed([0,3,5],[2,1,1]) 2 - L--------------------------------------------1 I-------------------1 I------------------- i. 2 3 1 2 5 Hana Rudová, Logické programování I, 1 7. dubna 2009 29 CLP(FD) v SICStus Prologu Disjunktivní rozvrhování sen" al i zed (Starts, Durati ons) Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Durations) tak, aby se nepřekrývaly příklad s konstantami: serialized([0,3,5],[2,l ,1]) 2 - L--------------------------------------------1 I-------------------1 I------------------- i. 2 3 L 2 5 příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná Hana Rudová, Logické programování I, 1 7. dubna 2009 29 CLP(FD) v SICStus Prologu Disjunktivní rozvrhování sen" al i zed (Starts, Durati ons) Rozvržení úloh zadaných startovním časem (seznam Starts) a dobou trvání (seznam nezáporných Durations) tak, aby se nepřekrývaly M příklad s konstantami: serialized([0,3,5],[2,l ,1]) 2 - L--------------------------------------------1 I-------------------1 I------------------- 1. 2 3 L 2 5 6 příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná i* D in 1. .2, C = 3, se ri ali zed([3 an,Pet r,Anna,Ota,Eva,Mari e], [D,D,D,C,C,C]) Hana Rudová, Logické programování I, 1 7. dubna 2009 29 CLP(FD) v SICStus Prologu Nepřekrývání obdélníků -• disjoint2(Rectangles) disjointl(Lines) disjoint2( [Name(X, Délka, Y, Vyska) | _ ] ) -• umístění obdélníků ve dvourozměrném prostoru doménové proměnné X,Y,Délka,Vyska mohou být z oboru celých čísel Hana Rudová, Logické programování I, 1 7. dubna 2009 30 CLP(FD) v SICStus Prologu Nepřekrývání obdélníku di sjoi nt2(Rectangles) di sjoi ntl(Li nes) disjoint2( [Name(X, Délka, Y, Vyska) | _ ] ) umístění obdélníků ve dvourozměrném prostoru doménové proměnné X,Y,Délka,Vyska mohou být z oboru celých čísel 3 příklad s konstantami: disjoint2([rect(0,3,0,l),rect(l,3,l,2),rect(4,2,2,-2)]) 2 _ 2 ------------ 1----------'----------------1-------- 3 1 6 Hana Rudová, Logické programování I, 1 7. dubna 2009 30 CLP(FD) v SICStus Prologu Nepřekrývání obdélníků di sj oi nt2(Rectangles) disjoint2( [Name(X, Délka, Y, Vyska) | _ ] ) disjointl(Lines) umístění obdélníků ve dvourozměrném prostoru doménové proměnné X,Y,Délka,Vyska mohou být z oboru celých čísel 3 příklad s konstantami: disjoint2([rect(0,3,0,l),rect(l,3,l,2),rect(4,2,2,-2)]) 2 _ 2 ------------ 1----------'----------------1-------- 3 1 12 3 4 5 6 3 příklad: vytvoření rozvrhu za předpokladu, že učitelé učiv různých místnostech D in 1..2, C = 3, disjoint2( class(Jan,D,Ml,l), class(Petr,D,M2,1), class(Petr,D,M3,l), ...] ) Hana Rudová, Logické programování I, 17. dubna 2009 30 CLP(FD) v SICStus Prologu Kumulativní rozvrhování M cumulative(Starts,Durations,Resources,Limit) -• Úlohy jsou zadány startovním časem (seznam Starts), dobou trvání (seznam Durations) a požadovanou kapacitou zdroje (seznam Resources) -• Rozvržení úloh tak, aby celková kapacita zdroje nikdy nepřekročila Limit Hana Rudová, Logické programování I, 1 7. dubna 2009 31 CLP(FD) v SICStus Prologu Kumulativní rozvrhování M cumulative(Starts,Durations,Resources,Limit) -• Úlohy jsou zadány startovním časem (seznam Starts), dobou trvání (seznam Durations) a požadovanou kapacitou zdroje (seznam Resources) -• Rozvržení úloh tak, aby celková kapacita zdroje nikdy nepřekročila Limit -• Příklad s konstantami: cumulative([0,l ,3],[4,2,3],[1,2,2],3) 2 3 i. 12 3 4 5 6 Hana Rudová, Logické programování I, 17. dubna 2009 31 CLP(FD) v SICStus Prologu Příklad: kumulativní rozvrhování M 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 ti 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 X.7 4 11 Hana Rudová, Logické programování I, 17. dubna 2009 32 CLP(FD) v SICStus Prologu Příklad: kumulativní rozvrhování M Vytvořte rozvrh pro následující schedulers, End) :- úlohy, tak aby nebyla překročena kapacita 1 3 zdroje, a minimalizujte celkovou dobu trvání úloha doba trvání kapacita ti 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 X.7 4 11 Hana Rudová, Logické programování I, 17. dubna 2009 32 CLP(FD) v SICStus Prologu Příklad: kumulativní rozvrhování M 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 ti 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 X.7 4 11 Hana Rudová, Logické programování I, 17. dubna 2009 32 CLP(FD) v SICStus Prologu schedule(Ss, End) :-length(Ss, 7), Příklad: kumulativní rozvrhování M 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 ti 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 X.7 4 11 Hana Rudová, Logické programování I, 17. dubna 2009 32 CLP(FD) v SICStus Prologu schedule(Ss, End) :-length(Ss, 7), Ds = [16, 6, 13, 7, 5, 18, 4], Rs = [ 2, 9, 3, 7, 10, 1, 11], 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 ti 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 X.7 4 11 schedule(Ss, End) :-length(Ss, 7), Ds = [16, 6, 13, 7, 5 Rs = [ 2, 9, 3, 7, 10 domain(Ss, 0, 51), domain([End], 0, 69), 18, 4], 1, 11], Hana Rudová, Logické programování I, 1 7. dubna 2009 32 CLP(FD) v SICStus Prologu 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 ti 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 X.7 4 11 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ý čas Hana Rudová, Logické programování I, 1 7. dubna 2009 32 CLP(FD) v SICStus Prologu 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 ti 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 X.7 4 11 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ý čas cumulative(Ss, Ds, Rs, 13), Hana Rudová, Logické programování I, 1 7. dubna 2009 32 CLP(FD) v SICStus Prologu 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 ti 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 X.7 4 11 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ý čas cumulative(Ss, Ds, Rs, 13), append(Ss, [End], Vars), labeling([mi ni mi ze(End)], Vars). Hana Rudová, Logické programování I, 1 7. dubna 2009 32 CLP(FD) v SICStus Prologu 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 ti t2 t3 t4 t5 t6 X.7 16 6 13 7 5 18 4 2 9 3 7 10 1 11 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ý čas cumulative(Ss, Ds, Rs, 13), append(Ss, [End], Vars), labeling([mi ni mi ze(End)], Vars). after([], [] , _) . after([S|Ss], [D|Ds], E) :- E #>= S+D, after(Ss, Ds, E). ti X2 t3 t4 t5 t6 X7 16 6 13 7 5 18 4 2 9 3 7 10 1 11 Hana Rudová, Logické programování I, 1 7. dubna 2009 32 CLP(FD) v SICStus Prologu 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 ti 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 X.7 4 11 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ý čas cumulative(Ss, Ds, Rs, 13), append(Ss, [End], Vars), labeling([mi ni mi ze(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 ? Hana Rudová, Logické programování I, 1 7. dubna 2009 32 CLP(FD) v SICStus Prologu