0

リストのリスト内のある要素から別の要素への遷移に関する関係を表現しようとしています。私ができるようにしたいのは、2 つの任意の要素の間に特定の違いが存在する必要があるということです。

リストがあれば 

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

ここで、すべての要素は長さ Y のリストです。

ここで、Xa のすべての要素が 1 を除いて等しいかそれ以下であり、Xa と Xb が X の任意の要素 (a!=b) である Xa->Xb との違いがあることを表現したいと思います。

例: Xa=[1,1,1,1] の場合、Xb は [1,1,1,2] になる可能性があります。これは、すべての要素が等しいか、1 を除いて減少するためです。最後の要素は 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

あなたのコードがあなたが考えていることを表現していないのではないかと疑うことが 1 つあります。あなたはこう言います：「Xa->Xb とは違い、Xa のすべての要素が 1 以下であり、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_different/1 ではなく all_distinct/1 をお勧めします。

于 2014-01-14T10:03:56.453 に答える