9

次の述語があると仮定します（これはPrologでのプログラミングの例です）：

[F0] isInteger(0).
[F1] isInteger(X):- isInteger(Y), X is Y+1.

  1. クエリの最初の結果はInteger（R）で、マーカーはF0に配置され、R=0を返します。

  2. ユーザーが;を押した場合 、マーカーはF1に配置され、subgoal（isInteger（Y）、F0で満たされます）およびR=1に移動します。

私は上記を理解しています。ここに私の質問があります：

  1. ユーザーが;を押した場合 繰り返しますが、マーカーはどこにありますか？検索はどのように進んでR=2を返しますか？本の78-79ページの画像を理解しようとしましたが、はっきりしていません。私が見つけたオンラインチュートリアルは、再帰が存在する場合のバックトラックを処理しません。

再帰が存在する場合のバックトラックを説明するチュートリアルを探しています。うまくいけば、理解に役立つスタックコンテンツの画像を使用します。

よろしくお願いしますスザンヌ

4

2 に答える 2

8

画像を使用してバックトラックと再帰を理解することは、非常に小さな例では機能しますが、より大きなプログラムには対応していません。また、プログラムをステップスルーすることで、最も興味深いプロパティを簡単に見逃してしまいます。幸いなことに、それよりも優れた概念があります。あなたの例を見てみましょうisInteger/1。

ソリューション/回答のセット

あなたの主な関心は、あなたが正しいことを説明していることを確認することです。ここで、2番目のルールが最も興味深いものです。矢印の方向に読んでください:-。つまり、右から左へ：提供Yされるのは整数であり、X is Y+1次に整数も提供されXます。

次に、この場合は無限である解のセットを推定できます。

終了プロパティ

次の質問は、述語の終了プロパティに関するものです。無限に多くの答えを生成する必要がある場合、終了することはできません（実際には終了してはなりません）。一方、のような地上クエリにisInteger(1)は、解決策が1つあるか、まったくないかのどちらかです。したがって、このような場合は述語が終了することが望ましいです。ただし、定義はここで終了しません。

失敗スライス

これをよりよく理解するために、failure-sliceを使用します。つまり、私はfalseあなたのプログラムに目標を挿入します。結果のプログラムフラグメントが終了しない場合、元のプログラムフラグメントは終了しません。

？-isInteger（1）、false

isInteger（0）：- false。
isInteger（X）：-
   isInteger（Y）、false、
    XはY+1です。

非常に小さな部分だけが非終了の原因です！残りの部分は、の値をまったく見ていませんX。したがって、プログラムは決して終了しません。どのように呼んでも。

を参照してください。

于 2013-01-02T01:45:28.403 に答える
0

スウィッシュコンソールでこれをトレースします。

% Handover to indenting predicate

isInteger(X) :- isInteger(X,0).

% As isInteger(), with printouts

isInteger(0,I) :- ws(I), format('0 reached\n').
isInteger(X,I) :- wrout('>', X,Y,I), ID is I+1, isInteger(Y,ID), wrout('<', X,Y,I), X is Y+1, wsucc(I).

% Writing out

wrout(C,X,Y,I) :-ws(I),format('~a X=',C),write(X),format(',Y='),write(Y),format('\n').

% Writing "success"

wsucc(I) :- ws(I),format('success\n').

% Indenting by 2*N underscores

ws(0).
ws(N) :- N>0, format('__'), ND is N-1, ws(ND).

2が整数ビアであるかどうかを確認し? - isInteger(2).ます（ただし、これについてはNextを呼び出さないでください。そうしないと、終わりのない検索が発生します！）

> X=2,Y=_G5707
__0 reached
< X=2,Y=0
__> X=_G5707,Y=_G6473
____0 reached
__< X=_G5707,Y=0
__success
< X=2,Y=1
success
true

を使用して整数を列挙します?- isInteger(I)

0 reached
I = 0

"次"

> X=_G5328,Y=_G5926
__0 reached
< X=_G5328,Y=0
success
I = 1

「次へ」（インデント「__」で再開することに注意してください）

__> X=_G5926,Y=_G391
____0 reached
__< X=_G289,Y=0
__success
< X=_G257,Y=1
success
I = 2

「次へ」（インデント「____」から再開することに注意してください）

____> X=_G391,Y=_G3260
______0 reached
____< X=_G391,Y=0
____success
__< X=_G289,Y=1
__success
< X=_G257,Y=2
success
I = 3

非常に素晴らしい。

これを地元のチームに説明します。これは、いくつかの「元の表記法」を使用した整数列挙プロセスの図です。うまくいけば、自明です。

整数列挙バックトラッキングの図

于 2014-12-01T00:23:32.980 に答える