2

プロローグ述語があります：

Add( [A|B] , Answer ) :-
    ...
    ~ Add everything in the list to come up with answer
    ...

変数を2回指定した場合を 除いAddUniqueて、リスト内のすべてに対して一意の値を返すように実装したいと思います。

論理的に同等のものは次のとおりです。

?- AddUnique([A, B, C], 10).次と同等です。?- Add([A, B, C], 10), A != B, B != C, A != C.

と：

?- AddUnique([A, B, B], 10).次と同等です。?- Add([A, B, B], 10), A != B.

また：

?- AddUnique([A, B, B], 10).以下と同等ではありません:?- Add([A, B, B], 10), A != B, B!=B.

が与えられた場合?- AddUnique([A,B,C,D], 4).、4 になる一意の正の整数を指定できないため、false を返す必要があります。

?- AddUnique([A,A,A,A], 4).が与えられた場合、 を返す必要がありA=1ます。

質問A != B, B != C, A != C.:このようなことをせずにロジックを述語内に移動するにはどうすればよいA != Aですか?

4

3 に答える 3

1

述語の説明が addUnique/2あれば、制約ロジック プログラミングを使用してソリューションを実装できます。これは初心者向けとはほど遠いですが、とにかく説明を投稿します。

まず、制約論理プログラミングとは何か、および実装の使用方法 (例: SWI-PL clpfd ) を調べることは価値があるかもしれません。基本的に、制約ロジック プログラミング (特に有限領域ソルバー) では、入力リストの変数に対して次の制約を指定できますaddUnique/2。

  1. 入力リストの変数を特定の数値 (つまり、0 から指定された値までの整数) にバインドする方法
  2. 入力リストの異なる変数が同時に同じ値にバインドできない方法 (つまり、!= どこが異なるか)
  3. 入力リスト内の変数と任意の数値の合計が、指定された値 (つまり、上記の 1 で変数が取り得る最大値) になる方法。

これらの仕様を一緒に使用すると、基礎となる制約ソルバーは、上記の制約が与えられたときに変数が同時に取ることができる許容値を自動的に決定し、ソリューションを提供できます (複数、1 つ、またはまったくない場合もあります)。

SWI-PROLOG で前述の制約ソルバー (clpfd ソルバー) を使用したソリューションを次に示します。

:- use_module(library(clpfd)).  % import and use the constraint solver library

addUnique([A|As], Val) :-
    unique_vars([A|As], UVs),  % determine all unique variables
    UVs ins 0..Val,            % (1) domain of all unique variables is 0 to Val
    pairwise_inequ(UVs),       % (2) all unique variables are pairwise !=
    construct_sum_constr(As, Val, A, Program),  % (3) construct the sum constraint
    Program,              % assert the sum constraint
    label(UVs).           % label domains to enumerate a solution (backtracks)

% predicate to return a list of unique vars, if present
unique_vars([], []).
unique_vars([V|Vs], [V|Uniq]) :-
    var(V),
    \+ var_memberchk(V, Vs), !,
    unique_vars(Vs, Uniq).
unique_vars([_|Vs], Uniq) :-
    unique_vars(Vs, Uniq).

% predicate to test if a variable appears in a list (possibly including variables)
var_memberchk(V0, [V1|_]) :- 
    V0 == V1, !.
var_memberchk(V0, [_|V1s]) :- 
    var_memberchk(V0, V1s).

% create constraints that assert each in the input list != to each other
pairwise_inequ([]).
pairwise_inequ([V|Vs]) :-
    map_inequ(Vs, V),
    pairwise_inequ(Vs).

% predicate to pairwise assert inequality between all list members
map_inequ([], _).
map_inequ([V1|V1s], V0) :-
    V0 #\= V1,   % the inequality constraint
    map_inequ(V1s, V0).

% predicate to construct a summation constraint, whereby all variables in the 
% input list are constructed into a sum with +/2 and finally equated to a value
construct_sum_constr([], Val, Sum, (Sum #= Val)).
construct_sum_constr([V|Vs], Val, Sum, Program) :-
    construct_sum_constr(Vs, Val, (V + Sum), Program).

たとえば、このコードを実行すると、次のようになります。

?- addUnique([A,B,B], 6).
A = 0,
B = 3 ;
A = 4,
B = 1 ;
A = 6,
B = 0.

;変数間の許容されるバインディングの次のソリューションを列挙します。必要に応じて と が同じ値になることはAありませんが、入力リスト内のすべての出現箇所の合計は常に になることに注意してください。別のクエリ:B6

 ?- addUnique([A,A,A],4).
false.

Aここでは、合計すると totaledにバインドする単一の整数が見つからなかったため、結果は失敗です4。

 ?- addUnique([A,A,A,A],4).
A = 1.

...予想通り。また、あなたは試したかった：

?- addUnique([A,B,C,D],4).
false.

A繰り返しますが、すべての変数、B、CおよびDがすべて異なるとアサートされ、すべてを にバインドできないため、ここでも結果は失敗です1。

編集ps。また、試してみたかった:

?- addUnique([A,A,A,1],4).
A = 1.

上記のコードを簡単に変更すると、ドメインをアサートするために呼び出すときに変数のみが使用されるようinsになります (入力リスト内の数値は使用されません)。

于 2010-06-08T00:03:41.007 に答える
1

doStuff(A,B,C,D)ふむ……それと意味がわかるはずだdoStuff(A,A,B,B)。まず、到達可能な目標を作成する適切な値で値を統合しAます。And second はandと同じです(ただし、最後のバリアントはおそらくバックトラッキングを引き起こします)。制限外なので、 の中でやるべきではないことをご理解いただければ幸いです。したがって、 and を使用する必要があります。DdoStuff/4A=B, C=D, doStuff(A,B,C,D)doStuff(A,B,C,D), A=B, C=Dunique/1doStuff/4doStuff(A,B,C,D), unique([A,B,C,D])doStuff(A,A,B,B), unique([A,B])

どのように読んだのだろうか...とにかく、次のようにA is not B定義できますunique/1

not_unique([H|T]):- member(H, T) ; not_unique(T).
unique(L):- not(not_unique(L)).
于 2010-06-06T13:22:07.463 に答える
-1

これが私が思いついた解決策です。入力を 10 未満の数字にのみ割り当てますが、その場合はうまく機能します! 

addUnique( A, Answer ) :- 
    used(A,[0,1,2,3,4,5,6,7,8,9],_),
    add(A,Answer).

add( [A|B] , Answer ) :-
    ~ Add everything in the list to come up with answer ~.


% ================================
% Ensures that all variables are unique.  
% ================================

% Base case: Assigned variables unique values
used([], Nin, Nin).

% Have already assigned a value to this variable
used([A|B], Nin, Nout) :-
        integer(A),
        helper(B,Nin,Nout).

% Have not assigned a value to this variable yet
% Assign it and remove it from the list.  
used( [A|B] , Nin, Nout) :-
        member(A,Nin),
        delete(Nin,A,Temp),
        helper(B,Temp,Nout).
于 2010-06-08T18:54:17.273 に答える