1

我正在尝试使用其 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或类似的东西，因此所有变量都是0or 1，而上面的查询也应该返回类似[0,1,0]vs[0,1,0]或[0,0,0]vs的解决方案[0,1,0]。

那么，我的推理有问题还是上述定义中有错误？

4

2 回答 2

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).

这可以通过观察 that IsLeis 1 if来解释

  • 要么X<Y（和值RestIsLe无关紧要）
  • 或X=Y为RestIsLe1。
于 2015-10-23T03:18:54.447 回答
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([], [], _).

这也比上面的简单得多。

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

于 2015-10-21T13:41:52.667 回答