为什么在验证中将clpfd变量分配给实际值? [英] Why a clpfd variable is assigned to an actual value in a reification?

问题描述

我正在研究(SWI-)Prolog程序，该程序使用CLP(FD)约束来查找特定问题的解决方案.为此，我碰巧需要两个列表的未定位"重叠部分.那就是:

I'm working on a (SWI-)Prolog program that uses CLP(FD) constraints to find a solution for a particular problem. To do so, I happen to need what I call an "unpositioned" overlapping of two lists. That is:

• 列表La的长度为A
• 列表Lb的长度为B
• A> B
• 未定位的重叠列表为La+Lb，其中元素以一对一的方式添加.

• List La has length A
• List Lb has length B
• A > B
• The unpositioned overlapping list is La+Lb, where elements are added in a one-by-one fashion.

但是，我需要Lb具有一个变量偏移量(即，每个列表的第一个元素在La+Lb加法中的位置都不相同.但是，列表Lb始终是在La的宽度内.例如:

However, I need Lb to have a variable offset (i.e. each lists' first element are not in the same position for the La+Lb addition. However, list Lb is always within the width of La. For instance:

成为La = [0,1,1,1,1,0,1,1,1]和Lb = [1,2,2].

可能的情况1

(Lb) 1 2 2 . . . . . . ---> offset = 0
(La) 0 1 1 1 1 0 1 1 1
( +) 1 3 3 1 1 0 1 1 1   

可能的情况2

(Lb) . . . 1 2 2 . . . ---> offset = 3
(La) 0 1 1 1 1 0 1 1 1
( +) 0 1 1 2 3 2 1 1 1   

可能的情况3

(Lb) . . . . . 1 2 2 . ---> offset = 5
(La) 0 1 1 1 1 0 1 1 1
( +) 0 1 1 1 1 1 3 3 1   

我想要的是将offset定义为与特定域相关联的 clpfd 变量.为了计算La+Lb，我编写了谓词overlap/6，如下:

What I want is to define the offset as a clpfd variable with a particular domain associated to it. In order to compute La+Lb I've written the predicate overlap/6, which is the following:

overlap([],[],_,_,_,[]) :- !.
overlap([],_, _,_,_,[]) :- !.
overlap(A, [],_,_,_, A) :- !.
overlap(A, _,Os,_,_, A) :- length(A,L), L =< Os, !.
overlap([A|As],[B|Bs],0,Os,S,[A|Ls]) :-  % Os is the actual Offset 
    A #= B #<== S #= Os,                 % S is a clpfd variable
    overlap(As,Bs,0,Os,S,Ls),!.
overlap([A|As],Bs,Acc,Os,S,[A|Ls]) :-
    Acc > 0,
    Acc0 is Acc-1,
    overlap(As,Bs,Acc0,Os,S,Ls),!.

想法是通过调用overlap/6来找到La+Lb，然后使用indomain(S)使数字收敛到加法的特定解.我的问题是，当Prolog到达行A #= B #<==> S #= Os时，将S分配给Os(大小写偏移值)，而不是使用已确定的条件约束A.

The idea is to find La+Lb by calling overlap/6 then, with indomain(S), make the numbers converge to a particular solution of the addition. My problem is that when Prolog reaches the line A #= B #<==> S #= Os, S is assigned to Os (a case offset value), rather to constrain A with a reified condition.

我疯了吗，这没有道理吗?有什么适当的方法可以做我正在尝试的事情吗?预先感谢！

Am I crazy and this makes no sense? Is there any proper way to do what I'm trying? Thanks in advance!

的想法是为S范围内的每个点调用overlap/6，然后使用此约束列表标记适当的S.

The idea is to call overlap/6 for every point within S's domain, and use this constraining list to label a proper S afterwards.

统一示例:

?- S in 0..2,
   L0 = [0,0,0,0],
   overlap(L0, [1,2], 0, S, L1),
   overlap(L1, [1,2], 1, S, L2),
   overlap(L2, [1,2], 2, S, L).
L = [_G1, _G2, _G3, _G4]

_G1 in 0\/1
_G2 in 0\/1\/2
_G3 in 0\/1\/2
_G4 in 0\/2

_G1 #= 1 #<== S #= 0
_G1 #= 0 #<== S #> 0

_G2 #= 2 #<== S #= 0
_G2 #= 1 #<== S #= 1
_G2 #= 0 #<== S #> 2

_G3 #= 0 #<== S #= 0
_G3 #= 2 #<== S #= 1
_G3 #= 1 #<== S #< 2

_G1 #= 0 #<== S #= 0
_G4 #= 0 #<== S #= 1
_G4 #= 2 #<== S #= 2

或者:

?- S in 0..2,
   L0 = [0,0,0,0],
   overlap(L0, [1,2], 0, S, L1),
   overlap(L1, [1,2], 1, S, L2),
   overlap(L2, [1,2], 2, S, L),
   indomain(S).
S = 0
L = [1, 2, 0, 0]

推荐答案

如果与起始位置S存在重叠，我们期望约束的合取，以便覆盖所有重叠的位置.例如:

If there is an overlap with starting position S, we expect a conjunction of constraints so that all overlapping positions are covered. For example:

:- use_module(library(clpfd)).

overlap_at(As, Bs, S, ABs) :-
        length(As, L),
        L1 #= L - 1,
        S in 0..L1,
        overlap_at_(As, Bs, S, 0, ABs).

overlap_at_([], _, _, _, []).
overlap_at_([A|As], Bs, S, N0, [AB|ABs]) :-
        overlap_here(Bs, [A|As], [AB|ABs], Conj),
        S #= N0 #==> Conj,
        S #> N0 #==> AB #= A,
        N1 #= N0 + 1,
        overlap_at_(As, Bs, S, N1, ABs).

overlap_here(_, [], _, 1) :- !.
overlap_here([], _, _, 1).
overlap_here([B|Bs], [A|As], [AB|ABs], (AB #= A + B #/\ Rest)) :-
        overlap_here(Bs, As, ABs, Rest).

请注意我如何描述overlap_here/4中的连词.

Notice how I describe a conjunction in overlap_here/4.

示例查询:

?- overlap_at([0,1,1,1,1,0,1,1,1], [1,2,2], 3, ABs).
ABs = [0, 1, 1, 2, 3, 2, _G909, _G912, _G915],
_G909 in inf..sup,
_G912 in inf..sup,
_G915 in inf..sup.

这为您提供了不错的解决方案:可以根据需要实例化所有(包括)重叠的元素.第三个参数当然也可以是一个变量:例如尝试

This gives you a good chunk of the solution: All elements up to and including the overlap are instantiated as desired. The third argument can of course also be a variable: Try for example

?- overlap_at([0,1,1,1,1,0,1,1,1], [1,2,2], S, ABs), 
   indomain(S), writeln(ABs), false.

产生如下内容:

[1,3,3,_,_,_,_,_,_]
[0,2,3,3,_,_,_,_,_]
[0,1,2,3,3,_,_,_,_]
[0,1,1,2,3,2,_,_,_]
[0,1,1,1,2,2,3,_,_]
[0,1,1,1,1,1,3,3,_]
[0,1,1,1,1,0,2,3,3]
[0,1,1,1,1,0,1,2,3]
[0,1,1,1,1,0,1,1,2]

我将剩下的作为练习:不受重叠影响的尾随位置必须等于A的元素.另外，您可能希望进一步限制重叠的可能位置，而我一直将其保留得比较笼统.

I leave the rest as an exercise: Trailing positions that are not affected by the overlap need to be made equal to elements of A. Also, you may want to further restrict the possible positions of the overlap, which I have kept rather general.

这篇关于为什么在验证中将clpfd变量分配给实际值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！