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)

制約を表現するには、 s(A1 #/\ A2 #/\ ... #/\ AN) => AN+1を具体化できるはずだと思うので、次のようにします。Ai

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

次に、s を収集Bし、接続詞が有効であることを確認するには、次のようにします。

(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かですが、上記のクエリはvsまたはvsなど1のソリューションも返す必要があります。[0,1,0][0,1,0][0,0,0][0,1,0]

それで、私の推論に何か問題がありますか、それとも上記の定義にバグがありますか?

4

2 に答える 2

2

の最初の句では、 2 つの異なる目的でmakeAndConstr/6を使用しているため、余分な障害が発生します ( についても同じです)。この名前が変更されたコードは次のように機能します。XY

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であると観察することによって説明されます

  • どちらか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への呼び出しごとに新しい を作成したことです。これがバグを回避するのにどのように役立つかはよくわかりませんが。それは単により効率的であるべきです。makeAndConstrB

于 2015-10-21T13:41:52.667 に答える