CP: elektronické materiály Logické programování s omezujícími podmínkami Constraint Logic Programming: CLP Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003. ■ 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. ■ http://kti.ms.mff.cuni.cz/~bartak/podminky/index.html SICStus Prolog User's Manual. Kapitola o CLP(FD). ■ http://www.fi.muni.cz/~hanka/sicstus/doc/html/ Příklady v distribuci SICStus Prologu: cca 60 příkladů, zdrojový kód ■ 1 i b/sicstus-'-'-'/l i brary/cl pfd/examples/ Probírané oblasti ■ Obsah ■ úvod: od LP k CLP ■ základy programování ■ základní algoritmy pro řešení problémů s omezujícími podmínkami ■ Příbuzné přednášky na Fl ■ PA163 Programování s omezujícími podmínkami ■ viz interaktivní osnova IS ■ PA1 67 Rozvrhování ■ http://www.fi.muni.cz/~hanka/rozvrhováni ■ zahrnuty CP techniky pro řešení rozvrhovacích problémů Hana Rudová, Logické programování I, 1 5. dubna 201 3 3 Logické programování s omezujícími podmínkami Hana Rudová, Logické programování 1,15. dubna 201 3 2 Logické programování s omezujícími podmínkami Omezení (constraint) ■ Dána ■ množina (doménových) proměnných Y = {y\,..., yt] ■ konečná množina hodnot (doména) D = {D\,... ,DjJ Omezení c na ľ je podmnožina DiX...xflt ■ omezuje hodnoty, kterých mohou proměnné nabývat současně ■ Příklad: ■ proměnné: A,B ■domény: {0,1} pro A {1,2} pro B ■omezení: A^B nebo (A,B) e {(0,1 ),(0,2),(1,2)} ■ Omezení c definováno na y\,.. .yt je splněno, pokud pro di e D\, ...dt^Dt platí (d\,... dt) e c ■ 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í 1,15. dubna 201 3 4 Logické programování s omezujícími podmínkami Problém splňování podmínek (CSP) Řešení CSP Dána ■ konečná množina proměnných X = {x\, ...,xn} ■ konečná množina hodnot (doména) D = {Di,... ,Dn} ■ konečná množina omezení C = {c\,..., cm} ■ omezení je definováno na podmnožině X Problém splňování podmínek je trojice (X,D, C) (constraint satisfaction problem) Příklad: ■ 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 5. dubna 201 3 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í: a"l"l_distinct([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 ř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 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 5. dubna 2013 Logické programování s omezujícími podmínkami Částečné ohodnocení proměnných (d\,dk),k < n ■ některé proměnné mají přiřazenu hodnotu Úplné ohodnocení proměnných (d\,dn) ■ všechny proměnné mají přiřazenu hodnotu Řešení CSP ■ úplné ohodnocení proměnných, které splňuje všechna omezení ■ (di,..., dn) e Di x ... x Dn je řešení (X,D, C) ■ pro každé Cí e c na x^,.. .Xík platí (tií1,.. .dík) e Cí Hledáme: jedno nebo všechna řešení nebo optimální řešení (vzhledem k objektivní funkci) Hana Rudová, Logické programování 1,15. dubna 201 3 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í řešení (1) a (2) deklarativní část ■ modelování problému ■ vyjádření problému splňování podmínek (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í 1,15. dubna 201 3 Logické programování s omezujícími podmínkami Kód CLPCFD) programu Příklad: algebrogram % základní struktura CLP programu sol ve( Variables ) :- declare_variables( Variables ), domain ([Jan] ,3,6], ... post_constraints( Variables ), a]]_distinct([]an,Petr,...]) labelingC Variables ). % triviální labeling labelingC [] ). labelingC [Var|Rest] ) :- fd_min(Var,Min) , % výběr nejmenší hodnoty z domény ( Var#=Min, labeling( Rest ) i Var#>Min , labeling( [Var|Rest] ) Hana Rudová, Logické programování I, 1 5. dubna 201 3 9 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(jzi) generický jazyk ■ CLP(FD) domény proměnných jsou konečné (Finite Domains) ■ CLP(K) doménou proměnných je množina reálných čísel ■ Cíl ■ využít syntaktické a výrazové přednosti LP ■ dosáhnout větší efektivity ■ Unifikace v LP je nahrazena splňováním podmínek ■ unifikace se chápe jako jedna z podmínek ■ A = B ■ A #< B, A in 0..9, domain([A, B] ,0,9), a]]_distinct([A, B,C]) Hana Rudová, Logické programování I, 1 5. dubna 201 3 11 Logické programování s omezujícími podmínkami ■ 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í přiřazena různé cifry ■ S a M nejsou 0 ■ 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] ) ■ labeling( [S,E,N,D,M,0,R,Y] ) Hana Rudová, Logické programování 1,15. dubna 201 3 1 0 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) ■ 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 ■ Prohledávání doplněno konzistenčními technikami ■A in 1..2, B in 0..1, B# #= | #\= | #< | #=< | #> | #>= ■ A + B #=< 3, A #\= (C - 4) * C 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), sumC[A,B,C],#= ,F) ■ Vari abl es i Suma musí být doménové proměnné nebo celá čísla scalar_product(Coeffs,Variables,RelOp,ScalarProduct) ■ domain([A,B,C,F],1,6), scalar_product( [1,2,3],[A,B,C],#= ,F) ■ Variables i Val ue musí být doménové proměnné nebo celá čísla, Coeff s jsou celá čísla ■ POZOR na pořadí argumentu, nejprve jsou celočíselné koeficienty, pak dom. proměnné ■ scalar_product(Coeffs, Variables, #= , Value, [consistency(domain)]) ■ silnější typ konzistence ■ POZOR: domény musí mít konečné hranice Hana Rudová, Logické programování I, 1 5. dubna 201 3 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é all_distinct a all_different se liší úrovní propagace ■ all_distinct má úplnou propagaci ■ all_different má slabší (neúplnou) propagaci Příklad: učitelé musí učit v různé hodiny ■ all_di sti nct C [Jan , Petr, Anna, Ota, Eva, Marie]) Jan = 6, Ota = 2, Anna = 5, Marie = 1, Petr in 3..4, Eva in 3..4 ■ 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 učitel min max Jan 3 6 Petr 3 4 Anna 2 5 Ota 2 4 Eva 3 4 Marie 1 6 Základní globální omezení all_distinct(List) ■ všechny proměnné různé cumulative(...) ■ disjunktivní a kumulativní rozvrhování cumulatives(...) ■ kumulativní rozvrhování na více zdrojů Hana Rudová, Logické programování 1,15. dubna 201 3 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 časem (Start, End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nepřekrývaly ■ příklad s konstantami: cumulative([task(0,2,2,l ,1), task(3,l ,4,1,2), task(5,l ,6,1,3)]) 3 1 2 3 4 5 6 příklad: vytvoření rozvrhu, za předpokladu, že doba trvání hodin není stejná JanE#= Jan+3, PetrE#= Petr+1, AnnaE#= Anna+2, ... cumulative(task(Jan,3,JanE,l,l),task(Petr,1,PetrE,1,2),task(Anna,2,AnnaE,1, task(Ota,2,OtaE,l,4),task(Eva,2,EvaE,l,5),task(Marie,3,MarieE,1,6)]) Hana Rudová, Logické programování I, 15. dubna 2013 23 CLP(FD) v SICStus Prologu Hana Rudová, Logické programování 1,15. dubna 2013 24 CLP(FD) v SICStus Prologu Kumulativní rozvrhování Kumulativní rozvrhování s více zdroji cumulative([task(Start,Duration,End,Demand,Taskld) | Tasks], [li mi t (Li mi t)]) 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,l,4)],[Ti mi t(3)]) 3 t-1-r 1 2 3 4 5 6 Hana Rudová, Logické programování I, 1 5. dubna 201 3 25 CLP(fD) v SICStus Prologu 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)) cumulatives([task(Start,Durati on,End,Demand,Machi neld)|Tasks], [machi ne(Id,Li mi t)|Machi nes],[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 (Machi neld) Zdroje zadány identifikátorem (Id) a kapacitou (Limit) Příklad: ?- domain([B,C],1,2), cumulatives([task(0,4,4,l,l),task(3,1,4,1,B), task(5,1,6,1,C)] [machi ne(l,1),machi ne(2,1)], [bound(upper)]). C in 1..2, B=2 Hana Rudová, Logické programování 1,15. dubna 201 3 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 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, 15. dubna 2013 27 CLP(fD) v SICStus Prologu Řešení: kumulativní rozvrhování | ?- schedu]e(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(l_imit, Ds, Rs, MaxCas, Ss, End) :-domainCSs, 0, MaxCas), End in 0..MaxCas, vytvor_u]ohy(Ss,Ds,Rs,1,Tasks), cumulative(Tasks, []i mi t(Limit)]), afterCSs, Ds , End), % koncový čas appendCSs, [End], Vars), ]abe]ing([minimize(End)],Vars). vytvor_ulohy([] ,[],[] ,_Id, []) . vytvor_ulohy([S|Ss], [D|Ds], [R|Rs], Id, [task(S,D,E,R,Id)|Tasks]):-Newld i s Id+1, E #= S+D, vytvor_u]ohy(Ss,Ds,Rs, Newld,Tasks). after([], [] , _) . after([S|Ss], [D|Ds], End) :- E #>= S+D, afterCSs, Ds, End). Hana Rudová, Logické programování 1,15. dubna 201 3 28 CLP(fD) v SICStus Prologu