Logické programování s omezujícími podmínkami
Algebrogram
Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo:
M různá písmena mají přiřazena různé cifry J SaM nejsou 0
Proměnné: S,E,N,D,M,O,R,Y
Domény: [1 ..9] pro S,M      [0..9] pro E,N,D,0,R,Y 1 omezení pro nerovnost: all_distinct([S,E,N,D,M,0,R,Y]) 3 1 omezení pro rovnosti:
SEND
+ MORE
MONEY
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, 4.
května 201 2
Omezující podmínky
Jazykové prvky
Nalezněte řešení pro algebrogram
DONALD + GERALD = ROBERT
Struktura programu
algebrogram( [D,0,N,A,L,G,E,R,B,T] ) domai n(...),
all_distinct(...),  ... #= 1abeli ng(...).
% domény proměnných % omezeni
% prohledáváni stavového prostoru
Knihovna pro CLP(FD)
:- use_module(library(clpfd))
Domény proměnných
Omezení
Aritmetické omezení
domain( Seznam, MinValue, MaxValue )
all_distinct( Seznam )
A*B + C #= D
Procedura pro prohledávání stavového prostoru
Hana Rudová, Logické programování I, 4. května 201 2
1abeli ng([],Seznam)
Omezující podmínky
Algebrogram: řešení
:- use_module(library(clpfd)).
donald(LD):-
% domény
LD=[D,0,N,A,L,G,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*G + 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 labeling([] , LD) .
Hana Rudová, Logické programování I, 4. května 201 2
4
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
Hana Rudová, Logické programování I, 4. května 201 2
5
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)])
3
1      2 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, 4. května 201 2
5
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.
Úkoly jsou zadány následujícím způsobem:
% ukol(Id,Doba,Mi nStart,MaxKonec)
ukol(1,4,8,70).       ukol(2,2,7,60). ukol(3,1,2,25). ukol(4,6,5,55) .
ukol(5,4,1,45).       ukol(6,2,4,35). ukol(7,8,2,25). ukol(8,5,0,20).
ukol(9,1,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(Začátky) :- domeny(Ukoly,Začátky,Tasks),
cumulative(Tasks), 1abeli ng([],Začátky), ti skni(Úkoly,Začátky).
domeny(Ukoly,Začátky,Tasks) :- findall(ukol(Id,Doba,MinStart,MaxKonec),
ukol(Id,Doba,Mi nStart,MaxKonec), Ukoly), nastav_domeny(Ukoly,Začátky,Tasks).
Hana Rudová, Logické programování I, 4. května 2012 6 Omezující podmínky
Plánování: výstup
tiskni(Úkoly,Začátky) :-
připrav(Ukoly,Začátky,Vstup), quicksort(Vstup,Vystup), nl, tiskni(Vystup).
priprav([] ,[],[]).
připrav([ukol(Id,Doba,MinStart,MaxKonec)|Úkoly],  [Z|Začátky], [ukol(Id,Doba,MinStart,MaxKonec,Z)|Vstup]) :-připrav(Ukoly,Začátky,Vstup).
ti skni([]) :- nl . tiskni([V|Vystup]) :-
V=ukol(Id,Doba,MinStart,MaxKonec,Z),
K is 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, 4. května 201 2
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, 4. května 201 2
8
Omezující podmínky
Plánování a domény
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í cumulati ve/l, jejíž prvky jsou úlohy ve tvaru task(Zacatek,Doba,Konec,1,Id).
% nastav_domeny(+Ukoly,-Začátky,-Tasks)
Hana Rudová, Logické programování I, 4.
května 201 2
9
Omezující podmínky
Plánování a domény
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í cumulati ve/l, jejíž prvky jsou úlohy ve tvaru task(Zacatek,Doba,Konec,1,Id).
% nastav_domeny(+Ukoly,-Začátky,-Tasks) nastav_domeny( [] ,[],[]).
nastav_domeny([ukol(Id,Doba,Mi nStart,MaxKonec)|Ukoly],[Z|Začátky] ,
[task(Z,Doba,K,l,Id)ITasks]) :-MaxStart i s MaxKonec-Doba, Z in MinStart..MaxStart, K #= Z + Doba,
nastav_domeny(Ukoly,Začátky,Tasks).
Hana Rudová, Logické programování I, 4.
května 201 2
9
Omezující podmínky
D.Ú. Plánování a precedence: precedence(Tasks)
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 vTasks lze použít nthl(N,Seznam,NtyPrvek) z knihovny
:- use_module(library(lists)).
Hana Rudová, Logické programování I, 4.
května 201 2
10
Omezující podmínky
D.Ú. Plánování a precedence: precedence(Tasks)
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 vTasks lze použít nthl(N,Seznam,NtyPrvek) z knihovny
:- use_module(library(lists)).
precedence(Tasks) :- findal1(prec(A,B),prec(A,B),P),
omezeni_precedence(P,Tasks).
omezeni_precedence([],_Tasks).
omezeni_precedence([přec(A,B)|Přec],Tasks) :-
nthl(A,Tasks,task(ZA,DA,_KA,1,A)),
nthl(B,Tasks,task(ZB,_DB,_KB,1,B)),
ZA + DA #=< ZB,
omezeni_precedence(Prec,Tasks).
Hana Rudová, Logické programování I, 4. května 2012 10 Omezující podmínky
Kumulativní rozvrhování
M 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
Hana Rudová, Logické programování I, 4. května 201 2
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,1,4)],[li mi t(3)])
Hana Rudová, Logické programování I, 4. května 201 2
Omezující podmínky
Plánování a lidé
Modifikujte řešení předchozího problému tak, že
M 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(Začátky) :- % původně
domeny(Ukoly,Začátky,Tasks), cumulative(Tasks), 1abeli ng([],Začátky), ti skni(Úkoly,Začátky).
ukoly_li de(Začátky) :- % upravená verze
domeny(Ukoly,Začátky,Tasks), 1 i de(Tasks,Li de), 1abeli ng([],Začátky), ti skni_li de(Li de,Úkoly,Začátky).
Hana Rudová, Logické programování I, 4. května 2012 12 Omezující podmínky
Plánování a lidé
% 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]).
Hana Rudová, Logické programování I, 4. května 201 2
Omezující podmínky
Plánování a lidé
% clovek(Id,Kapacita,IdUkoly)
% človek 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]).
1 i de(Tasks,Lide) :-
findal1(clovek(Kdo,Kapacita,Úkoly),clovek(Kdo,Kapacita,Úkoly), Lide), omezeni_li de(Li de,Tasks).
omezeni_1i de([],_Tasks).
omezeni_lide([clovek(_Id,Kapacita,UkolyCloveka)|Lide],Tasks) :-
omezeni_clovek(UkolyCloveka,Kapacita,Tasks), omezeni_li de(Li de,Tasks).
Hana Rudová, Logické programování I, 4.
května 201 2
1 3
Omezující podmínky
Plánování a lidé (pokračování)
Napište predikát omezeni _clovek(UkolyCloveka, Kapacita, Tas ks), který ze seznamu Tasks vybere úlohy určené seznamem UkolyCloveka a pro takto vybrané úlohy sešle omezení cumulati ve/2 s danou kapacitou člověka Kapacita.
Pro nalezení úlohy v Tasks lze použít nthl(N,Tasks, NtyPrvek) z knihovny
:- use_module(library(lists)).
Hana Rudová, Logické programování I, 4. května 201 2
14
Omezující podmínky
Plánování a lidé (pokračování)
Napište predikát omezeni _clovek(UkolyCloveka, Kapacita, Tas ks), 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 knihovny
:- use_module(library(lists)).
omezeni_clovek(UkolyCloveka,Kapacita,Tasks) :-
omezeni _clovek(UkolyCloveka,Kapaci ta,Tas ks,[]).
omezeni_clovek([],Kapacita,_Tasks,TasksC) :-
cumulative(TasksC,[li mi t(Kapacita)]). omezeni_clovek([UIUkolyCloveka],Kapacita,Tasks,TasksC) :-
nthlCU,Tasks,TU),
omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[TU|TasksC]).
Hana Rudová, Logické programování I, 4. května 201 2
14
Omezující podmínky