close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Constraint Logic
Programming
CLP
1
Prolog and generate and test paradigma
Example: Magic Square
Example 1:
Find a mapping of numerals 0 to 9 on the variables
A, B, ...I such that the totals in all rows and
columns are the same (the corresponding sum has
to be 15).
square1([A,B,C,D,E,F,G,H,I]):generate1([A,B,C,D,E,F,G,H,I]),
test1([A,B,C,D,E,F,G,H,I]).
2 / 23
A
B
C
2
7
6
D
E
F
9
5
1
G
H
I
4
3
8
Umělá inteligence I.
Naive solution 1
square1([A,B,C,D,E,F,G,H,I]):- generate1([A,B,C,D,E,F,G,H,I]),
test1([A,B,C,D,E,F,G,H,I]).
generate1(X):- n_list1(X).
A B C
n_list1([]).
D E F
G H I
n_list1([H|T]):- numeral(H), n_list1(T).
numeral(1).
numeral(6).
numeral(2).
numeral(7).
numeral(3).
numeral(8).
numeral(4).
numeral(9).
numeral(5).
test1([A,B,C,D,E,F,G,H,I]):- all_different([A,B,C,D,E,F,G,H,I]),
A+B+C =:= 15, D+E+F =:= 15, G+H+I =:= 15,A+D+G =:= 15,
B+E+H =:= 15, C+F+I =:= 15,C+E+G =:= 15, A+E+I =:= 15.
all_different([]).
all_different([H|T]):- not_in(H,T), all_different(T).
not_in(_,[]).
not_in(H,[HH|T]):- H=\=HH, not_in(H,T).
3 / 23
Umělá inteligence I.
Criticism + solution 2
Problems: generate1 creates numerous lists of candidate solutions,
which do not meet even the basic condition (no repetition of
numerals).
Number of calls to the predicate numeral is 99 = 387 420 489.
The first solution has been found after 85.66 s (P4, 2.8GHz).
How to improve the solution? More efficient predicate generate2 limits
the repetition of numerals already during the process of generating
the candidate solution.
square2([A,B,C,D,E,F,G,H,I]):generate2([A,B,C,D,E,F,G,H,I]),
test2([A,B,C,D,E,F,G,H,I]).
generate2(X):- n_list2(X).
n_list2([]).
n_list2([H|T]):- n_list2(T), numeral(H), not_in(H,T).
test2([A,B,C,D,E,F,G,H,I]):A+B+C =:= 15,D+E+F =:= 15,G+H+I =:= 15,
B+E+H =:= 15,C+F+I =:= 15,C+E+G =:= 15,
4 / 23
A+D+G =:= 15,
A+E+I =:= 15.
Umělá inteligence I.
Solution 3
square2 program is much quicker
 predicate numeral is called 5 611 770 times only
 the first solution has been found after 0.53 s
Further improvement can be achieved by interleaving the tests which can be checked
with the process of generation of the candidate solution. Heuristics: start setting the
values to the variables which appear most often in the considered totals.
square3([A,B,C,D,E,F,G,H,I]):gentest3(E,[]),
gentest3(A,[E]),
gentest3(I,[E,A]),
A+E+I
gentest3(C,[E,A,I]),
gentest3(G,[E,A,I,C]),
G+E+C
gentest3(B,[E,A,I,C,G]),
A+B+C
gentest3(H,[E,A,I,C,G,B]),
B+E+H
gentest3(D,[E,A,I,C,G,B,H]), A+D+G
gentest3(F,[E,A,I,C,G,B,H,D]),D+E+F
gentest3(D,L) :- numeral(D), not_in(D,L).
=:= 15,
=:=
=:=
=:=
=:=
=:=
A
B
C
D
E
F
G
H
I
15,
15,
15, G+H+I =:= 15,
15,
15, C+F+I =:= 15.
Now, predicate numeral is called 6498 times only and the first solution has been
immediately, ie. in 0.00 s (bellow resolving power). Next solutions in 0.02 s
5 / 23
Umělá inteligence I.
Solution 4
Diversity of used numerals can be ensured if there is available the list of those numerals
which have not been used, yet :
square4([A,B,C,D,E,F,G,H,I]):-
A
B
C
choose(A,R1,R2),
D
E
F
choose(I,R2,R3), A+E+I =:= 15,
G
H
I
choose(E,[1,2,3,4,5,6,7,8,9],R1),
choose(C,R3,R4),
choose(G,R4,R5), G+E+C =:= 15,
choose(B,R5,R6), A+B+C =:= 15,
choose(H,R6,R7), B+E+H =:= 15, G+H+I =:= 15,
choose(D,R7,R8), A+D+G =:= 15,
choose(F,R8,R9), D+E+F =:= 15, C+F+I =:= 15.
% choose(Member,Source_list,What_remains_from_Source_list).
choose(P,[P|T],T).
choose(P,[H|T],[H|TT]):- choose(P,T,TT).
Number of calls of the predicate numeral is reduced to 3361.
The first solution is found in 0.00 s, the same for the further solutions.
6 / 23
Umělá inteligence I.
Alternatives to „generate and test paradigma“
 Solution based on “test and generate paradigma”
The gradual increase of the solution efficiency is due to increased involvement of problem
constraints in the process of generation of candidate solutions.
Can it be ensured by changing the sequence of predicates in the original solution?
search(Solution):- test(Solution), generate(Solution).
 No! But we can get close using the schema: provide constraints and generate
 The idea is to ensure automatic interruption of the generation as soon as any constrain is
violated
This cannot be achieved in standard Prolog, because
 the predicates for testing (e.g. arithm. operations) require that all their arguments are
grounded
 grounding is ensured in the predicate generate
 Additional functionality is needed!! Some implementations of Prolog offer suspension of
goals by a built-in predicate constrain(Variable, Goal)
 if Variable is grounded, the system is asked to solve the Goal
 if Variable is free (not grounded), Goal is suspended (frozen, delayed) until the
Variable is grounded
7 / 23
Umělá inteligence I.
Solution based on suspension
square_c(L) :- test_c(L),n_list1(L).
test_c([A,B,C,D,E,F,G,H,I]):- all_different ([A,B,C,D,E,F,G,H,I]),
total(A,B,C),total(D,E,F),total(G,H,I),total(A,D,G),
total(B,E,H),total(C,F,I),total(A,E,I),total(C,E,G).
total(X,Y,Z):- constrain(X,constrain(Y,constrain(Z,X+Y+Z=:=15))).
n_list1([]).
n_list1([H|T]):- numeral(H), n_list1(T).
all_different_c([]).
all_different_c([H|T]):- not_in_c(H,T), all_different(T).
not_in_c(_,[]).
not_in_c(H,[HH|T]):- constrain(H,constrain(HH, H=\=HH)), not_in_c(H,T).
Number of calls of the predicate numeral is reduced to 2377.
8 / 23
Umělá inteligence I.
Prolog and unification as its basic operation
Advantages of unification
-uniform manipulation with all objects of a language
- programs are understandable and predicates are invertible
- it can be applied to syntacticaly related objekts
Problem appears as soon as we need to compare objekts which have the same meaning
(semantics) but their syntax differs
- e.g. the query ?- 2+3 = 5. fails in standard Prolog, because the two
expressions cannot be unified.
Partial solution of standard Prolog: introduction of extralogical operator is
-is fails whenever it is applied to exprssions with free variables, e.g.
?- 5 is 3 + X. fails in standard Prolog.
Constraint Logic Programming (CLP) tries to resolve both upper mentioned problems:
“test and generate programming paradigma” and unification.
In CLP, unification is replaced by a decision procedure, which takes into account both
syntax and semantics of considered objects.
9 / 23
Umělá inteligence I.
CLP
 CLP is not a pure enhancement of standard Prolog, but its generalization.
Constraints are expressed using a fixed set of operators, e.g. from the domain of
arithmetics (comparison of linear arithmetic expressions), set theory (finite domains).
Each CLP system specifies a set of predicates, which are suspended automaticaly,
whenever their arguments contain free (non-grounded) variables.
The resulting CLP program ensures a direct solution based on “constrain and generate
paradigma” without any additional auxiliary predicates.
 Constraint solving - two approaches
incremental linear methods = the system treats the set C of all constraints requested
up to now as a whole; whenever a new constraint is added to C the resulting set is
tested for consistency (and backtracking is started as soon as inconsistency appears).
 domain technologies = the used variables can be given restrictions concerning their
finite domain using the operator :: (e.g. X :: 1..9). Additional functionality of the
system is on-line propagation of domain constraints between all mutually related
variables. Backtracking is started whenever a domain of any considered variable is
empty.
10 / 23
Umělá inteligence I.
CLP system

i
e
ECL PS
ECLiPSe provides automated suspension of the following
predicates of arithmetics

Real numbers: <, > >=,=<, =:=, =\=
 Racional numbers: $=, $<, …
 Integers: #=, ## (různý), #<, … [-10 000 000, 10 000 000]

Efficient deterministic methods (simplex m., Gaus
elimination, etc.) are used to solve the set of considered
constraints
11 / 23
Umělá inteligence I.
Beatles and spiders
Suppose, you get a closed box with beatles and spiders. You know that
all of them together have 34 legs. How many beatles you have?
insects(Beatles, Spiders,Legs):- Beatles #>0,Spiders#>0,
8*Spiders + 6* Beatles #= Legs.
?- insects(B, S,34).
The system adds the domain info B:: 0..10000000,S:: 0..10 000 000
0 + 6*B <= 8*S + 6*B (=34) <= 8*107 + 6*B, thus 6*B <= 34 and 0<= B <6
8*S + 0 <= 8*S + 6*B (=34) <= 8*S +6*107, thus 8*S <= 34 and 0<= S <5
…
solution Beatles=3, Spiders=2
?- insects(Beatles, Spiders,46).
Spiders= Spiders{[2..5]}, Beatles={[1..5]}
Delayed goals: -46 + 8* Spiders{[2..5]}+6* Beatles={[1..5]}#=0
12 / 23
Umělá inteligence I.
Magic square in ECLiPSe
test5(L):- L=[A,B,C,D,E,F,G,H,I],
L::1..9,
alldifferent(L),
A+B+C #= 15,
D+E+F #= 15,
G+H+I #= 15,
A+D+G #= 15,
B+E+H #= 15,
C+F+I #= 15,
C+E+G #= 15,
A+E+I #= 15.
generate5([]).
generate5([H|T]):- indomain(H),
generate5(T).
13 / 23
Umělá inteligence I.
optimize(+Objective,-Cost)
This build-in predicate (in eplex library) calls the external solver's
optimizer and succeeds if it finds an optimum for the Objective
function. In this case the problem variables get instantiated to the
solution values, and Cost gets bound to the cost of this solution.
Note that this will find at most one solution, ie. you won't get
alternative optima on backtracking.
[eclipse1]:
[eclipse2]:
Y = 2.0
X=2
C = 2.0
yes.
14 / 23
eplex:(X+Y >= 3), eplex:(X-Y =:= 0), optimize(min(X), C).
Y = 1.5
X = 1.5
C = 1.5
yes.
integers([X]), eplex:(X+Y >= 3), eplex:(X-Y =:= 0), optimize(min(X), C).
Umělá inteligence I.
Transportation problem
Costs of
transport
Customer
2
Customer
3
Daily
Producer1 5
1
1
4
Producer2 2
6
9
6
3
5
2
10
Customer’s
requirements
Customer
1
production
optim([X11,X12,X13,X21,X22,X23], Costs) :-
integers ([X11,X12,X13,X21,X22,X23,Costs]),
eplex:( X11 >=0,X12 >=0,X13 >=0, X21 >=0,X22 >=0,X23 >=0),
eplex:( X11+X21 >=3, X12+X22 >=5, X13+X23 >=2),
eplex:( X11 + X12 +X13 <=4, X21 + X22 + X23 <=6),
Costs = 5*X11 +X12 + X13 + 2*X21 + 6*X22, +9*X23,
optimize(min(Costs),C).
X = [0,2,2,3,3,0], C =28.
15 / 23
Umělá inteligence I.
On-line Guide to Constraint Programming, Roman Barták,
2001. http://kti.ms.mff.cuni.cz/~bartak/constraints/
The ECLiPSe Constraint Logic Programming System,
Imperial College London, 2001.
http://www.icparc.ic.ac.uk/eclipse
16 / 23
Umělá inteligence I.
1/--страниц
Пожаловаться на содержимое документа