2

我可以将可能值的域分配给变量，即：

 ?- X in 1..3, X #= 3.
 X = 3.

有没有办法添加约束，以便变量可以接受指定域中的值列表？对最大 3 个元素列表的约束，其值在 1..5 范围内呢？

最后一个问题：一个变量 Y 可以接受最多 3 个元素的列表，这些元素在变量 X 接受的值域中（为了它恰好是 1..5）？

任何示例或提示如何开始建立这样的约束？

根据潜伏者：

?- L=[1,2,3], length(L, 3), L ins 1..5.
L = [1, 2, 3].

?- L=[1,2,3,4], length(L, 3), L ins 1..5.
false.

?- L=[1,2,6], length(L, 3), L ins 1..5.
false.

?- L=[1,2,5], length(L, 3), L ins 1..5.
L = [1, 2, 5].


?- L=[4,5], length(L, 3), L ins 1..5.
false.

只有最后一个是关闭的，应该是真的..让我改进一个约束:)

列出 1 到 3 个元素，而不是只有 3 个元素。

哈，这有效：

?- L=[4,5], X in 1..3, length(L, X), L ins 1..5.
L = [4, 5],
X = 2.

CLP 有多酷 :)

现在再细化。如何使列表的元素不重复？

4

3 回答 3

2

在 CLP 中，将约束与不确定性（搜索）分开是很重要的。在基于 Prolog 的框架中，这种区别在语言中并不明显，这常常使初学者感到困惑。

以 Prolog 的length/2之类的谓词为例：虽然从逻辑上讲，这可以被视为对其参数值的“约束”，但在 CLP 术语中，我们通常不将其称为约束，因为它会在任何时候不确定地为其参数生成值这些没有充分实例化。

我们对约束的期望行为更加被动：它应该禁止其参数采用约束语义不允许的值，但不主动生成任意有效值。原因是我们通常希望在开始探索不同的变量分配（搜索阶段）之前建立一个完整的约束网络（约束设置阶段）。

现在，约束求解器在某个变量域上带有许多预定义的约束（最广泛使用的是整数变量的约束）。但是您想约束一个变量以从列表域中获取值。您没有现成的实现，因此您可能想要编写自己的实现。CLP 系统在支持您定义自己的约束方面有所不同。在以下示例中，我使用ECLiPSe的延迟子句功能，因为这可能是最易读的（免责声明：我个人参与了 ECLiPSe）。

这是一个简单的长度约束。请注意如果任一参数未实例化，则导致谓词等待的“延迟子句”：

delay c_len(Xs, N) if var(Xs) ; var(N).
c_len([], 0).
c_len([_|Xs], N) :-
        N1 is N-1,
        c_len(Xs, N1).

这可以确保一个变量只需要一个特定长度的列表：

?- c_len(Xs, 3), Xs = [_,_].
No (0.00s cpu)

?- c_len(Xs, 3), Xs = [_,_,_].
Xs = [_76, _78, _80]
Yes (0.00s cpu)

?- c_len(Xs, 3), Xs = [_,_,_,_].
No (0.00s cpu)

但是当没有足够的信息时，它会等待（如“延迟目标”消息所示）：

?- c_len(Xs, 3), Xs = [_,_|Tail].
Xs = [_64, _66|Tail]
There is 1 delayed goal.
Yes (0.00s cpu)

在最后一个示例中，我们看到，尽管约束是正确的（从某种意义上说，它不允许对其参数进行无效实例化），但它实际上可以更聪明一点，并推断出它Tail必须是长度为 1 的列表。这是相当典型：约束的操作行为（通常称为其传播强度）可能因实现而异。通常它反映了传播强度和计算复杂性之间的权衡。

这是一个更好的实现。它利用了有限域变量，还实现了约束列表元素域的要求：

:- use_module(library(ic)).    % provides finite domain solver

delay bounded_list(Xs,_Lo,_Hi,Len) if var(Xs), var(Len).
bounded_list([],_Lo,_Hi, 0).
bounded_list([X|Xs], Lo, Hi, Len) :-
        Len #> 0,
        Lo #=< X, X #=< Hi,
        Len1 #= Len-1,
        bounded_list(Xs, Lo, Hi, Len1).

这可以强制执行您想要的列表属性（此处长度为 1 到 3，值介于 1 到 5 之间）：

?- N #:: 1..3, bounded_list(Xs,1,5,N), Xs = [1,2,3].
N = 3
Xs = [1, 2, 3]
Yes (0.00s cpu)

?- N #:: 1..3, bounded_list(Xs,1,5,N), Xs = [1,2,3,4].
No (0.00s cpu)

?- N #:: 1..3, bounded_list(Xs,1,5,N), Xs = [1].
N = 1
Xs = [1]

?- N #:: 1..3, bounded_list(Xs,1,5,N), Xs = [1,9].
No (0.00s cpu)

它还进行了一些早期推断，例如创建具有适当整数域的列表元素：

?- bounded_list(Xs, 1, 5, 3).
Xs = [_319{1..5}, _472{1..5}, _625{1..5}]
Yes (0.00s cpu, ...)
于 2018-02-17T02:02:45.850 回答
1

As per lurker this seem to be a solution of a List with 1 up-to 3 elements of non repeatable numbers in the range of 1 .. 5 :

 ?- L=[4,1,Z], X in 1..3, length(L, X), L ins 1..5, all_distinct(L).
 L = [4, 1, Z],
 X = 3,
 Z in 2..3\/5,
 all_distinct([4, 1, Z]).

 ?- L=[4,1,1], X in 1..3, length(L, X), L ins 1..5, all_distinct(L).
 false.

 ?- L=[4,1,2], X in 1..3, length(L, X), L ins 1..5, all_distinct(L).
 L = [4, 1, 2],
 X = 3.

 ?- Lst=[3,1,5], Length in 1..3, length(Lst, Length), Lst ins 1..5, all_distinct(Lst).
 Lst = [3, 1, 5],
 Length = 3.
于 2018-02-15T21:12:38.080 回答
0

这段代码没有意义，实际上并没有使用 clpfd。

?- L=[4,5], X in 1..3, length(L, X), L ins 1..5.

L = [4, 5],
X = 2.

删除X in 1..3and后L ins 1..5，它的工作原理相同。

?- L=[4,5],length(L,X).

L = [4, 5],
X = 2.
于 2018-02-16T01:37:38.227 回答