7

Learn Prolog Now!を読んでいます。のカットに関する章と、同時に Bratko の人工知能のためのプロローグ プログラミング、第 5 章: バックトラッキングの制御。最初は、カットは他のプログラミング言語で知られている if-else 句を模倣する簡単な方法のように見えました。

# Find the largest number
max(X,Y,Y):- X =< Y,!. 
max(X,Y,X).

falseただし、行の下に記載されているように、このコードは、期待している場合でもすべての変数がインスタンス化される場合に失敗します。

?- max(2,3,2).
true.

理由は明らかです。最初のルールは失敗し、2 番目のルールにはもう条件が関連付けられていないため、成功します。私はそれを理解していますが、解決策が提案されています（ここではスウィッシュです）：

max(X,Y,Z):- X =< Y,!, Y = Z. 
max(X,Y,X).

そして、これをどう読むべきか、私は混乱している。私は、「これより前に来るすべてが真である場合、同じ述語を持つ他のルールを含めて終了を停止!する」という意味だと思いました。!ただし、これは正しくありません。これは、 のインスタンス化がY = Z失敗した場合にのみ発生することを意味し、そのルールでは役に立たないからです。

では、カットは「人間的」な方法でどのように読み取られるべきでしょうか? そして、拡張として、max/3上記の提案されたソリューションをどのように読むべきですか?

4

2 に答える 2

6

この回答とこの質問も参照してください。

上記の max/3 の提案されたソリューションをどのように読むべきですか?

max(X,Y,Z):- X =< Y, !, Y = Z. 
max(X,Y,X).

これは次のように読むことができます。

の場合X =< Y、述語の第 2 節を忘れて、 と を統合YしZます。

カットは選択ポイントを捨てる。選択ポイントは、解を見つけた後、さらに解を探すための検索をどこから再開するかを Prolog に指示する証明ツリー内のマークです。したがって、カットはプルーフ ツリーの一部を切り取ります。上記の最初のリンク (ここにもう一度あります) では、カットについて詳しく説明していますが、その回答の大部分は、他の場所でカットについて他の人が言ったことを引用しているだけです。

お持ち帰りのメッセージは、Prolog プログラムにカットを入れると、宣言的にではなく操作的にそれを読むように強制するということだと思います。証明木のどの部分が切り取られるかを理解するために、あなた (プログラマー) は一連の動作を実行し、節の順序を検討し、どのサブゴールが選択点を作成できるかを検討し、どのソリューションが失われるかを検討する必要があります。証明木を作成する必要があります (Prolog に任せるのではなく)。

必要のない選択ポイントを作成しないようにするために使用できる手法は多数あります。ただし、これは少し大きなトピックです。利用可能な資料を読み、具体的な質問をする必要があります。

于 2016-12-02T15:05:35.910 に答える