CS计算机代考程序代写 .

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

Declarative Programming
More on Finite Domains

Geraint A. Wiggins

Professor of Computational Creativity
Department of Computer Science

Vrije Universiteit Brussel

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

Reasoning about domains

▶ So far, we have covered the establishment of integer finite
domains for variables, and how they can be programmed
at the object level

▶ It is possible, however, to ask questions about the
domains themselves, using meta-predicates

▶ For example, we can ask what is the minimum possible
value of a domain at any given time:

?- X in 1..10, X #\= 1, fd_inf( X, Min ).

Min = 2
X in 2..10 ?
true

▶ This is useful when we want to forcibly minimise a value

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

Reasoning about domains (2)

▶ We can ask about the size of a domain:
?- X in 1..10, X in 5..15,

fd_size( X, Size ).

Size = 6
X in 5..10 ?
true

▶ This is useful when we want to constrain search by
instantiating the variable with the smallest domain first

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

Reasoning about domains (3)

▶ And we can get at the whole domain (in two ways), in
case we want to do some more subtle search control:

?- X in 1..10, X #\= 5,
fd_dom( X, Dom ).

Dom = (1..4)\/(6..10)
X in (1..4)\/(6..10) ?
true

▶ All these predicates are used to implement the
labeling/2 predicate

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

Labelling variables

▶ The predicate labeling/2 (note the American spelling)
is a fast way of “filling the gaps” in a constraint system
involving many variables

▶ Of course, not all constraint systems have a unique
solution, and we need a way of choosing values

▶ One other way is to use indomain/1, but this only works
for one variable at a time

▶ labeling/2 takes arguments as follows:
1. A control specification;
2. A list of variables to be given values

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

Labelling variables (2)

▶ The control specification consists of three parts:
Variable choice heuristic – in which order to instantiate

variables;
Value choice heuristic – how to search through the

possible values;
Optimality – all solutions, or just one optimal one.

▶ We can use these options to improve our search,
depending on what we know about the distributions of
the solutions about the domains

▶ Sometimes, they can make a considerable improvement,
particularly when many inequalities are involved; however,
sometimes, as in the fd_adder example, they make
things worse

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

Labelling variables (3)
▶ Two particularly useful options are maximize and

minimize (again, note the spelling)
▶ They tie a variable to its maximum (minimum) possible

value as the labelling is generated eg
% without labelling
?- X in 1..10, Y in 2..8, X #< Y + 2. X in 1..9, Y in 2..8 ? true % with labelling ?- X in 1..10, Y in 2..15, X #< Y + 2, labeling( [max(X)], [X,Y] ). X = 10, Y = 9 ? ; false . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Labelling variables (4) ▶ We can maximize more than one variable: ?- X in 1..10, Y in 2..15, X #< Y + 2, labeling( [max(X),max(Y)], [X,Y] ). X = 10, Y = 15 ? ; false Note that the variable named last is the one to be maximized. ▶ Note that when we use optimisation, we only get one solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Labelling variables (5) ▶ In some constraint systems, we can maximise more than one variable; the order in which variables are maximised can affect their values ▶ To see why, consider each variable as one of a number of dimensions defining a multi-dimensional space ▶ The domains of the variables demarcate a hyper-solid in that space, in the body of which solutions may lie ▶ The hyper-solid may have local maxima and minima with respect to some dimensions which are not global ▶ This constraint system will try to explore all the maxima and minima on backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example: resource allocation ▶ Suppose we have to design a simple program for stock control: ▶ We have a number of boxes to stack in a restricted space. All the boxes are of the same width and depth, but their heights vary. ▶ The largest boxes contain the heaviest goods, and so should be stacked lowest ▶ The space available is big enough for 1 box deep (4 units), and 4 boxes along (16 units), but it is only 8 units high. ▶ How can we stack the boxes to make them fit? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example: resource allocation (2) ▶ Our box sizes can be represented like this: % box( number, height ) :- block box( -, - ). box( 1, 2 ). box( 2, 2 ). box( 3, 6 ). box( 4, 2 ). box( 5, 4 ). box( 6, 2 ). box( 7, 6 ). box( 8, 5 ). box( 9, 3 ). ▶ box/2 is blocked to prevent too-early choice of box and height . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example: resource allocation (3) ▶ We can constrain the physical properties of individual boxes like this: constrain_boxes( [], [], [] ). constrain_boxes( [Box|Boxes], [B,T,Stack|Variables], [box( Box,B,T,H,Stack ) |BoxList] ) :- box( Box, H ), space( _MaxWidth, MaxHeight ), T in 0..MaxHeight, B in 0..MaxHeight, H in 2..6, T #= B + H, Stack in 1..4, constrain_boxes( Boxes, Variables, BoxList ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example: resource allocation (4) ▶ We can constrain the relationships between boxes like this: link_boxes( [] ). link_boxes( [_] ). link_boxes( [box( _, _, T1, H1, Stack1 ), box( Box2, B2, T2, H2, Stack2 )|Boxes] ) :- Stack2 #>= Stack1,
Stack2 #=< Stack1 + 1, ( Stack1 #= Stack2 ) #==> ( H1 #>= H2 ),
( Stack1 #= Stack2 ) #<==> ( T1 #= B2 ),
( Stack1 #= Stack2 – 1 ) #<==> ( B2 #= 0 ),
link_boxes( [box( Box2, B2, T2, H2, Stack2 )|

Boxes] ).

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

.
.
.

.

Example: resource allocation (5)
▶ We link the two together like this:

store_boxes( BoxList ) :-
length( BoxList, 9 ),
length( BoxNumbers, 9 ),
all_different( BoxNumbers ),
constrain_boxes( BoxNumbers, Variables,

BoxList ),
link_boxes( BoxList ),
labeling( [ffc], Variables ).

▶ And we get a solution:
X = [box(5,0,4,4,1),box(1,4,6,2,1),

box(2,6,8,2,1),box(8,0,5,5,2),
box(9,5,8,3,2),box(3,0,6,6,3),
box(4,6,8,2,3),box(7,0,6,6,4),
box(6,6,8,2,4)] ?