Logické programování s omezujícími podmínkami
Jazykové prvky
Nalezněte řešení pro algebrogram
DONALD + CERALD = ROBERT
■ Struktura programu
algebrogram( Cifry ) :-domai n(...), constraints(...) , labe"ling(. . .) .
■ Knihovna pro CLP(FD)
■ Domény proměnných
■ Omezení
■ Aritmetické omezení
:- 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       labeling([], [xi, X2, X3])
Hana Rudová, Logické programování I, 7. května 2007
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, 7. května 2007 2 Omezující podmínky
Algebrogram: řešení
:- usejioduleOibraryCclpfd)) .
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(l_D) ,
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, 7. května 2007
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).       ukol(2,2,7,60).       ukol(3 ,1,2 ,25) . ukol(4,6, 5 , 55) .
ukol(6,2,4,35).       úkol (7,8,2,25) . ukol(8, 5 ,0,20) .
ukol(10,7,4,50).     ukol(11,5,2,50).       ukol(12,2,0,35). ukol(14,5,15,70).    ukol(15,4,10,40).
ukol(5,4,l,45) . ukol(9,l,8,40). ukol(13,3,30,60).
Kostra řešení: ukoly(Zacatky)
domény(Úkoly,Začátky,Doby), seriál ized(Začátky,Doby), labeling([],Začátky).
domény(Úkoly,Začátky,Doby) :- findal1(ukol(Id,Doba,MinStart.MaxKonec) ,
ukol(Id,Doba,MinStart,MaxKonec), Úkoly), nastav_domeny(Úkoly,Začátky,Doby).
Hana Rudová, Logické programování I, 7. května 2007 5 Omezující podmínky
Plánování: výstup II
quicksort(S, Sorted) :- quicksortl(S,Sorted-[]).
quicksortl([],Z-Z).
quicksortl([X|Tail], A1-Z2) :-
spi i t(X, Tail, Small, Big), quicksortKSmall , A1-[X|A2]), quicksortl(Big, A2-Z2).
split(_X,  [],  [], []).
split(X,  [Y I T],  [Y I Small], Big) :-
split(X,  [YIT], Small,   [Y|Big]) :-
greater(X.Y), !, split(X, T, Small, Big). split(X, T, Small, Big).
greater(ukol(_
,Zl),ukol(_
,Z2))
Z1>Z2.
Hana Rudová, Logické programování I, 7. května 2007
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([], [] , []) .
pri 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([VIVystup]) :-
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, 7. května 2007 6
Omezující podmínky
Plánování a domény
nastav_domeny( [] ,[],[]).
nastav_domeny([U|Úkoly],[Z|Začátky],[Doba|Doby]) U=ukol(_Id,Doba,MinStart,MaxKonec), MaxStart is MaxKonec-Doba, Z in MinStart..MaxStart, nastav_domeny(Úkoly,Začátky,Doby).
Hana Rudová, Logické programování I, 7. května 2007
Omezující podmínky
Plánování a precedence
Plánování a lidé
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 zjištění parametrů úlohy lze použít např. nth(N,Seznam,NtyPrvek) z knihovny
:- use_module(library(lists)) .
precedence(Zacatky,Doby) :-
findall CprecCA,B),prec(A,B),P), omezeni_precedence(P,Začátky,Doby).
omezeni_precedence([],_Zacatky,_Doby).
omezeni_precedence([přec(A,B)|Přec],Začátky,Doby) : -
nth(A,Začátky,ZA), nth(B,Začátky,ZB), nth(A,Doby,DA),
ZA + DA #< ZB,
omezeni_precedence(Prec,Začátky).
Hana Rudová, Logické programování I, 7. května 2007 9 Omezující podmínky
Plánování a lidé (pokračování)
omezeni_clovek(IdUkoly, Začátky, Doby) : -
omezeni_clovek(IdUkoly,Začátky,Doby, [] , []) .
% omezeni_clovek(IdUkoly,Začátky,Doby,ClovekZ,ClovekD) omezeni_clovek([],_Zacatky,_Doby,ClovekZ,ClovekD) :-
serialized(ClovekZ,ClovekD). omezeni_clovek([U|IdUkoly],Začátky,Doby,ClovekZ,ClovekD) :-
nth(U,Začátky,Z),
nth(U,Doby,D),
omezeni_clovek(IdUkoly,Začátky,Doby,[Z|ClovekZ],[D|ClovekD]).
Rozšiřte řešení problému tak, aby mohl každý člověk zpracovávat několik úkolů dle jeho zadané kapacity.
% clovek(Id,Kapacita,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, 7. května 2007 11 Omezující podmínky
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 jeden úkol)
% clovek(Id,IdUkoly) ... clovek Id zpracovává úkoly v seznamu IdUkoly clovekCl, [1,2,3,4,5]).    clovek(2,[6,7,8,9,10]).    clovek(3,[11,12,13,14,15]).
li de(Začátky,Doby,Li de) :-
fi ndal1(clovek(Kdo,IdUkoly),clovek(Kdo,IdUkoly), Li de), omezeni_1i de(Li de,Začátky,Doby).
omezeni_lide([],_Zacatky,_Doby).
omezeni_1i de([Clovek|Lide],Začátky,Doby) :-
Clovek=clovek(_Id,IdUkoly),
omezeni_clovek(IdUkoly,Začátky,Doby),
omezeni_1i de(Li de,Začátky,Doby).
Hana Rudová, Logické programování I, 7. května 2007 10 Omezující podmínky
1 i de(Začátky,Doby,Lide) :-
fi ndal1(clovek(Kdo,Kapacita,IdUkoly),clovek(Kdo,Kapacita,IdUkoly), Li dc omezeni_1i de(Li de,Začátky,Doby).
omezeni_lide([],_Zacatky,_Doby).
omezeni_1ide([clovek(_Id,Kapacita,IdUkoly)|Lide],Začátky,Doby) :-omezeni_clovek(IdUkoly,Kapaci ta,Začátky,Doby), omezeni_1i de(Li de,Začátky,Doby).
omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby) :-
omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby,[],[]).
omezeni_clovek([],Kapacita,_Zacatky,_Doby,ClovekZ,ClovekD) :-
1ength(ClovekZ,Delka), 1 i stOfl(Delka,Li stOf1),
cumulative(ClovekZ,ClovekD,Li stOf1,Kapacita). omezeni_clovek([U|IdUkoly],Kapacita,Začátky,Doby,ClovekZ,ClovekD) :-
nth(U,Začátky,Z), nth(U,Doby,D),
omezeni_clovek(IdUkoly.Kapacita,Začátky,Doby,[Z|ClovekZ],[D|ClovekD]). listOf1(0,[]) :- !.
list0fl(D,[1|L])  :- Dl i s D-l, 1 istOf1(D1,L).
Hana Rudová, Logické programování I, 7. května 2007 12 Omezující podmínky