0

我试图表达从列表列表中的一个元素到另一个元素的转换关系。我想做的，就是说两个任意元素之间应该存在一定的差异。

如果我们有清单 

X=[X1,X2,X3,...Xn]

其中所有元素都是长度为 Y 的列表。

我现在想表达应该与 Xa->Xb 有所不同，其中 Xa 中的所有元素都等于或小于但一个，并且 Xa 和 Xb 是 X 的任何给定元素（a！= b）

例如：如果 Xa=[1,1,1,1] 那么 Xb 可能是 [1,1,1,2]，因为所有元素都相等或减少，除了最后一个，它从 1->2 开始。

我写了以下谓词来做到这一点：

ensure_atleast_n_patterns( ListOfLists, DiffPattern, NoOfAtLeastEqualPatterns ) :-
    ( 
    %Loop through the list to set up the constraint between first
    %element and the rest, move on to next element and and set
    %up constraint from second element on on etc.
    %Ex: if ListOfLists=[X1,X2,X3,X4], the following 'loops' will run:
    %X1-X2, X1-X3,X1-4,X2-X3,X2-X4,X3,X4
    fromto(ListOfLists, [This | Rest], Rest,[_]),
    fromto(0,In1,Out1,PatternCount),
    param([DiffPattern])
    do
        (
            %Compare the difference between two elements:
            foreach( X, Rest ),
            fromto(0,In2,Out2,Sum2),
            param([DiffPattern,This])
            do
                This=[X1,X2,X3,X4,X5],
                X=[Y1,Y2,Y3,Y4,Y5],
                DiffPattern=[P1,P2,P3,P4,P5],
                X1 #< Y1 #<=> R1,
                X2 #< Y2 #<=> R2,
                X3 #< Y3 #<=> R3,
                X4 #< Y4 #<=> R4,
                X5 #< Y5 #<=> R5,
                Result in 0..1,
                (R1 #= P1) #/\ (R2 #= P2) #/\ (R3 #= P3) #/\ (R4 #= P4) #/\ (R5 #= P5) #<=> (Result #=1),
                Out2 #= In2 + Result
        ),
        Out1 #= In1 + Sum2
    ),
    %Count up, and require that this pattern should at least be present
    %NoOfAtLeastEqualPatterns times
    PatternCount #>= NoOfAtLeastEqualPatterns.

这接缝工作正常。如果我也尝试在行上使用 all_different()，我的问题就会出现。例如：我想一个解决方案可能是：

 0,0,0,0,0
 2,2,2,2,1
 1,1,1,1,2
 4,4,4,3,4
 3,3,3,4,3
 etc...

但标签“永远”挂起

我的方法错了吗？有没有更好的方法来解决这个问题？

测试代码：

  mytest( X ):-
   Tlen = 10,
   Mind = 0,
   Maxd = 20,
   length( X1,Tlen),
   length( X2,Tlen),
   length( X3,Tlen),
   length( X4,Tlen),
   length( X5,Tlen),
   domain(X1, Mind, Maxd),
   domain(X2, Mind, Maxd),
   domain(X3, Mind, Maxd),
   domain(X4, Mind, Maxd),
   domain(X5, Mind, Maxd),

   all_different( X1 ),
   all_different( X2 ),
   all_different( X3 ),
   all_different( X4 ),
   all_different( X5 ),

   X=[X1,X2,X3,X4,X5],

   transpose( X, XT ),

   ensure_atleast_n_patterns( XT, [0,0,0,0,1],1),
   ensure_atleast_n_patterns( XT, [0,0,0,1,0],1),
   ensure_atleast_n_patterns( XT, [0,0,1,0,0],1),
   ensure_atleast_n_patterns( XT, [0,1,0,0,0],1),
   ensure_atleast_n_patterns( XT, [1,0,0,0,0],1).

我像这样运行它：

mytest(X),append(X, X_1), labeling( [], X_1 ).
4

1 回答 1

4

有一件事让我怀疑你的代码没有表达你的想法。你说：“我现在想表达应该与 Xa->Xb 有所不同，其中 Xa 中的所有元素都等于或小于一个，并且 Xa 和 Xb 是 X 的任何给定元素 (a!=b)”。但是在您的代码中，您不会考虑所有元素对。您只考虑 Xb 位于 Xa 右侧某处的对（Xb 是 Rest 的元素）。这种不对称性可能使找到解决方案变得困难。

不过，这里有一个 Tlen = Maxd = 5 的解决方案：

| ?- mytest([[0,3,4,1,2],[1,2,4,0,3],[1,4,2,0,3],[3,1,4,2,0],[3,4,1,2,0]]).
yes

但由于不对称，以下失败：

| ?- mytest([[0,1,2,3,4],[1,0,3,2,4],[1,0,3,4,2],[3,2,0,1,4],[3,2,0,4,1]]).
no

如果您修复您的代码以便它考虑所有对 (Xa,Xb)，那么从任何解决方案中，您都可以通过置换 ListOfLists 的元素（XT 的行）来获得另一个解决方案。通过打破这种解决方案的对称性来减少搜索空间通常是一个好主意。你可以这样做：

lex_chain(XT),

顺便说一句，我推荐 all_distinct/1 而不是 all_different/1。

于 2014-01-14T10:03:56.453 回答