4 
ar([],[]).
ar([p(_,_)|L],L1):-ar(L,L2),L1=L2.
ar([p(X,Y)|L],L1):-ar(L,L2),L1=[p(X,Y)|L2].

（pは点を表し、座標XとYを持ちます）

結果がどのように構築されているか、特にL1が新しい値を取得する部分を理解するのを手伝ってください、ありがとう！

4

2 に答える 2

2

述語の定義は、 powerset関数ar/2のように動作し、次の構文の変形です (は の用語に制限されています)。Xp/2

% clause 1: base case
ps([], []).

% clause 2: omit the element X
ps([_X|Y], Z) :-
    ps(Y, Z). 

% clause 3: keep the element X
ps([X|Y], [X|Z]) :-
    ps(Y, Z).

述語ps/2(およびあなたのar/2) は基本的にバックトラックして、最初の引数のリストのすべてのサブリストを 2 番目の引数のサブリストにバインドします。これは、2 番目と 3 番目の節で表される選択によって実現されます。つまり、新しいリストを作成するときに、リスト要素を省略するか保持します。

ゴールを実行するときに Prolog が何をするかを考えてみましょうps([a,b],L):

  • ps([_|[b]], Z) :- ps([b], Z).(句 2 を介して、 drop a)。
    • ps([b|[]], Z) :- ps([], Z).(節 2 により、 drop ; =bであることに注意してください)。 [b][b|[]]
      • ps([], Z)バインドしZ = []ます（節1を介して、ソリューション1を提供します）。
    • ps([b|[]], [b|Z]) :- ps([], Z).（節3を介して、保持b）。
      • ps([], Z)バインドしZ = []ます（節1を介して、ソリューション2を提供します）。
  • ps([_|[b]], [a|Z]) :- ps([b], Z).（節3を介して、保持a）。
    • ps([b|[]], Z) :- ps([], Z).(句 2 を介して、 drop b)。
      • ps([], Z)バインドしZ = []ます（節1を介して、ソリューション3を提供します）。
    • ps([b|[]], [b|Z]) :- ps([], Z).（節3を介して、保持b）。
      • ps([], Z)バインドしZ = []ます（節1を介して、ソリューション4を提供します）。

節 1 の「基本ケース」に該当する最も深いレベルのそれぞれが、コール スタックを返します。これらの各ケースは、次の結果になります。

  1. aと の両方をドロップb:[]
  2. ドロップa、キープb:[b]
  3. キープa、ドロップb:[a]
  4. との両方aを保持b:[a,b]

したがって、バックトラックして[]、[b]、[a]および[a,b]、つまり の 4 つのサブリストを生成できます[a,b]。

于 2012-11-22T04:08:49.290 に答える
1

まず第一に、この手順は順列を計算するのではなく、一種のサブリストを計算することに注意してください: 「いくつかの」ポイントが削除されたリストで、「いくつかの」は一般的な形で表されます (解の 1 つは空のリストであり、また他の解決策は元のリストです)、入力リストが整形式であると仮定します。

入力リストが適切に形成されていない場合 (「ポイント」ではない項目が 1 つある場合)、手順は失敗します。

ar/2では、再帰的な手順であるの 3 つの句について説明します。

最初の節、

ar([], []).

最初の引数が空のリストの場合、2 番目の引数も入力リストであることを示します。つまり、空のリストの場合、手順の規則に準拠する唯一の「サブリスト」も空のリストです。これは、再帰的手続きの基本ケースでもあります。

第二節、

ar([p(_,_)|L], L1):-ar(L, L2), L1=L2.

L2最終的には と統合されるため、変数を使用せずに書き換えることができますL1。

ar([p(_,_)|L], L1):-ar(L, L1).

この句は、入力リストの先頭をスキップして再帰を続けています。再帰が戻ると、結果のリスト ( ar/2call の 2 番目の引数) が句の先頭の 2 番目の引数と統合されます。

第三節、

ar([p(X,Y)|L], L1):-ar(L, L2), L1=[p(X,Y)|L2].

L2繰り返しますが、変数を使用せずに、結果のリストを節の先頭に作成することで書き直すことができます。

ar([p(X,Y)|L], [p(X,Y)|L1]):-ar(L,L1).

この句は、入力リストの先頭を取得し、末尾で再帰を続行し、句の先頭の 2 番目の引数を取得した項目と再帰の結果のリストに統合します。つまり、再帰の結果とともに、入力リストの項目 (先頭) が保持されます。

また、このプロシージャは元に戻せないことに注意してください。最初の引数がインスタンス化されておらず、2 番目の引数がインスタンス化されている状態で呼び出された場合、永久にループします。

于 2012-11-21T23:44:46.010 に答える