Logické programování s omezujícími podmínkami Constraint Logic Programming: CLP CP: elektronické materiály M Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003. M http://www.ics.uci.edu/~dechter/books/materials.html průsvitky ke knize Barták R. Přednáška Omezující podmínky na MFF UK, Praha. M http://kti.ms.mff.cuni.cz/~bartak/podminky/index.html SICStus Prolog User's Manual. Kapitola o CLP(FD). M http://www.fi.muni.cz/~hanka/sicstus/doc/html/ M Příklady v distribuci SICStus Prologu: cca 60 příkladů, zdrojový kód 3 1 i b/si cstus-*/li brary/clpfd/examples/ Hana Rudová, Logické programování I, 1 9. dubna 201 2 2 Logické programování s omezujícími podmínkami Probírané oblasti Obsah M úvod: od LP k CLP S základy programování základní algoritmy pro řešení problémů s omezujícími podmínkami Hana Rudová, Logické programování I, 1 9. dubna 201 2 3 Logické programování s omezujícími podmínkami Probírané oblasti M Obsah 3 úvod: od LP k CLP * základy programování «• základní algoritmy pro řešení problémů s omezujícími podmínkami M Příbuzné přednášky na Fl 3 PA163 Programování s omezujícími podmínkami £> viz interaktivní osnova IS 3 PA1 67 Rozvrhování & http://www.fi.muni.cz/~hanka/rozvrhováni X zahrnuty CP techniky pro řešení rozvrhovacích problémů Hana Rudová, Logické programování I, 1 9. dubna 201 2 3 Logické programování s omezujícími podmínkami Omezení (constraint) M Dána 3 množina (doménových) proměnných Y = {yi,... ,3^} M konečná množina hodnot (doména) D = {Di,... ,Dk) 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 9. dubna 201 2 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,...,yk} M 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: M proměnné: A,B M domény: {0,1} pro A {1,2} pro B .•omezení: A^B nebo (A,B) e {(0,1 ),(0,2),(1,2)} Hana Rudová, Logické programování I, 1 9. dubna 201 2 4 Logické programování s omezujícími podmínkami Omezení (constraint) M Dána 3 množina (doménových) proměnných Y = {yľ,... 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ě 3 Příklad: M proměnné: A,B domény: {0,1} pro A {1,2} pro B .•omezení: A^B nebo (A,B) g {(0,1 ),(0,2),(1,2)} M Omezení c definováno na yi,... 3^ je splněno, pokud pro di e Di, ...dk e Dk platí (di,...dk) e c 3 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 9. dubna 201 2 4 Logické programování s omezujícími podmínkami Problém splňování podmínek (CSP) M Dána M konečná množina proměnných X = {x\,..., xn} M konečná množina hodnot (doména) D = {D\,... ,Dn} M 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 9. dubna 201 2 5 Logické programování s omezujícími podmínkami Problém splňování podmínek (CSP) M Dána M konečná množina proměnných X = {x\,..., xn} M konečná množina hodnot (doména) D = {D\,... ,Dn} M 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: 3 proměnné: A,B,C -•domény: {0,1} pro A {1,2} pro B {0,2} pro C omezení: A^B, B^C Hana Rudová, Logické programování I, 1 9. dubna 201 2 5 Logické programování s omezujícími podmínkami Řešení CSP M Částečné ohodnocení proměnných (d\,..., dk), k < n M některé proměnné mají přiřazenu hodnotu M Úplné ohodnocení proměnných (di,dn) M všechny proměnné mají přiřazenu hodnotu Hana Rudová, Logické programování I, 1 9. dubna 201 2 6 Logické programování s omezujícími podmínkami Řešení CSP Částečné ohodnocení proměnných (di,..., dk),k < n M některé proměnné mají přiřazenu hodnotu Úplné ohodnocení proměnných (di,..., dn) M všechny proměnné mají přiřazenu hodnotu 3 Řešení CSP 3 úplné ohodnocení proměnných, které splňuje všechna omezení M (di,...,dn) g Di x ... x Dn je řešení (X,D,C) 3 pro každé a e C na x^,.. .xtk platí (d^,... dik) e a Hana Rudová, Logické programování I, 1 9. dubna 201 2 6 Logické programování s omezujícími podmínkami Řešení CSP Částečné ohodnocení proměnných (di,..., dk),k < n * některé proměnné mají přiřazenu hodnotu Úplné ohodnocení proměnných (di,..., dn) * všechny proměnné mají přiřazenu hodnotu 3 Řešení CSP 3 úplné ohodnocení proměnných, které splňuje všechna omezení * (di,...,dn) g Di x ... x Dn je řešení (X,D,C) 3 pro každé a e C na x^,.. .xtk platí (d^,... dtk) g a M Hledáme: jedno nebo všechna řešení nebo optimální řešení (vzhledem k objektivní funkci) Hana Rudová, Logické programování I, 1 9. dubna 201 2 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 nct( [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, 1 9. dubna 201 2 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í: al l_di sti nct( [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 9. dubna 201 2 7 Logické programování s omezujícími podmínkami Příklad: jednoduchý školní rozvrh M proměnné: Jan, Petr, ... domény: {3,4, 5,6}, {3,4},... M omezení: al l_di sti nct( [Jan, Petr, . . . ]) částečné ohodnocení: Jan=6, Anna=5, Marie=l -9 úplné ohodnocení: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=6 ř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 Hana Rudová, Logické programování I, 1 9. dubna 201 2 7 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 Příklad: jednoduchý školní rozvrh M proměnné: Jan, Petr, ... domény: {3,4, 5,6}, {3,4},... M omezení: al l_di sti nct( [Jan, Petr, . . . ]) částečné ohodnocení: Jan=6, Anna=5, Marie=l -9 úplné ohodnocení: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=6 ř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 M optimalizace: ženy učí co nejdříve Hana Rudová, Logické programování I, 1 9. dubna 201 2 7 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 Příklad: jednoduchý školní rozvrh proměnné: Jan, Petr, ... domény: {3,4, 5,6}, {3,4},... omezení: al l_di sti nct( [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 M řešení CSP: Jan=6, Petr=3, Anna=5, 0ta=2, Eva=4, Marie=l M všechna řešení: ještě Jan=6, Petr=4, Anna=5, 0ta=2, Eva=3, Marie=l M 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 9. dubna 201 2 7 Logické programování s omezujícími podmínkami CLP(FD) program M 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 9. dubna 201 2 8 Logické programování s omezujícími podmínkami CLP(FD) program M Základní struktura CLP programu 1. definice proměnných a jejich domén 2. definice omezení 3. hledání řešení M (1) a (2) deklarativní část 3 modelování problému * vyjádření problému splňování podmínek Hana Rudová, Logické programování I, 1 9. dubna 201 2 8 Logické programování s omezujícími podmínkami CLP(FD) program M Základní struktura CLP programu 1. definice proměnných a jejich domén 2. definice omezení 3. hledání řešení M (1) a (2) deklarativní část 3 modelování problému vyjádření problému splňování podmínek M (3) řídící část prohledávání stavového prostoru řešení «• procedura pro hledání řešení (enumeraci) se nazývá labeling umožní nalézt jedno, všechna nebo optimální řešení Hana Rudová, Logické programování I, 1 9. dubna 201 2 8 Logické programování s omezujícími podmínkami Kód CLP(FD) programu % základní struktura CLP programu solve( Variables ) :- deci are_vari ables( Variables ), domain ([Jan] ,3,6], Hana Rudová, Logické programování I, 1 9. dubna 201 2 9 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,...]) Hana Rudová, Logické programování I, 1 9. dubna 201 2 9 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 ). Hana Rudová, Logické programování I, 1 9. dubna 201 2 9 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_ch'stinct([Jan,Petr,...]) 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 ) Hana Rudová, Logické programování I, 1 9. dubna 201 2 9 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,...]) 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] ) ). Hana Rudová, Logické programování I, 1 9. dubna 201 2 9 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: 3 SEND + MORE = MONEY 3 různá písmena mají přiřazena různé cifry M S a M nejsou 0 Hana Rudová, Logické programování I, 1 9. dubna 201 2 10 Logické programování s omezujícími podmínkami Příklad: algebrogram M Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: * SEND + MORE = MONEY M různá písmena mají přiřazena různé cifry J SaM nejsou 0 M domain([E,N,D,0,R,Y], 0, 9), domain([S,M],1,9) Hana Rudová, Logické programování I, 1 9. dubna 201 2 10 Logické programování s omezujícími podmínkami Příklad: algebrogram M Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: * SEND + MORE = MONEY M různá písmena mají přiřazena různé cifry J SaM nejsou 0 M domain([E,N,D,0,R,Y], 0, 9), domain([S,M],1,9) 3 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 9. dubna 201 2 10 Logické programování s omezujícími podmínkami Příklad: algebrogram M Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: * SEND + MORE = MONEY M různá písmena mají přiřazena různé cifry J SaM nejsou 0 M domain([E,N,D,0,R,Y], 0, 9), domain([S,M],1,9) 3 1000*S + 100*E + 10*N + D + 1000*M + 100*0 + 10*R + E #= 10000*M + 1000*0 + 100*N + 10*E + Y M all_distinct( [S,E,N,D,M,0,R,Y] ) Hana Rudová, Logické programování I, 1 9. dubna 201 2 10 Logické programování s omezujícími podmínkami Příklad: algebrogram M Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: * SEND + MORE = MONEY M různá písmena mají přiřazena různé cifry J SaM nejsou 0 M domain([E,N,D,0,R,Y], 0, 9), domain([S,M],1,9) 3 1000*S + 100*E + 10*N + D + 1000*M + 100*0 + 10*R + E #= 10000*M + 1000*0 + 100*N + 10*E + Y M all_distinct( [S,E,N,D,M,0,R,Y] ) M labelingC [S,E,N,D,M,0,R,Y] ) Hana Rudová, Logické programování I, 1 9. dubna 201 2 10 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 CLP(jzl) 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 9. dubna 201 2 Logické programování s omezujícími podmínkami Od LP k CLP I M CLP: rozšíření logického programování o omezující podmínky M CLP systémy se liší podle typu domény 3 CLP(jzl) generický jazyk M CLP(fd) domény proměnných jsou konečné (Finite Domains) M CLP(r) doménou proměnných je množina reálných čísel M Cíl M využít syntaktické a výrazové přednosti LP M dosáhnout větší efektivity Hana Rudová, Logické programování I, 1 9. dubna 201 2 Logické programování s omezujícími podmínkami Od LP k CLP I M CLP: rozšíření logického programování o omezující podmínky M CLP systémy se liší podle typu domény 3 CLP(jzl) generický jazyk M CLP(fd) domény proměnných jsou konečné (Finite Domains) M CLP(r) doménou proměnných je množina reálných čísel M Cíl M využít syntaktické a výrazové přednosti LP M dosáhnout větší efektivity -0 Unifikace v LP je nahrazena splňováním podmínek M unifikace se chápe jako jedna z podmínek 3 A = B M A #< B, A in 0..9, domai n( [A, B] ,0,9), al l_di s ti nct( [A, B, C]) Hana Rudová, Logické programování I, 1 9. dubna 201 2 11 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 9. dubna 201 2 12 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 3 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 9. dubna 201 2 12 Logické programování s omezujícími podmínkami Od LP k CLP II M 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 Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky Hana Rudová, Logické programování I, 1 9. dubna 201 2 12 Logické programování s omezujícími podmínkami Od LP k CLP II M 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 Podmínky jsou deterministicky vyhodnoceny v okamžiku volání podmínky M Prohledávání doplněno konzistenčními technikami J A in 1..2, BinO.,1, B# Vyvolání dvou řešičů: unifikace + řešič omezení Hana Rudová, Logické programování I, 1 9. dubna 201 2 Logické programování s omezujícími podmínkami Operační sémantika CLP M CLP výpočet cíle G * Store množina aktivních omezení = prostor omezení (constraint store) M inicializace Store = 0 M 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} 3 snažíme se splnit c vyvoláním jeho řešiče ± při neúspěchu se vyvolá backtracking s> při úspěchu se podmínky v NewStore zjednoduší propagací omezení M 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 (Gf, Store), kde G' je prázdný cíl a Store je splnitelná. Hana Rudová, Logické programování I, 1 9. dubna 201 2 14 Logické programování s omezujícími podmínkami CLP(FD) v SICStus Prologu Systémy a jazyky pro CP IBM ILOG CP 1987 M omezující podmínky v C++, Jave nebo generickém modelovacím jazyku OPL M implementace podmínek založena na objektově orientovaném programování M špičkový komerční sw, vznikl ve Francii, nedávno zakoupen IBM M nyní nově volně dostupný pro akademické použití Hana Rudová, Logické programování I, 1 9. dubna 201 2 16 CLP(FD) vSICStus Prologu Systémy a jazyky pro CP M IBM ILOG CP 1987 3 omezující podmínky v C++, Jave nebo generickém modelovacím jazyku OPL 3 implementace podmínek založena na objektově orientovaném programování 3 špičkový komerční sw, vznikl ve Francii, nedávno zakoupen IBM M nyní nově volně dostupný pro akademické použití Swedish Institute of Computer Science: SICStus Prolog 1 985 3 silná CLP(fd) knihovna, komerční i akademické použití Hana Rudová, Logické programování I, 1 9. dubna 201 2 16 CLP(FD) v SICStus Prologu Systémy a jazyky pro CP M IBM ILOG CP 1987 3 omezující podmínky v C++, Jave nebo generickém modelovacím jazyku OPL 3 implementace podmínek založena na objektově orientovaném programování 3 špičkový komerční sw, vznikl ve Francii, nedávno zakoupen IBM 3 nyní nově volně dostupný pro akademické použití Swedish Institute of Computer Science: SICStus Prolog 1 985 3 silná CLP(fd) knihovna, komerční i akademické použití M IC-PARC, Imperiál College London, Cisco Systems: ECL'PS6 1 984 3 široké možnosti kooperace mezi různými řešičemi: konečné domény, reálná čísla, repai r 3 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 9. dubna 201 2 16 CLP(FD) v SICStus Prologu Systémy a jazyky pro CP M IBM ILOG CP 1987 3 omezující podmínky v C++, Jave nebo generickém modelovacím jazyku OPL 3 implementace podmínek založena na objektově orientovaném programování 3 špičkový komerční sw, vznikl ve Francii, nedávno zakoupen IBM M nyní nově volně dostupný pro akademické použití Swedish Institute of Computer Science: SICStus Prolog 1 985 3 silná CLP(fd) knihovna, komerční i akademické použití M IC-PARC, Imperiál College London, Cisco Systems: ECL'PS6 1 984 3 široké možnosti kooperace mezi různými řešičemi: konečné domény, reálná čísla, repai r 3 od 2004 vlastní Cisco Systems volně dostupné pro akademické použití, rozvoj na IC-PARC, platformy: Windows, Linux, Solaris Mnoho dalších systémů: Choco, Gecode, Minion, Oz, SWI Prolog, ... Hana Rudová, Logické programování I, 19. dubna 2012 16 CLP(FD) v SICStus Prologu CLP(FD) v SICStus Prologu M Vestavěné predikáty jsou dostupné v separátním modulu (knihovně) :- use_module(library(clpfd)). Obecné principy platné všude nicméně standarty jsou nedostatečné M stejné/podobné vestavěné predikáty existují i jinde CLP knihovny v SWI Prologu i ECLiPSe se liší Hana Rudová, Logické programování I, 1 9. dubna 201 2 CLP(FD) v SICStus Prologu Příslušnost k doméně: Range termy ?- domain( [A, B], 1,3). domain( +Variables, +Min, +Max) A in 1. . 3 B in 1. .3 Rudová, Logické programování I, 1 9. dubna 201 2 18 CLP(FD) v SICStus Prologu Příslušnost k doméně: Range termy M ?- domain( [A,B], 1,3). A in 1..3 B in 1. . 3 M ?- A in 1..8, A #\= 4. A in (1..3) \/ (5..8) Hana Rudová, Logické programování I, 1 9. dubna 201 2 1 8 domain( +Variables, +Min, +Max) ?X in +Min..+Max CLP(FD) vSICStus Prologu Příslušnost k doméně: Range termy M ?- domain( [A, B], 1,3). domain( +Variables, +Min, +Max) A in 1. . 3 B in 1..3 J ?- A in 1..8, A#\= 4. ?X in +Min. .+Max A in (1..3) \/ (5..8) M 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 9. dubna 201 2 18 CLP(FD) vSICStus Prologu Příslušnost k doméně: Range termy M ?- domain( [A,B], 1,3). domain( +Variables, +Min, +Max) A in 1. . 3 B in 1..3 J ?- A in 1..8, A#\= 4. ?X in +Min. .+Max A in (1..3) \/ (5..8) M 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) Hana Rudová, Logické programování I, 1 9. dubna 201 2 18 CLP(FD) vSICStus Prologu Příslušnost k doméně: Range termy M ?- domain( [A, B], 1,3). domain( +Variables, +Min, +Max) A in 1. . 3 B in 1..3 J ?- A in 1..8, A#\= 4. ?X in +Min. .+Max A in (1..3) \/ (5..8) M 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) M A in 1..8, A #\= 4, fd_dom(A,Range). Range=(1..3) \/ (5..8) 3 A in 2..10, fd_dom(A,(1..3) \/ (5..8)). no Hana Rudová, Logické programování I, 1 9. dubna 201 2 18 CLP(FD) vSICStus Prologu Příslušnost k : Range termy ?- domainC [A,B], 1,3) A in 1. . 3 B in 1..3 domain( +Variables, +Min, +Max) ?- A in 1..8, A #\= 4. A in (1..3) \/ (5..8) ?X in +Min..+Max Doména reprezentována jako posloupnost intervalů celých čísel ?- A in (1..3) \/ (8..15) \/ (5..9) \/ {100}. A in (1..3) \/ (5..15) \/ {100} Zjištění domény Range proměnné Var: 3 A in 1..8, A #\= 4, fd_dom(A,Range). M A in 2..10, fd_dom(A,(1..3) \/ (5..8)). ?X in +Range fd_dom(?Var,?Range) Range=(l..3) \/ (5..8) no Range term: reprezentace nezávislá na implementaci Hana Rudová, Logické programování I, 1 9. dubna 201 2 18 CLP(FD) vSICStus Prologu Příslušnost k doméně: FDSet termy FDSet term: reprezentace závislá na implementaci ?- A in 1..8, A #\= 4, fd_set(A, FDSet) . f d_set (?Var, ?FDSet) A in (1..3) \/ (5..8) FDSet = [[1|3],[5|8]] Hana Rudová, Logické programování I, 1 9. dubna 201 2 19 CLP(FD) vSICStus 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) . f cLset (?Var, ?FDSet) A in (1..3) \/ (5..8) FDSet = [[1|3],[5|8]] ?- 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 = [[1|3],[5|8]] B in (1..3) \/ (5..8) Hana Rudová, Logické programování I, 1 9. dubna 201 2 19 CLP(FD) vSICStus Prologu Příslušnost k doméně: FDSet termy FDSet term: reprezentace závislá na implementaci 3 ?- A in 1..8, A #\= 4, fd_set(A, FDSet) . f cLset (?Var, ?FDSet) A in (1..3) \/ (5..8) FDSet = [[1|3],[5|8]] M ?- 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 = [[1|3],[5|8]] B in (1..3) \/ (5..8) M FDSet termy představují nízko-úrovňovou implementaci FDSet termy nedoporučeny v programech M používat pouze predikáty pro manipulaci s nimi M omezit použití A in_set [ [112], [61 9] ] Range termy preferovány Hana Rudová, Logické programování I, 19. dubna 2012 19 CLP(FD) v SICStus Prologu Další fd_. . . predikáty M fdset_to_list(+FDset, -List) vrací do seznamu prvky FDset 1 i st_to_fdset(+List, -FDset) vrací FDset odpovídající seznamu M fd_var(?Var) je Var doménová proměnná? fd_mi n(?Var, ?Mi n) nejmenší hodnota v doméně fd_max(?Var, ?Max) největší hodnota v doméně M fd_size(?Var,?Size) velikost domény M fd_degree(?Var,?Degree) počet navázaných omezení na proměnné M mění se během výpočtu: pouze aktivní omezení, i odvozená aktivní omezení Hana Rudová, Logické programování I, 1 9. dubna 201 2 20 CLP(FD) vSICStus Prologu Aritmetická omezení 3 Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>= 3 A + B #=< 3, A #\= (C - 4) * ( D - 5), A/2 #= 4 POZOR: neplést #=< a #>= s operátory pro implikaci: #<= #=> Hana Rudová, Logické programování I, 1 9. dubna 201 2 21 CLP(FD) vSICStus Prologu Aritmetická omezení 3 Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>= M A + B #=< 3, A #\= (C - 4) * ( D - 5), A/2 #= 4 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é proměnné nebo celá čísla Hana Rudová, Logické programování I, 1 9. dubna 201 2 21 CLP(FD) vSICStus Prologu Aritmetická omezení 3 Expr RelOp Expr RelOp -> #= | #\= | #< | #=< | #> | #>= M A + B #=< 3, A #\= (C - 4) * ( D - 5), A/2 #= 4 ^ 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) 3 Variables i Suma musí být doménové proměnné nebo celá čísla M scalar_product(Coeffs,Vari ables,RelOp,SealarProduct) M domain([A,B,C,F],1,6), scalar_product( [1,2,3],[A,B,C],#= ,F) M Variables i Value musí být doménové proměnné nebo celá čísla, Coef f s jsou celá čísla M POZOR na pořadí argumentů, nejprve jsou celočíselné koeficienty, pak dom. proměnné M scalar_product(Coeffs, Variables, #= , Value, [consistency(domain)]) S silnější typ konzistence S* POZOR: domény musí mít konečné hranice Hana Rudová, Logické programování I, 19. dubna 201 2 21 CLP(FD) v SICStus Prologu Základní globální omezení M all_distinct(List) M všechny proměnné různé M cumulative(...) M disjunktivní a kumulativní rozvrhování cumulatives(...) M kumulativní rozvrhování na více zdrojů Hana Rudová, Logické programování I, 1 9. dubna 201 2 22 CLP(FD) vSICStus Prologu Všechny proměnné různé M all_distinct(Variables), all_different(Variables) Proměnné v seznamu Van" abl es jsou různé M al l_di sti nct a al l_di fferent se liší úrovní propagace al l_di sti nct má úplnou propagaci «• al l_di f ferent má slabší (neúplnou) propagaci Hana Rudová, Logické programování I, 1 9. dubna 201 2 23 CLP(FD) vSICStus Prologu Všechny proměnné různé al l_di sti nct (Vari abl es), al l_di f f e rent (Vari abl es) Proměnné v seznamu Vari abl es jsou různé al l_di sti nct a al l_di f ferent se liší úrovní propagace al l_di sti nct má úplnou propagaci «• al l_di f ferent 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 9. dubna 201 2 23 CLP(FD) vSICStus Prologu Všechny proměnné různé al l_di sti nct (Vari abl es), al l_di f f e rent (Vari abl es) Proměnné v seznamu Vari abl es jsou různé al l_di sti nct a al l_di f ferent se liší úrovní propagace all_distinct má úplnou propagaci «• al l_di f ferent má slabší (neúplnou) propagaci Příklad: učitelé musí učit v různé hodiny 3 all_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, 1 9. dubna 201 2 23 CLP(FD) vSICStus Prologu Všechny proměnné různé M all_distinct(Variables), all_different(Variables) Proměnné v seznamu Van" abl es jsou různé M al l_di sti nct a al l_di fferent se liší úrovní propagace al l_di sti nct má úplnou propagaci «• al l_di fferent má slabší (neúplnou) propagaci M Příklad: učitelé musí učit v různé hodiny 3 all_distinct([Jan,Petr,Anna,Ota,Eva,Marie]) Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr in 3..4, Eva in 3..4 3 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, 19. dubna 201 2 23 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í (unární zdroj) cumulative([task(Start, Duration, End, 1, Id) | Tasks]) M Rozvržení úloh zadaných startovním a koncovým časem (Start, End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly Hana Rudová, Logické programování I, 1 9. dubna 201 2 24 CLP(FD) vSICStus Prologu Disjunktivní rozvrhování (unární zdroj) M cumulative([task(Start, Duration, End, 1, Id) | Tasks]) M Rozvržení úloh zadaných startovním a koncovým časem (Start, End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly M příklad s konstantami: cumulative([task(0,2,2,l ,1), task(3,l ,4,1,2), task(5,l ,6,1,3)]) 1 í 2 3 12 3 4 5 6 Hana Rudová, Logické programování I, 1 9. dubna 201 2 24 CLP(FD) vSICStus Prologu Disjunktivní rozvrhování (unární zdroj) M cumulative([task(Start, Duration, End, 1, Id) | Tasks]) M Rozvržení úloh zadaných startovním a koncovým časem (Start, End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly 3 příklad s konstantami: cumulative([task(0,2,2,l ,1), task(3,l ,4,1,2), task(5,l ,6,1,3)]) 1 í 2 3 12 3 4 5 6 3 příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná Hana Rudová, Logické programování I, 1 9. dubna 201 2 24 CLP(FD) vSICStus Prologu Disjunktivní rozvrhování (unární zdroj) M cumulative([task(Start, Duration, End, 1, Id) | Tasks]) M Rozvržení úloh zadaných startovním a koncovým časem (Start, End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly 3 příklad s konstantami: cumulative([task(0,2,2,l ,1), task(3,l ,4,1,2), task(5,l ,6,1,3)]) 1 í 2 3 12 3 4 5 6 3 příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná JanE#= Jan+3, PetrE#= Petr+l, AnnaE#= Anna+2, ... cumulative(task(Jan,3,JanE,1,1),task(Petr,1,PetrE,1,2),task(Anna,2,AnnaE,1, task(Ota,2,OtaE,1,4),task(Eva,2,EvaE,1,5),task(Mari e,3,Mari eE,1,6)]) Hana Rudová, Logické programování I, 1 9. dubna 201 2 24 CLP(FD) vSICStus Prologu Kumulativní rozvrhování M cumulative([task(Start,Duration,End,Demand,Taskld) | Tasks], [limit(Limit)]) Rozvržení úloh zadaných startovním a koncovým časem (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 nepřekročila Limit Hana Rudová, Logické programování I, 1 9. dubna 201 2 25 CLP(FD) vSICStus Prologu Kumulativní rozvrhování M cumulative([task(Start,Duration,End,Demand,Taskld) | Tasks], [limit(Limit)]) Rozvržení úloh zadaných startovním a koncovým časem (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 nepřekročila Limit Příklad s konstantami: cumulative([task(0,4,4,l,l),task(l,2,3,2,2),task(3,3,6,2,3),task(4,2,6,1,4)],[li mi t(3)]) 2 4 3 1 1 1 1 l Hana Rudová, Logické programování I, 19. dubna 201 2 25 ° ° u CLP(FD) v SICStus Prologu Kumulativní rozvrhování s více zdroji M 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)) M cumul atives([task(Start,Durati on,End,Demand,Machi neld)|Tasks], [machine(Id,Limit)IMachines],[bound(upper)]) M Úlohy zadány startovním a koncovým časem (Start, End), dobou trvání (nezáporné Du rati on), požadovanou kapacitou zdroje (Demand) a požadovaným typem zdroje (Machi neld) M Zdroje zadány identifikátorem (Id) a kapacitou (Limit) Hana Rudová, Logické programování I, 1 9. dubna 201 2 26 CLP(FD) vSICStus Prologu Kumulativní rozvrhování s více zdroji M 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)) M cumul atives([task(Start,Durati on,End,Demand,Machi neld)|Tasks], [machine(Id,Limit)IMachines],[bound(upper)]) M Úlohy zadány startovním a koncovým časem (Start, End), dobou trvání (nezáporné Du rati on), požadovanou kapacitou zdroje (Demand) a požadovaným typem zdroje (Machi neld) M Zdroje zadány identifikátorem (Id) a kapacitou (Limit) 3 Příklad: ?- domain([B,C],1,2), cumulatives([task(0,4,4,l,l),task(3,l,4,l,B), task(5,l,6,l,C)], [machine(1,1),machine(2,1)] , [bound(upper)]). C in 1..2, B=2 Hana Rudová, Logické programování I, 19. dubna 201 2 26 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 tl 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 t7 4 11 Hana Rudová, Logické programování I, 1 9. dubna 201 2 27 CLP(FD) vSICStus 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 tl 16 2 t2 6 9 t3 13 3 t4 7 7 t5 5 10 t6 18 1 t7 4 11 Hana Rudová, Logické programování I, 1 9. dubna 201 2 27 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování | ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? Hana Rudová, Logické programování I, 1 9. dubna 201 2 28 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování | ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedule(Limit, Ds, Rs, MaxCas, Ss, End) :- Hana Rudová, Logické programování I, 1 9. dubna 201 2 28 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování I ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedule(Limit, Ds, Rs, MaxCas, Ss, End) :-domain(Ss, 0, MaxCas), End in O..MaxCas, Hana Rudová, Logické programování I, 1 9. dubna 201 2 28 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování | ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedu]e(Limit, Ds, Rs, MaxCas, Ss, End) :-domain(Ss, 0, MaxCas), End in 0..MaxCas, vytvor_ulohy(Ss,Ds,Rs,l,Tasks), Hana Rudová, Logické programování I, 1 9. dubna 201 2 28 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování I ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedule(Limit, Ds, Rs, MaxCas, Ss, End) :-domain(Ss, 0, MaxCas), End in O..MaxCas, vytvor_ulohy(Ss,Ds,Rs,1,Tasks), cumulati ve (Tasks, [limit (Limit)]) , Hana Rudová, Logické programování I, 1 9. dubna 201 2 28 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování I ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedule(Limit, Ds, Rs, MaxCas, Ss, End) :-domain(Ss, 0, MaxCas), End in 0..MaxCas, vytvor_ulohy(Ss,Ds,Rs,1,Tasks), cumulative(Tasks, [li mi t(Li mi t)]), after(Ss, Ds, End), % koncový čas Hana Rudová, Logické programování I, 1 9. dubna 201 2 28 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování I ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedule(Limit, Ds, Rs, MaxCas, Ss, End) :-domain(Ss, 0, MaxCas), End in 0..MaxCas, vytvor_ulohy(Ss,Ds,Rs,1,Tasks), cumulative(Tasks, [li mi t(Li mi t)]), after(Ss, Ds, End), % koncový čas append(Ss, [End], Vars), Hana Rudová, Logické programování I, 1 9. dubna 201 2 28 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování | ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedule(Limit, Ds, Rs, MaxCas, Ss, End) :-domain(Ss, 0, MaxCas), End in 0..MaxCas, vytvor_ulohy(Ss,Ds,Rs,1,Tasks), cumulati ve (Tasks, [limit (Limit)]) , after(Ss, Ds, End), % koncový čas append(Ss, [End], Vars), labeling([mi ni mi ze(End)],Vars). Hana Rudová, Logické programování I, 1 9. dubna 201 2 28 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování | ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedule(Limit, Ds, Rs, MaxCas, Ss, End) :-domain(Ss, 0, MaxCas), End in 0..MaxCas, vytvor_ulohy(Ss,Ds,Rs,1,Tasks), cumulati ve (Tasks, [limit (Limit)]) , after(Ss, Ds, End), % koncový čas append(Ss, [End], Vars), labeling([mi ni mi ze(End)],Vars). vytvor_ulohy([],[],[],_Id,[]). vytvor_ulohy([S|Ss], [D|Ds], [R|Rs], Id, [task(S,D,E,R,Id)|Tasks]):-Newld is Id+1, E #= S+D, vytvor_ulohy(Ss,Ds,Rs, Newld,Tasks). Hana Rudová, Logické programování I, 1 9. dubna 201 2 28 CLP(FD) vSICStus Prologu Řešení: kumulativní rozvrhování I ?- schedule(13, [16,6,13,7,5,18,4], [2,9,3,7,10,1,11], 69, Ss, End). Ss = [0,16,9,9,4,4,0], End = 22 ? schedule(Limit, Ds, Rs, MaxCas, Ss, End) :-domain(Ss, 0, MaxCas), End in 0..MaxCas, vytvor_ulohy(Ss,Ds,Rs,1,Tasks), cumulative(Tasks, [li mi t(Li mi t)]), after(Ss, Ds, End), % koncový čas append(Ss, [End], Vars), labeling([mi ni mi ze(End)],Vars). vytvor_ulohy([],[],[],_Id,[]). vytvor_ulohy([S|Ss], [D|Ds], [R|Rs], Id, [task(S,D,E,R,Id)|Tasks]):-Newld is Id+1, E #= S+D, vytvor_ulohy(Ss,Ds,Rs, Newld,Tasks). after([], [] , _) ■ after([S|Ss], [D|Ds], End) :- E #>= S+D, after(Ss, Ds, End). Hana Rudová, Logické programování I, 19. dubna 201 2 28 CLP(FD) v SICStus Prologu