7

次のプログラムを想定します。

nat(0).
nat(s(N)) :- nat(N).

/* 0+b=b */
plus(0,B,B) :- nat(B).
/* (a+1)+b = c iff a+(b+1)=c */
plus(s(A),B,C) :- plus(A,s(B),C).

2 つの数値を加算する場合はうまく機能しますが、次のようなクエリを実行しようとすると、次のようになります。 

plus(Z,Z,s(0)).

Z解決策がないことが明らかになった後も、可能な値を検索し続けます（つまり、 Z>s(0)）

私は cut( !) 演算子に精通しており、私の直感では解決策がそれと関係があると言っていますが、この場合の使用方法がわかりません。

4

3 に答える 3

4

!/0このような問題に対しては、一貫して良い解決策ではありません。通常、より一般的なクエリの有効なソリューションが失われます。

代わりに、この場合は完全に機能する有限領域制約の使用を検討してください。

?- use_module(library(clpfd)).
true.

?- Z + Z #= 0.
Z = 0.

?- Z + Z #= 0, Z #> 0.
false.

編集: 要求に応じて、CLP(FD) なしで可能な解決策:

plus(0, Y, Y).
plus(s(X), Y, s(Z)) :- plus(X, Y, Z).
于 2014-03-23T22:38:15.937 に答える
3

したがって、ここでの目的は、特定のプログラムの正確な終了プロパティを理解することです。Prolog は、比較的複雑な実行メカニズムを備えているため、他のプログラミング言語とは大きく異なります。特に、バックトラッキングは「通常の解像度」と非常に絡み合っており、統合と組み合わされています。

元のプログラムの問題を理解する最も簡単な方法は、次の障害スライスを検討することです (他の例についてはリンクを参照してください)。

plus(0,B,B) :- false , nat(B) .
plus(s(A),B,C) :- plus(A,s(B),C), false .

この小さなプログラムが終了しない場合、元のプログラムも終了しません。したがって、最初に、このプログラムがいつ終了しないかという問題を考えることができます。

C3 番目の引数を考えてみましょう。単に渡される変数があります。その値 (このフラグメント) には誰も興味がありません。したがって、3 番目の引数は終了にはまったく影響しません。

さらに悪いことに、2 番目の引数もヘッド内の自由変数Bにすぎないため、このフラグメントが終了するかどうかに引数が影響することはありません。

したがって、このフラグメントを終了させたい場合は、最初の引数を知る必要があります。そうしないと、プログラムがループします。終了インファーサーを使用して、この降伏を終了条件として確認することもできます。

plus(A,B,C)terminates_if b(A),b(B);b(A),b(C).

最良の方法は、プログラムを再構成することです。次の終了条件を提供します。

plus(A,B,C)terminates_if b(A),b(B);b(C).

Prolog では、通常、プログラムをさらに一般化して、予期しない解決策を受け入れながら、終了条件をより良い状態に改善することを好みます。

plus(A,B,C)terminates_if b(A);b(C).

ただし、この最後のバージョンでは、常に受け入れられるとは限らないソリューションが認められています。たとえばplus(0, nonnumber, nonnumnber)、今は成功していますが、失敗したい場合があります。

もちろん、カットを使っていくつかの実験を行うこともできますが、カットを使用すると非常にエラーが発生しやすいことに注意してください。少なくとも、「効率の向上」を妨げることが多い適切なテストと組み合わせる必要があります。

于 2014-03-23T23:39:11.833 に答える
1

間違った方法でアプローチしていることに気付きました。必要なのは cut( )ではなく、0になるまで「分解」!する別のルール セットです。ありえない値を与える:XYZXYZ

plus(0,0,0).
plus(s(A),B,s(C)) :- plus(A,B,C).
plus(0,s(B),s(C)) :- plus(0,B,C).
于 2014-03-23T23:08:32.603 に答える