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,D,C,E,R,B,T] ) :- domai n(...), a"l"l_distinct(. . .), TabelingC.. .) . Knihovna pro CLP(FD) Domény proměnných Omezení Aritmetické omezení % domény proměnných % omezeni % prohledávám' stavového prostoru :- use_module("library(clpfd)) . domain( Seznam, MinValue, MaxValue ) a"l"l_di sti nct( Seznam ) A*B + C #= D Procedura pro prohledávání stavového prostoru Hana Rudová, Logické programování I, 6. května 2010 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í I, 6. května 2010 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 all_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í I, 6. května 2010 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í I, 6. května 2010 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). domény(Ukoly,Začátky,Tasks) :- findal1(ukol(Id,Doba,MinStart.MaxKonec), ukol(Id,Doba,MinStart,MaxKonec), Úkoly), nastav_domeny(Ukoly,Začátky,Tasks). Hana Rudová, Logické programování I, 6. května 2010 6 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, 6. května 2010 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í I, 6. května 2010 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í I, 6. května 2010 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í I, 6. května 2010 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í I, 6. května 2010 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) % 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]) 1ide(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í I, 6. května 2010 12 Omezující podmínky Plánování a lidé (pokračování) 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_modu]eOibraryOists)) . omezen i _c"lovek (Úkol ydoveka, Kapacita, Tas ks) : - omezen i _c"lovek (Úkol yCloveka, Kapacita, Tasks , []) . omezen i _c"lovek( [] , Kapaci ta,_Tasks .TasksC) : - cumulativeCTasksC,[limit(Kapacita)]). omezen i _c"lovek( [U | Úkol yCloveka], Kapaci ta, Tas ks , TasksC) : - nthl(U,Tasks,TU), omezen i _c"lovek (Úkol yCloveka, Kapaci ta, Tasks , [TU | TasksC]) . Hana Rudová, Logické programování I, 6. května 2010 13 Omezující podmínky