CLPFD ins 运算符产生未充分实例化的错误

Question

所以，我的目标是在 Prolog 中制作地图着色器。这是我正在使用的地图：

这是我的着色限制：

colouring([A,B,C,D,E,F]) :- 
    maplist( #\=(A), [B,C,D,E] ),
    maplist( #\=(B), [C,D,F]),
    C #\= D,
    maplist( #\=(D), [E,F]),
    E #\= F.

其中 [A,B,C,D,E,F] 是从 1 到 n 的数字（颜色）列表。

所以我希望我的求解器能够在给定 6 种颜色的列表和一个自然数 N 的情况下，以一种即使是最一般的查询也能产生结果的方式来确定颜色和 N 个约束：

regions_ncolors(L,N) :- colouring(L), L ins 1..N, label(L).

最常见的查询是 regions_ncolors(L,N).

然而，运算符 ins 似乎不接受变量 N，而是产生一个参数未充分实例化的错误。我尝试改用此解决方案：

int_cset_(N,Acc,Acc) :- N #= 0.
int_cset_(N,Acc,Cs) :- N_1 #= N-1, int_cset_(N_1,[N|Acc],Cs).
int_cset(N,Cs) :- int_cset_(N,[],Cs).

% most general solver
regions_ncolors(L,N) :- colouring(L), int_cset(N,Cs), subset(L,Cs), label(L).

其中int_cset(N,Cs)中的参数为自然数(N)，计数集Sn = {1,2,...,N}

但是这个解决方案有问题，因为 regions_ncolors(L,N). 只有 returns 所有 N 的相同（一个）解决方案，当我尝试向 N 添加约束时，它进入无限循环。

那么我该怎么做才能使最一般的查询双向工作（对于未实例化的变量）？

提前致谢！

顺便说一句，我在上一个 post 中添加了一个 swi-prolog 标签，尽管它已被审核删除。我不知道这个问题是否特定于 swi-prolog，这就是我保留标签的原因，以防万一:)

Answer 1

您的 colouring 太具体了，您将地图的拓扑结构编码到其中。这不是问题，但它违背了为任何列表提供“最通用查询”解决方案的目的。

如果你想避免使用自由变量而不是列表的问题，你可以先用 length/2 实例化列表。比较：

?- L ins 1..3.
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:   [16] throw(error(instantiation_error,_86828))
ERROR:   [10] clpfd:(_86858 ins 1..3) ...

这和你看到的是同一个问题吗？

如果先做一个列表和对应的集合：

?- length(L, N), L ins 1..N.
L = [],
N = 0 ;
L = [1],
N = 1 ;
L = [_A, _B],
N = 2,
_A in 1..2,
_B in 1..2 ;
L = [_A, _B, _C],
N = 3,
_A in 1..3,
_B in 1..3,
_C in 1..3 .

如果您像这样使用 length/2，您将完全在 CLP(FD) 标签之外枚举可能的列表和整数集。然后，您可以对列表中的变量添加更多约束，如有必要，使用标签。

这是否有助于您进一步解决问题？我不确定它如何帮助解决着色问题。您将需要地图拓扑的不同表示，这样您就不必像您在问题中遇到的 colouring/1 那样在谓词中手动定义它。

Answer 2

你的程序有几个问题。

subset/2不纯

SWI 的（默认）内置谓词 subset/2 不是您希望的纯关系。相反，它期望两个参数都已经充分实例化。如果没有，它需要猜测并坚持下去：

?-            colouring(L), subset(L,[1,2,3,4,5]).
L = [1,2,3,4,2,1].

?-            colouring(L), subset(L,[1,2,3,4,5]), L = [2|_].
false.

?- L = [2|_], colouring(L), subset(L,[1,2,3,4,5]), L = [2|_].
L = [2,1,3,4,1,2].

使用纯粹的定义，在第三个查询中添加另一个目标 L = [2|_] 是不可能使失败的查询成功的。

一般来说，除了变量的顺序和选项参数之外，不要干扰 labeling/2 是个好主意。内部实现通常比手动实例化快得多。

此外，您的地图太简单了，无法暴露 subset/2 的弱点。不确定最小失败图是什么，但这是

中的一个这样的例子

R. Janczewski et al. The smallest hard-to-color graph for algorithm DSATUR, Discrete Mathematics 236 (2001) p.164.

colouring_m13([K1,K2,K3,K6,K5,K7,K4]):-
    maplist(#\=(K1), [K2,K3,K4,K7]),
    maplist(#\=(K2), [K3,K5,K6]),
    maplist(#\=(K3), [K4,K5]),
    maplist(#\=(K4), [K5,K7]),
    maplist(#\=(K5), [K6,K7]),
    maplist(#\=(K6), [K7]).

?-            colouring_m13(L), subset(L,[1,2,3,4]).
false.                   % incomplete

?- L = [3|_], colouring_m13(L), subset(L,[1,2,3,4]).
L = [3,1,2,2,3,1,4].

int_cset/2 永不终止

...（某些错误情况除外，例如 int_cset(non_integer, _).）。例如考虑：

?- int_cset(1,Cs).
   Cs = [1]
;  *LOOPS*

并且不要被找到实际解决方案的事实所愚弄！它仍然没有终止。

@Luis: But how come? I'm getting baffled by this, the same thing is happening on ...

要看到这一点，您需要 failure-slice 的概念，它有助于识别程序中的负责部分。一些由目标组成的假动作false暴露了责任部分。

false删除了所有不必要的部分。剩下的必须以某种方式更改。

int_cset_(N,Acc,Acc) :- false, N #= 0.
int_cset_(N,Acc,Cs) :- N1 #= N-1, int_cset_(N1,[N|Acc],Cs), false.

int_cset(N,Cs) :- int_cset_(N,[],Cs), false.

?- int_cset(1, Cs), false.
% loops

添加冗余目标N1 #> 0 将避免不必要的非终止。

仅此并不能解决您的问题，因为如果未给出 N，由于以下故障片段，您仍然会遇到无法终止的情况：

regions_ncolors(L,N) :-
   colouring(L),
   int_cset(N,Cs), false,
   subset(L,Cs),
   label(L).

在int_cset(N,Cs)中，Cs第一次出现，因此不会影响终止（还有一个原因，它的定义也会忽略它..）因此只有N 有机会导致终止。

@TA_intern 已经使用 length/2 建议了实际的解决方案，它解放了其中一项受模式困扰的琐事。

CLPFD ins 运算符产生未充分实例化的错误

CLPFD ins operator yields not sufficiently instantiated error

prolog

clpfd

subset/2不纯

int_cset/2 永不终止