CP: elektronické materiály Logické programování s omezujícími podmínkami Constraint Logic Programming: CLP 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, 26. dubna 2011 3 Logické programování s omezujícími podmínkami ■ 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/ Hana Rudová, Logické programování I, 26. dubna 201 1 2 Logické programování s omezujícími podmínkami Historie a současnost ■ 1963 interaktivní grafika (Sutherland: Sketchpad) ■ Polovina 80. let: logické programování omezujícími podmínkami ■ 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, ...) ■ minimalizace změny v rozvrhu, minimalizace ceny ■ Nokia: automatická konfigurace sw pro mobilní telefony ■ Renault: krátkodobé plánování výroby, funkční od roku 1995 Hana Rudová, Logické programování I, 26. dubna 201 1 4 Logické programování s omezujícími podmínkami ,Vfc} Dk} Omezení (constraint) Dána ■ množina (doménových) proměnných Y = {yi ■ konečná množina hodnot (doména) D = {Di,. Omezení c na Y je podmnožina D\ x ... x Dk ■ 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 d\ e D\,.. .dk e Dk platí (tři, ■ ■ ■ dk) 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í I, 26. dubna 201 1 Logické programování s omezujícími podmínkami Řešení CSP Čá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í ■ (tři, ■ ■ ■, d„) e Di x ... x Dn je řešení (X, D, C) ■ pro každé cf e C na X{v .. platí (d\l,.. .dik) e cf Hledáme: jedno nebo všechna řešení nebo optimální řešení (vzhledem k objektivní funkci) Hana Rudová, Logické programování I, 26. dubna 2011 Logické programování s omezujícími podmínkami Problém splňování podmínek (CSP) Dána ■ konečná množina proměnných X = {xi,...,x„} ■ konečná množina hodnot (doména) D = {D\,...,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, 26. dubna 201 1 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 1_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 řešení CSP: 3an=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, 26. dubna 201 1 Logické programování s omezujícími podmínkami CLPCFD) program Kód CLPCFD) programu 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í I, 26. dubna 201 I 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: ■ 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_distinctC [S,E,N,D,M,0,R,Y] ) labelingC [5,E,N,D,M,0,R,Y] ) Hana Rudová, Logické programovaní I, 26. dubna 2011 11 Logické programováni s omezujícími podmínkami % základní struktura CLP programu solveC Variables ) :- declare_variablesC Variables ), domainCpan] ,3,6], ... post_constraints( Variables ), an_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 ) i Var#>Min , labelingC [Var|Rest] ) Hana Rudova, Logické programování I, 26. dubna 201 1 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(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"l"l_di sti net ([A, B, C]) Hana Rudová, Logické programování I, 26. dubna 201 1 1 2 Logické programováni s omezujícími podmínkami Od LP k CLP II. Syntaxe CLP ■ 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# Vyvolání dvou řešičů: unifikace + řešič omezení Hana Rudová, Logické programování I, 26. dubna 201 1 14 Logické programování s omezujícími podmínkami Operační sémantika CLP CLP výpočet cíle G ■ Store množina aktivních omezení = prostor omezení (constraint store) ■ inicializace Store = 0 ■ 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} ■ snažíme se splnit c vyvoláním jeho řešiče ■ při neúspěchu se vyvolá backtracking ■ při úspěchu se podmínky v NewStore zjednoduší propagací omezení ■ zbývající cíle jsou prováděny s upraveným NewStore CLP(FD) v SICStus Prologu CLP výpočet cíle G je úspěšný, pokud se dostaneme z iniciálního stavu (G, 0} do stavu #= | #\= | #< | #=< | #> | #>= ■ 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), sum([A,B,C],#= ,F) ■ Variables i Suma musí být doménové proměnné nebo celá čísla ■ scalar_product(Coeffs,Variables,RelOp,Seal arProduct) ■ 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í argumentů, 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, 26. dubna 201 1 22 CLP(f D) v SICStus Prologu Základní globální omezení Všechny proměnné různé all_distinct(List) ■ všechny proměnné různé cumulative(...) ■ disjunktivní a kumulativní rozvrhování cumulati ves(...) ■ kumulativní rozvrhování na více zdrojů all_distinet(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_distinct([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 Hana Rudová, Logické programování I, 26. dubna 201 1 23 CLP(FD) v SICStus Prologu Hana Rudová, Logické programování I, 26. dubna 201 1 24 CLP(FD) v SICStus Prologu Disjunktivní rozvrhování (unární zdroj) Kumulativní rozvrhování 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+l, PetrE#= Petr+1, AnnaE#= Anna+2, cumulative(task(]an,1,JanE,1,1),task(Petr,l,PetrE,1,2),task(Anna,1,AnnaE,1, task(Ota, 2 , OtaE ,1,4), task(Eva, 2 , EvaE ,1,5), task(Mari e, 3 , Man' eE, 1,6) ]) Hana Rudová, Logické programování I, 26. dubna 2011 CLP(fD)vSICStus Prologu cumulative([task(Start,Duration,End,Demand,TaskId) | 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)],[limit(3)]) 3 Hana Rudová, Logické programování I, 26. dubna 201 1 CLP(fD>vSICStus Prologu Kumulativní rozvrhování s více zdroji Rozvržení úloh tak, aby se nepřekrývaly a daná kapacita zdrojů nebyla překročena (limit zdroje chápán jako horní mez - bound (upper)) cumulatives([tas k(Start,Duration,End,Demand,Machi neld)|Tasks], [machi ne(Id,Limit)|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,l,6,l,C)] [machine(l,l),machine(2,1)], [bound(upper)]). C in 1..2, B=2 Hana Rudová, Logické programování I, 26. dubna 2011 27 CLP(fD) v SICStus Prologu