4

私は次のコードを持っています:

neighbor(C1, C2, [C1, C2|L]).
neighbor(C1, C2, [C2, C1|L]).
neighbor(C1, C2, [H|L]) :- neighbor(C1, C2, L).

not_neighbors(C5, C2, E, R) :-
    not_neighbor(C5, C2, E).

not_neighbors(C5, C2, E, R) :-
    not_neighbor(C5, C2, R).

/* THIS DON'T WORK */
not_neighbor(C5, C2, E) :-
    \+ neighbor(C5, C2, E).

または ：

same_position(I, J, [I|U], [J|V]).
same_position(I, J, [M|U], [N|V]) :-
    I \== M,   % optimisation
    J \== N,   % optimisation
    same_position(I, J, U, V).

/* THIS DON'T WORK */
not_under(C4, C1, R, E) :-
    \+ same_position(C4, C1, R, E).

私は問題が否定であることを知っており、same_positionたとえば反対の結果を得たいと思っています。

M. @CapelliC は私に使用を提案しましたdif/2が、これを私の特定の例に適用する方法がわかりません。

4

2 に答える 2

3

最初に、リストの「隣人」であるとはどういう意味かを論理的に考えてみましょう: リスト内のAと Bの隣接要素はどのような場合でしょうか?

回答: リストが次の形式[...,X,Y,...]で、少なくとも次のいずれかが成り立つ場合:

  • A = X と B = Y
  • A = Y と B = X。

論理的には: ( A = X∧ B = Y) ∨ ( A = Y∧ B = X)。

これの反対を述べたいと思います。これは否定された式です。

   ¬ ( ( A = X∧ B = Y) ∨ ( A = Y∧ B = X) ) ≡

≡ ¬ ( A = X∧ B = Y) ∧ ¬ ( A = Y∧ B = X) ≡

≡ (¬ A = X∨ ¬ B = Y) ∧ (¬ A = Y∨ ¬ B = X) ≡

≡ ( A≠ X∨ B≠ Y) ∧ ( A≠ Y∨ B≠ X)

ド・モルガンの法則が実際に適用されると誰が考えたでしょうか?

Prolog でX≠を述べるには、@CapelliC が既に提案したように、強力な制約を使用します。その引数が異なる用語である場合、真です。これは純粋な述語であり、すべての方向で正しく機能します。Prolog システムでまだ提供されていない場合は、ベンダーに必要であることを知らせてください。それまでは、必要に応じて で概算できます。Ydif/2dif/2iso_dif/2

したがって、Prolog では、上記は次のようになります。

( dif(A, X) ; dif(B, Y) ), ( dif(A, Y) ; dif(B, X) )

なぜなら(',')/2は連言を(;)/2表し、選言を表します。

したがって、次のようになります。

not_neighbours(_, _, [])。
not_neighbours(_, _, [_])。
not_neighbours(A, B, [X,Y|残り]) :-
        ( dif(A, X) ; dif(B, Y) ),
        ( dif(A, Y) ; dif(B, X) ),
        not_neighbours(A, B, [Y|Rest])。

いくつかのテスト ケースにより、述語の正確性についてより確信が持てるようになりました。

?- not_neighbours(a, b, [a,b])。
間違い。

?- not_neighbours(A, B, [A,B])。
間違い。

?- not_neighbours(A, B, [_,A,B|_])。
間違い。

?- not_neighbours(A, B, [_,B,A|_])。
間違い。

?- not_neighbours(a, b, [_,a,c,_])。
真実 。

この定義は、すべての引数が変数である場合にも正しく機能することに注意してください。これを最も一般的なケースと呼びます。

このソリューションの欠点は、(;)/2多くの代替案が作成されることであり、それらの多くはまったく問題になりません。不要な代替を取り除くことができる別の代数的等価性によって、これを大幅に効率化できます。

¬ A ∨ B ≡ A → B

したがって、私たちの場合、 (¬ A = X∨ ¬ B = Y) はA = X → B≠と書くことができますY。

Prolog では、強力なメタ述語を使用して含意を表現できます。if_/3

impl(A, B) :- if_(A, B, true).

したがって、宣言的に同等にソリューションを次のように書くことができます。

not_neighbours(_, _, [])。
not_neighbours(_, _, [_])。
not_neighbours(A, B, [X,Y|残り]) :-
        impl(A=X, dif(B, Y)),
        impl(B=X, dif(A, Y)),
        not_neighbours(A, B, [Y|Rest])。

サンプルクエリ:

?- not_neighbours(a, b, [x,y])。
真;
間違い。

そして、より一般的なケース:

?- not_neighbours(a, b, [X,Y])。
X = a、
dif(Y, b) ;
X = b、
dif(Y, a) ;
差分 (X, b),
差分 (X, a) ;
間違い。

この述語を使用して、回答の確認と生成を行うことができます。たとえば、反復的な深化を試して、すべての回答を公平に列挙します。

?- length(Ls, _), not_neighbours(A, B, Ls).

驚くべきことに、純粋な論理的推論により、一般的で効率的な Prolog プログラムにたどり着きました。

dif/2これは最初の Prolog システムに登場し、しばらくの間一部のベンダーによって無視されていたためです。最近でdif/2は、2 つの用語が異なることを宣言的に述べることができる重要な組み込み述語として、ますます多くの実装で (再び) 利用できるようになっています。その不純な代替物が通常 Prolog コースで引き起こす大規模な混乱は、 で回避できますdif/2。

于 2016-09-05T21:08:37.270 に答える
1

隣接していないものを生成したい場合\+は、定義上セミデットのままでは実行されず、変数をバインドすることはありません。答えを組み立てる何かが必要です。1 つのオプションは、すべてのペアを生成してから、 your を使用して\+ neighbor(...)隣接しないものをフィルタリングすることです。直接構成的なアプローチもそれほど難しくありませんが、両方の順序付けが必要なため、コードが少し複雑になります。

not_neighbor(C1, C2, List) :-
    append(_, [C10,_|Postfix], List),
    member(C20, Postfix),
    swap(C1,C2, C10,C20).

swap(X,Y, X,Y).
swap(X,Y, Y,X).

http://swish.swi-prolog.org/p/njssKnba.plを参照してください。

于 2016-09-05T21:03:52.797 に答える