Logické programování s omezujícími podmínkami Jazykové prvky Nalezněte řešení pro algebrogram DONALD + CERALD = ROBERT ■ Struktura programu algebrogram( [D,0,N,A,L,C,E,R,B,T] ) :- domain(...), % domény proměnných all_distinct(...)■ ...#=..., % omezeni % prohledávám' stavového prostoru Tabe1ing(.. .) . Knihovna pro CLP(FD) Domény proměnných Omezení Aritmetické omezení :- use_module("library(clpfd)) . domainC Seznam, MinValue, MaxValue ) a"l"l_distí nct( Seznam ) A*B + C #= D Procedura pro prohledávání stavového prostoru Hana Rudová, Logické programování 1,15. května 2013 labe"ling([] .Seznam) Omezující podmínky 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 ■ Proměnné: S,E,N,D,M,0,R,Y ■ Domény: [1..9] pro S,M [0..9] pro E,N,D,0,R,Y ■ 1 omezení pro nerovnost: a"l"l_di stinct([S, E, N,D,M,0, R, Y]) ■ 1 omezení pro rovnosti: 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*0 + 10*R + E + MORE #= 10000*M + 1000*0 + 100*N + 10*E + Y MONEY Hana Rudová, Logické programování 1,15. května 2013 2 Omezující podmínky Algebrogram: řešení :- use_module("library(clpfd)) . donald(LD):- % domény LD=[D,0,N,A,L,C,E,R,B,T], domain(LD,0,9), domain([D,G,R],1,9), % omezeni a"l"l_distinct(LD) , 100000*D + 10000*0 + 1000*N + 100*A + 10*L + D + 100000*C + 10000*E + 1000*R + 100*A + 10*L + D #= 100000*R + 10000*0 + 1000*B + 100*E + 10*R + T, % prohledáváni stavového prostoru TabelingCC] , LD). Hana Rudová, Logické programování 1,15. května 201 3 Omezující podmínky 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)]) Start, Duration, End, Id musí být doménové proměnné s konečnými mezemi nebo celá čísla Hana Rudová, Logické programování 1,15. května 2013 Omezující podmínky Plánování Každý úkol má stanoven dobu trvání a nejdřívější čas, kdy může být zahájen. Nalezněte startovní čas každého úkolu tak, aby se jednotlivé úkoly nepřekrývaly. Úkolyjsou zadány následujícím způsobem: % ukol(Id,Doba,MinStart,MaxKonec) ukol(l,4,8,70). úkol (2,2, 7,60) . ukol(3 ,1,2 ,25) . ukol(4,6, 5 , 55) . ukol(5,4,l,45). ukol(6,2,4,35). ukol(7,8,2 ,25) . ukol(8, 5 ,0,20) . ukol(9,l,8,40). ukol(10,7,4,50). ukol(11,5,2,50). ukol(12,2,0,35) . ukol(13,3,30,60). ukol(14,5,15,70). ukol(15,4,10,40) . Kostra řešení: ukoly(Zacatky) :- domeny(Ukoly,Začátky,Tasks), cumulative(Tasks), labeling([],Začátky), tiskni(Úkoly,Začátky). domény(Ukoly,Začátky,Tasks) :- findal1(ukol(Id,Doba,MinStart.MaxKonec), ukol(Id,Doba,MinStart,MaxKonec), Úkoly), Hana Rudová, Logické programování 1,15. května 201 3 nastav_domeny(Ukoly,Začátky.Tasks). Omezující podmínky Plánování: výstup tiskni(Úkoly,Začátky) :- priprav(Ukoly,Začátky,Vstup), quicksort(Vstup,Vystup), nl, tiskni(Vystup). priprav([] , [] , []) . při prav([ukol(Id,Doba,Mi nStart.MaxKonec)|Úkoly], [Z|Začátky], [ukol(Id,Doba,MinStart,MaxKonec,Z)IVstup]) :-priprav(Ukoly,Začátky,Vstup). tiskni ([]) :- nl . tiskni([V|Vystup]) :- V=ukol(Id,Doba,MinStart,MaxKonec,Z), K i s Z+Doba, formatC ~d: \t~d..~d \t(~d: ~d..~d)\n', [Id,Z,K,Doba,MinStart,MaxKonec] ), ti skni(Vystup). Hana Rudová, Logické programování I, 1 5. května 2013 7 Omezující podmínky Plánování: výstup II quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|Tail], A1-Z2) :- split(X, Tail, Small, Big), quicksortl(Small, A1-[X|A2]), quicksortl(Big, A2-Z2). split(_X, [], [], []). split(X, [Y|T], [Y|Small], Big) :- greater(X,Y), !, split(X, T, Small, Big). split(X, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). greater(ukol(_,_,_,_,Zl),ukol(_,_,_,_,Z2)) :- Z1>Z2. Hana Rudová, Logické programování 1,15. května 2013 8 Omezující podmínky Plánování a domény D.Ú. Plánování a precedence: precedence(Tasks) Napište predikát nastav_domeny/3, který na základě datové struktury [ukol (Id ,Doba,MinStart,MaxKonec) | Úkoly] vytvoří doménové proměnné Začátky pro začátky startovních dob úkolů a strukturu Tasks vhodnou pro omezení cumulative/1, jejíž prvky jsou úlohy ve tvaru task(Začátek,Doba,Konec,1,Id). % nastav_domeny(+Ukoly,-Začátky,-Tasks) nastav_domeny( [],[],[]). nastav_domeny([ukol(Id,Doba,Mi nStart.MaxKonec)|Úkoly],[Z|Začátky], [task(Z,Doba,K,l,Id)ITasks]) :-MaxStart is MaxKonec-Doba, Z in MinStart..MaxStart, K #= Z + Doba, nastav_domeny(Úkoly,Začátky.Tasks). Hana Rudová, Logické programování 1,15. května 2013 9 Omezující podmínky Kumulativní rozvrhování ■ 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)],[li mi t(3)]) 2 3 1 1 1 1 1 1 2 3 4 5 6 Hana Rudová, Logické programování 1,15. května 2013 11 Omezující podmínky Rozšiřte řešení předchozího problému tak, aby umožňovalo zahrnutí precedencí, tj. jsou zadány dvojice úloh A a B a musí platit, že A má být rozvrhováno před B. % prec(IdA.IdB) prec(8,7). prec(6,12). prec(2,l). Pro určení úlohy v Tasks lze použít nthl(N, Seznam, NtyPrvek) z knihovny :- use_module(library(lists)). precedence(Tasks) :- findall(prec(A,B),prec(A,B),P), omezeni_precedence(P,Tasks). omezeni_precedence([],_Tasks). omezeni_precedence([prec(A,B)|Přec],Tasks) :- nthl(A,Tasks,task(ZA,DA,_KA,l,A)), nthl(B,Tasks,task(ZB,_DB,_KB,1,B)), ZA + DA #=< ZB, omezeni_precedence(Prec,Tasks). Hana Rudová, Logické programování 1,15. května 2013 10 Omezující podmínky Plánování a lidé Modifikujte řešení předchozího problému tak, že ■ odstraňte omezení na nepřekrývání úkolů ■ přidejte omezení umožňující řešení každého úkolu zadaným člověkem (každý člověk může zpracovávat nejvýše tolik úkolů jako je jeho kapacita) ukoly(Zacatky) :- % původně domenyCUkoly,Začátky,Tasks), cumulative(Tasks), labeling([],Začátky), tiskni(Úkoly,Začátky). ukoly_lide(Zacatky) :- % upravená verze domeny(Ukoly,Začátky,Tasks), 1ide(Tasks,Lide), labeling([],Začátky), ti skni_li de(Li de,Ukoly,Začátky). Hana Rudová, Logické programování 1,15. května 2013 12 Omezující podmínky Plánování a lidé Plánování a lidé (pokračování) % clovek(Id,Kapacita,IdUkoly) % clovek Id zpracovává úkoly v seznamu IdUkoly clovek(l,2,[1,2,3,4,5]). clovek(2,l,[6,7,8,9,10]). clovek(3,2,[11,12,13,14,15]). ]ide(Tasks,Lide) :- findall (clovek(Kdo,Kapacita,Úkoly),clovek(Kdo,Kapacita,Úkoly), Lide) , omezeni_lide(Lide,Tasks). omezeni_lide([],_Tasks). omezeni_1ide([clovek(_Id,Kapacita,UkolyCloveka)|Lide],Tasks) :-omezeni_clovek(UkolyCloveka,Kapaci ta,Tasks), omezeni_lide(Lide,Tasks). Hana Rudová, Logické programování 1,15. května 2013 13 Omezující podmínky Napište predikát omezeni_clovek(UkolyCloveka,Kapacita,Tasks) , který ze seznamu Tasks vybere úlohy určené seznamem UkolyCloveka a pro takto vybrané úlohy sešle omezení cumulative/2 s danou kapacitou člověka Kapacita. Pro nalezení úlohy v Tasks lze použít nthl(N,Tasks,NtyPrvek) z kni hovny :- use_module(library(lists)). omezeni_clovek(UkolyCloveka,Kapacita,Tasks) :- omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[]). omezeni_clovek([].Kapacita,_Tasks.TasksC) :- cumulativeCTasksC,[limit(Kapacita)]). omezeni_clovek([U|UkolyCloveka],Kapacita,Tasks,TasksC) :- nthl(U,Tasks,TU), omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[TU|TasksC]). Hana Rudová, Logické programování 1,15. května 2013 14 Omezující podmínky