我正在开发一个 (SWI-)Prolog 程序,该程序使用 CLP(FD) 约束来寻找特定问题的解决方案。为此,我碰巧需要两个列表的“未定位”重叠。那是:
La
长度为 A Lb
长度为 B La+Lb
,其中元素以一对一的方式添加。 但是,我需要
Lb
有一个可变偏移量 (即每个列表的第一个元素在 La+Lb
添加的位置不同。但是,列表 Lb
始终在 La
的宽度内。例如:成为
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
, 如下: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),!.
这个想法是找到
La+Lb
调用 overlap/6
然后,使用 indomain(S)
,使数字收敛到加法的特定解。我的问题是,当 Prolog 到达 A #= B #<==> S #= Os
行时, S
分配给 Os
(大小写偏移值),而不是约束 A
有一个具体化的条件。我疯了吗?这没有任何意义吗?有什么合适的方法来做我正在尝试的事情吗?提前致谢!
编辑:这个想法是调用
overlap/6
对于 S
内的每个点的域,并使用此约束列表来标记正确的 S
然后。统一示例:
?- 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
,我们期望约束的结合,以便覆盖所有重叠的位置。例如:
:- 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
中是如何描述连词的。 .示例查询:
?- 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.
这为您提供了一个很好的解决方案:直到并包括重叠的所有元素都根据需要进行实例化。第三个参数当然也可以是一个变量: 例如尝试
?- 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
的元素.此外,您可能希望进一步限制重叠的可能位置,我一直保持相当笼统。
关于list - 为什么在具体化中将 clpfd 变量分配给实际值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20688099/