-1

私は SWI Prolog を使用して大学の試験のために Prolog を勉強していますが、次の問題の 2 つの異なるソリューションの違いについて疑問があります。

Xはアトム、L はリスト、 NumXは X が L に現れる回数です。

これが最初の解決策です：

count0(_,[],0).

count0(A, [A|Tail], N) :-
            count0(A,Tail,N1), % L'elemento cercato appare N1 volte nella sottolista
                N is N1+1.     % N vale N1+1

count0(A, [B|Tail], N) :-
            A\=B,            % A è diverso da B
        count0(A,Tail,N). % N è il numero di occorrenze di A nella sottolista

これが 2 番目の解決策です。

count1(_,[],0).

count1(A, [A|Tail], N) :- !,
                      count1(A, Tail, N1),
              N is N1+1.

count1(A, [_|Tail], N) :- count1(A, Tail, N).

私の問題は、2 番目のバージョンで CUT が果たす役割を理解していないことです。

CUT は、CUT が配置されている特定のポイントでバックトラックを防止することを知っています。

プログラムの最初のバージョンは、A が 2 番目のルールで B と異なるかどうかをチェックします (これが必要ですか? 最初のルールが失敗した場合は、A がリストの HEAD と統合されないため、ヘッドのリストAの要素とは異なります）

2 番目のバージョンは、2 番目のルールでこのチェックを実行せず、最初のルールにカットを入れます...

それは、(2 番目のバージョンで) バックトラッキングを防止しないと、次のことが起こるという事実に依存する可能性があります。2番目のルールを使用することが起こります:

count1(A, [_|Tail], N) :- count1(A, Tail, N).

計算で別の分岐を取り、その分岐では N がありません N+1 ですか?

4

1 に答える 1

1

最初のバージョンは 2 番目の句に選択ポイントを残しますが、2 番目のバージョンは 2 番目の句に入るとその句にコミットします (カット付き)。

最初のバージョンでは、アイテムがリストの先頭と異なることを明示的にチェックする必要があります。これは、バックトラック時に、2 番目の句が以前に成功したかどうかに関係なく、3 番目の句が実行されるためです。

たとえば 1 つの要素の単純な入力リストを使用して両方の手順をトレースすると、自分で確認できます。

?- count0(a,[a], Count).

あなたのプログラムの最初のバージョンは、項目とリストの先頭を照合し、再帰を実行します。ただし、必要に応じて他の選択肢を表示するための選択ポイントが残ります。次に、基本ケース (空のリスト) により再帰が終了し、 Count=1の結果が得られます。

ここでプロローグに他の選択肢を要求すると、まだその選択ポイントがあるため、thirc 句を試します。A と B が異なることを明示的に確認しないと、再帰的に (再び空のリストで) 自分自身を呼び出し、間違った答えであるCount=0を返します!

次に、プログラムの 2 番目のバージョン (カットを使用するバージョン) です。プロローグが項目 a で 2 節目に入ると、カットとコミットするので、選択点を残しません。これで、再帰を実行し、正しい結果のCount=1で終了します。

ここで prolog に他の選択肢を求めると、チェックするものが残っていないと言われます。カットの結果、A と B が異なることを確認する必要はなくなりました。そうでなければ、2 番目の節がコミットされ、3 番目の節がテストされないため、それらが異なることは確実だからです。

于 2013-04-10T16:00:20.237 に答える