3

私は次のプログラムを与えられています：

edge(a,b).
edge(b,c).
edge(a,d).

path(N,M):- path(N,New),edge(New,M).
path(N,M):- edge(N,M).

次のクエリにプルーフ ツリー アルゴリズムを適用する場合は、次のように尋ねました。

?- path(a,X).

証明木は無限の成功木ですか、それとも無限の失敗木ですか?

私が見ているように、ツリーの構築中に、パスのルール 1 を何度も適用し、無限のツリーを作成し、パスのルール 2 に到達することはありません..

したがって、無限の障害ツリーが作成されます。しかし、私が持っている解決策は、それが無限の成功の木であると言います。私の質問は、私は正しいですか、それとも私の教授は正しいですか? :]

4

2 に答える 2

4

使用している用語はわかりませんが、Lloyd (論理プログラミングの基礎) で使用されている一般的な用語は、 success、infinite、およびfailure ブランチを含む可能性があるSLD-treeです。また、標準の Prolog 計算規則 (= 一番左の原子を選択) を使用していると仮定します。

あなたの例の SLD ツリーは無限であり、3 つの回答置換に対応する有限数の成功分岐が含まれていますX = b ; X = c ; X = d。注意すべき重要なことは、このツリーには無限の障害ブランチがありますが、それでもすべてのソリューションが含まれているということです!

計算規則の選択そのものが、SLD ツリーのサイズと構造に影響を与える可能性があります。しかし、良い点は次のとおりです。計算ルールが何であれ、成功の分岐が得られます! 保証します！ええと、無限の SLD ツリーを巧妙な方法で描画し、使用方法を知っている人に保証されています...賢明に。しかし、無限のリソースと賢明さを備えた人々にとっては問題ありません。

もう 1 つの観察結果は、この SLD ツリーの形状が節の順序とはまったく無関係であることです。したがって、非再帰ルールが最後に記述されているかどうか (あなたの場合のように) または最初に記述されているかどうかは、ツリーの形状に大きな違いはありません: 同じサイズ (両方とも無限または両方とも有限) になり、含まれますノードの数は同じですが、一部のブランチは異なる順序で表示されます。

Prolog はその SLD ツリーを段階的に作成しようとしますが、最も原始的な方法を使用して作成します。ブランチの探索を開始し、他のブランチを展開する前に完全に探索します。つまり、Prolog は SLD ツリー (または正確には SLD ツリーの一部のみ) の非常にスペース効率の高い表現を使用できることを意味します。実際、これは本質的にスタックですが、支払う代償は無限分岐に出くわすと、スタックします - 実際、無限のリソースがない限り。そして、節の順序は、成功分岐 (= 答え) が見つかるかどうか、またはそれらが何らかの無限分岐によって埋められるかどうかに影響します。

実際には、これらすべての無限の木を視覚化することは非常に困難です。私たちはそれらに慣れていません。

しかし、Prolog がその証明をどのように実行するかをよりよく理解する方法は他にもあります。

ここでの中心的な概念は、SLD ツリーで言えば、すべてのブランチの有限性を意味するクエリ/ゴールの普遍的な終了です。

目標の普遍的な終了を観察するのは非常に簡単Goal,falseです。代わりに実行するだけです。

では、これfalseは私たちの SLD ツリーで何をしたのでしょうか? 基本的に、無限または有限の障害分岐のみが存在するようになりました。すべての答えはなくなりました。

今、事態はさらに良くなっています: 私たちはfalseあなたのプログラムに導入することさえあります. 結果のプログラムは、失敗スライスと呼ばれます。このプログラムはもはや元のプログラムと同じではありませんが、次のプロパティが保持されます: 失敗スライスが終了しない (= 無限分岐がある) 場合、元のプログラムも終了しません (= 無限分岐がある)。

多くの場合、障害スライスははるかに短いため、理解がはるかに高速です。あなたのプログラムを見てください：

?- パス(a,X), false .

エッジ (a、b) :- false。
エッジ (b、c) :- false。
エッジ (a、d) :- false。

path(N,M):- path(N,New), false , edge(New,M) .
path(N,M):- false、 edge(N,M)。

経験豊富な Prolog プログラマーは、プログラムのこの小さな断片を見るだけで、はるかに理解しやすくなります。彼らは、無限の分岐を想像することに時間を費やしたり、実際の Prolog の実行を想像したりしません。

ある意味では、 はfalseすでに計算規則を示していますfalse。

これも「見る」ことを学ぶことができます。このリンクをたどってください。

于 2013-07-08T18:31:02.887 に答える
2

私はそれを無限ループと呼んでいます。トレースを見てください:

?- trace, path(a,X).
Call: (7) path(a, _G394) ? 
Call: (8) path(a, _G511) ? 
Call: (9) path(a, _G511) ? 
Call: (10) path(a, _G511) ? 
...
Call: (147) path(a, _G511) ? 
Call: (148) path(a, _G511) ? 
...
ERROR: Out of local stack

私はこれらの用語に精通していませんが、うまくいくかもしれません。解決策は生み出されないので、これが無限のサクセス ツリーであると主張するのは難しいでしょう。無限の時間と空間が与えられたとしても、成功する解決策を生み出すことはありません。同時に、プロローグの意味での失敗は即時であり、それも起こっていません。無限の失敗ツリーのようなものが存在する可能性があるかどうかはわかりません.無限の数の選択ポイントを生成するものと呼ばない限り、それらはすべて失敗します. しかし、ここには失敗はありません。これを本当の意味で無限ループと呼んだ方が正直でしょう。そのようなことは、成功と失敗の領域の外に存在します。これが、Haskell で ⊥ がすべての型に属する理由です。その意味では、あなたはどちらも正しいのかもしれません。

于 2013-07-08T14:36:02.297 に答える