使用约束按字典顺序排列两个变量列表

Question

我正在尝试使用 CLP(FD) 在 BProlog 中实现字典顺序约束。

据我所知，BProlog 手册没有提供内置的 lexLeq 约束（尽管存在针对此全局约束的有效传播算法），所以我正在尝试编写我的拥有并将顺序表示为以下二进制约束集：

X1 #=< Y1, (X1 #= Y1) #=> (X2 #=< Y2), (X1 #= Y1 #/\ X2 #= Y2) #=> (X3 #=< Y3), ..., (X1 #= Y1 #/\ ... #/\ XN #= YN) #=> (XN+1 #=< #YN+1)

为了表达 (A1 #/\ A2 #/\ ... #/\ AN) => AN+1 约束，我认为我应该能够具体化 Ais，所以：

domain(B, 0, 1),
(X1 #= Y1) #<=> B

然后我收集 Bs 并检查连词是否有效我只是这样做：

(sum(Bs) #= N) #=> AN+1

这个想法导致以下（可能非常难看）代码：

lexLeq(Xs, Ys) :-
    lexLeq(Xs, [], Ys, []).

lexLeq([X|Xs], [], [Y|Ys], []) :-
    X #=< Y,
    lexLeq(Xs, [X], Ys, [Y]).
lexLeq([X|Xs], [OldX|OldXs], [Y|Ys], [OldY|OldYs]) :-
    makeAndConstr([OldX|OldXs], [OldY|OldYs], X, Y),
    lexLeq(Xs, [X,OldX|OldXs], Ys, [Y, OldY|OldYs]).
lexLeq([], _, [], _).


makeAndConstr(Xs, Ys, X, Y) :-
    length(Xs, N),
    makeAndConstr(Xs, Ys, [], N, X, Y).

makeAndConstr([X|Xs], [Y|Ys], Bs, N, X, Y) :-
    domain(B, 0, 1),
    (X #= Y) #<=> B,
    makeAndConstr(Xs, Ys, [B|Bs], N, X, Y).
makeAndConstr([], [], Bs, N, X, Y) :-
    (sum(Bs) #= N) #=> (X #=< Y).

这部分有效：

| ?- domain([A,B,C,D,E,F], 0, 1), lexLeq([A,B,C], [D, E, F]), labeling([A,B,C,$
A = 0
B = 0
C = 0
D = 0
E = 0
F = 0 ?;
A = 0
B = 0
C = 0
D = 1
E = 1
F = 1 ?;
A = 1
B = 1
C = 1
D = 1
E = 1
F = 1 ?;
no

如您所见，生成的所有解决方案都满足约束条件。问题是并非所有有效的解决方案都产生了。似乎我描述的约束也以某种方式暗示 X1 #>= X2 #>= ... #>= XN 或类似的东西，因此所有变量都是 0 或 1，虽然上面的查询应该 return 也有解决方案，例如 [0,1,0] vs [0,1,0] 或 [0,0,0] vs [0,1,0].

所以，是我的推理有问题还是上面的定义有问题？

Answer 1

好的，我找到了一个可行的、看似可行的解决方案：

lexLeq([], []).
lexLeq([X|Xs], [Y|Ys]) :-
    X #=< Y,
    domain(B, 0, 1),
    (X #= Y) #<=> B,
    lexLeq(Xs, Ys, [B]).

lexLeq([X|Xs], [Y|Ys], Bs) :-
    length(Bs, N),
    (sum(Bs) #= N) #=> (X #=< Y),

    domain(B, 0, 1),
    (X #= Y) #<=> B,
    lexLeq(Xs, Ys, [B|Bs]).
lexLeq([], [], _).

这个也比上面简单多了。

不同之处在于，在第一个解决方案中，我为每次调用 makeAndConstr 创建了新的 B，而不是重复使用已创建的相同 B。虽然我不太确定这对避免错误有何帮助；它应该更有效。

Answer 2

在 makeAndConstr/6 的第一个子句中，您将 X 用于两个不同的目的，这会导致额外的失败（Y 也是如此）。此重命名的代码有效：

makeAndConstr([X1|Xs], [Y1|Ys], Bs, N, X, Y) :-
    domain(B, 0, 1),
    (X1 #= Y1) #<=> B,
    makeAndConstr(Xs, Ys, [B|Bs], N, X, Y).

您可以通过追踪一个您期望成功的简单目标找到它，例如lexLeq([0,1],[0,1]).

字典顺序约束的更简单表述

我想与您分享一个优雅的解决方案，这是我多年前从我的前同事 Warwick Harvey 那里学到的。它是这样的：

lex_le(Xs, Ys) :-
    lex_le(Xs, Ys, 1).

lex_le([], [], 1).
lex_le([X|Xs], [Y|Ys], IsLe) :-
    IsLe #<=> (X #< Y+RestIsLe),
    lex_le(Xs, Ys, RestIsLe).

这是通过观察 IsLe 是 1 if

来解释的

或者 X<Y（RestIsLe 的值无关紧要）
或X=Y并且RestIsLe是1。

使用约束按字典顺序排列两个变量列表

Lexicographically order two lists of variables using constraints

list

prolog

lexicographic

clpfd

b-prolog