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: 3 SEND + MORE MONEY M různá písmena mají přiřazena různé cifry i 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 M 1 omezení pro nerovnost: all_distinct([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, 21. května 2009 2 Omezující podmínky Jazykové prvky Nalezněte řešení pro algebrogram DONALD + GERALD = ROBERT -• Struktura programu algebrogramC Cifry ) :-domain(. . .) , constraints(...), labeling(...)■ -• Knihovna pro CLP(FD) :- use_module(library(clpfd)) . -• Domény proměnných domain( Seznam, MinValue, MaxValue ) M Omezení all_distinct( Seznam ) -• Aritmetické omezení a*b + c #= d -• Procedura pro prohledávání stavového prostoru labeling([], [XI, X2, X3]) Hana Rudová, Logické programování I, 21. května 2009 3 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, 21. května 2009 4 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. Ukolyjsou zadány následujícím způsobem: % úkol(Id,Doba,Mi nStart,MaxKonec) úkol(1,4,8,70). úkol(2,2,7,60). úkol(3,1,2,25). úkol(4,6,5,55). úkol(5,4,1,45). úkol(6,2,4,35). úkol(7,8,2,25). úkol(8,5,0,20). úkol(9,1,8,40). úkol(10,7,4,50). úkol(11,5,2,50). úkol(12,2,0,3 5). úkol(13,3,30,60). úkol(14,5,15,70). úkol(15,4,10,40). Kostra řešení: úkol y(Začátky) :- domeny(Ukoly,Začátky,Doby), serial i zed(Začátky,Doby), 1abeli ng([],Začátky). domény(Úkoly,Začátky,Doby) :- findall(úkol(Id,Doba,MinStart,MaxKonec), úkol(Id,Doba,MinStart,MaxKonec), Úkoly), nastav_domeny(Úkol y,Začátky,Doby). Hana Rudová, Logické programování I, 21. května 2009 5 Omezující podmínky Plánování: výstup tiskni(Úkoly,Začátky) :- priprav(Ukoly,Začátky,Vstup), quicksort(Vstup,Vystup), ni, tiskni(Vystup). priprav([] , [] , []). při prav([úkol(Id,Doba,MinStart,MaxKonec)|Úkoly], [Z|Začátky], [úkol(Id,Doba,MinStart,MaxKonec,Z)IVstup]) :- priprav(Ukoly,Začátky,Vstup). tiskni ([]) : - ni . 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] ), tiskni(Vystup). Hana Rudová, Logické programování I, 21. května 2009 6 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), quicksortlCSmall, A1-[X|A2]), quicksortl(Big, A2-Z2). splitCX, [], [], []). splitCX, [Y|T], [YlSmall], Big) :- greater(X,Y), !, splitCX, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- splitCX, T, Small, Big). greaterCukol(_,_,_,_,Zl),úkol(_,_,_,_,Z2)) :- Z1>Z2. Hana Rudová, Logické programování I, 21. května 2009 7 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(Úkol y,Začátky,Doby). Hana Rudová, Logické programování I, 21. května 2009 8 Omezující podmínky Plánování a precedence 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)). Hana Rudová, Logické programování I, 21. května 2009 9 Omezující podmínky Plánování a precedence 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(prec(A,B),prec(A,B),P), omezeni_precedence(P,Začátky,Doby). omezeni_precedence([],_Zacatky,_Doby). omezeni_precedence([prec(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, 21. května 2009 9 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 jeden úkol) % clovek(Id,IdUkoly) ... človek Id zpracovává úkoly v seznamu IdUkoly clovek(l,[1,2,3,4,5]). clovek(2,[6,7,8,9,10]). clovek(3,[11,12,13,14,15]). Hana Rudová, Logické programování I, 21. května 2009 10 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 jeden úkol) % clovek(Id,IdUkoly) ... človek Id zpracovává úkoly v seznamu IdUkoly clovek(l,[1,2,3,4,5]). clovek(2,[6,7,8,9,10]). clovek(3,[11,12,13,14,15]). li de(Začátky,Doby,Lide) :- findall(clovek(Kdo,IdUkoly),clovek(Kdo,IdUkoly), Lide), omezeni_li de(Li de,Začátky,Doby). omezeni_lide([],_Zacatky,_Doby). omezeni_lide([Clovek|Lide],Začátky,Doby) :- Clovek=clovek(_Id,IdUkoly), omezeni_clovek(IdUkoly,Začátky,Doby), omezeni_li de(Li de,Začátky,Doby). Hana Rudová, Logické programování I, 21. května 2009 10 Omezující podmínky Plánování a lidé (pokračování) omezeni_clovek(Idllkoly,Začátky,Doby) : - omezeni_clovek(Idllkoly,Začátky,Doby, [],[]). % omezeni_clovek(IdUkoly,Začátky,Doby,Cl ovekZ,Cl ovekD) 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(Idllkoly,Začátky,Doby, [Z|ClovekZ] , [D|C1 ovekD]) Hana Rudová, Logické programování I, 21. května 2009 1 1 Omezující podmínky Plánování a lidé (pokračování) omezeni_clovek(Idllkoly,Začátky,Doby) : - omezeni_clovek(Idllkoly,Začátky,Doby, [],[]). % omezeni_clovek(IdUkoly,Začátky,Doby,Cl ovekZ,Cl ovekD) 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, 21. května 2009 1 1 Omezující podmínky li de(Začátky,Doby,Lide) :- fi ndal1(clovek(Kdo,Kapacita,IdUkoly),clovek(Kdo,Kapacita,IdUkoly), Lide), omezeni_li de(Li de,Začátky,Doby). omezem'_lide([] ,_Zacatky,_Doby) . omezem'_lide([clovek(_Id, Kapacita, IdUkoly) | Lide] ,Začátky,Doby) : - omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby), omezeni_li de(Li de,Začátky,Doby). omezem'_clovek(IdUkoly, Kapacita,Začátky,Doby) : - omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby,[],[]). omezem'_clovek([] , Kapaci ta, _Zacatky,_Doby,ClovekZ,ClovekD) : - 1ength(ClovekZ,Delka), 1 i stOfl(Delka,Li stOf1), cumulati ve(ClovekZ,ClovekD,Li stOf1,Kapaci ta). omezem'_clovek([U | IdUkoly] , Kapaci ta, 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,[]) :- !. listOfl(D,[1|L]) :- Dl is D-l, listOfl(Dl,L). Hana Rudová, Logické programování I, 21. května 2009 12 Omezující podmínky