5

私は「純粋な」プロローグ（いいえis、カット、または同様のもの。はい、それは宿題です）で可逆的な関係を書き込もうとしていますが、方法がわからないことを認めなければなりません。そのようなものを作るプロセスは見当たらない。

「純粋ではない」が可逆的な算術関係（add、mult、equal、less、...）が与えられ、これらの関係を作成するために使用する必要があります。

今、私は二分木の葉のリストであるtree(List,Tree)場合に真である関係を作成することによって可逆関数を作成する方法を理解しようとしています。ListTree

そのようなことを達成するために、私は葉tree_size(Tree,N)があるときに真である関係を作成しようとしています。これが私の素朴で不可逆的な関係です：TreeN

tree_len(n(_,leaf,leaf),1).
tree_len(n(op,G,D),N) :-
    tree_len(G,TG),
    tree_len(D,TD),
    add(TG,TD,N).

クエリは実行できますtree_len(some tree, N)が、たとえば、は実行できないtree_len(X,3)ため、元に戻すことはできません。これまでにいくつか試してみましたが、どこで何を探すべきかわからないので、がっかりしていることを認めなければなりません。これを行う方法は実際にありますか？

4

2 に答える 2

9

非終了の理由

まず、あなたの定義が元に戻せない理由を理解してみましょう。それをよりよく説明するために、失敗スライスを使用します。クエリを考えてみてtree_len(X,1).ください

?- tree_len(T,1).
T = n(_G267, leaf, leaf)

しかし、別の答えを求めてはいけません。ループしてしまうからです:

?- tree_len(T,1).
T = n(_G267, leaf, leaf) ;
** LOOPS **

そのため、私たちが得た答えは少し気を散らすものでした。一見、すべて問題ないように見えましたが、後戻りして初めて実際の問題が発生しました。これは、Prolog で慣れる必要があるものです。明らかに、3 を使用したクエリの方が適切に選択されています。しかし、それは運でした。

一般的にこれを確実にする簡単な方法があります。false追加の目標をクエリに追加するだけです。追加falseするということは、もはや成功することができないため、答えに関心がなくなったことを意味します。このようにして、気を散らすものはすべて取り除かれ、問題に直接直面します。

?- tree_len(T,1), false.
** LOOPS **

では、このループはどこから来たのでしょうか。

純粋で単調な Prolog プログラム (このようなもの) では、プログラムにいくつかの目標を追加することで、非終了の理由をローカライズできfalseます。結果のプログラム ( failure-sliceと呼ばれる) が終了しない場合、元のプログラムも終了しません。これは、クエリの最小の失敗スライスです。

?- tree_len(T,1), false .

tree_len(n(_,leaf,leaf),1) :- false .
tree_len(n(op,G,D),N) :-
    tree_len(G,TG), false ,
     tree_len(D,TD) ,
     N は TG+TD .

私たちのプログラムは残りわずかです！非終了の原因はこの小さな断片です。問題を解決したいのであれば、その小さな部分で何かをしなければなりません。他のすべては無駄です。

したがって、このフラグメントがループしないようにプログラムを変更する必要があります。

実際には、2 つの選択肢があります。後続の演算またはclpfd のような制約を使用できます。前者は任意の Prolog システムで利用でき、後者は SWI、YAP、SICStus、GNU、B などの一部でのみ提供されます。

後継演算の使用

ここで、3 は で表されs(s(s(0)))ます。

tree_lensx(T, s(N)) :-
   tree_lendiff(T, N,0)。

tree_lendiff(n(_,leaf,leaf), N,N)。
tree_lendiff(n(op,G,D), s(N0),N) :-
   tree_lendiff(G, N0,N1),
   tree_lendiff(D、N1、N)。

ここでは、いくつかの一般的なコーディング手法を使用しました。

違い

実際の関係はtree_lendiff/3、1 つの引数ではなく、2 つの引数を使用して自然数を表すことです。実際の数は、両者の差です。このようにして、定義を可逆的に保持することが可能です。

左再帰の回避

もう 1 つの手法は、左再帰を回避することでした。tree_lendiff/3実際に記述される長さは、長さから 1を引いたものです。最初に得た失敗スライスを覚えていますか? まったく同じ障害スライスがここにも存在します! ただし、長さを 1 つずつ「シフト」することで、再帰規則の先頭が確実に終了するようになりました。

使用するlibrary(clpfd)

もともと、有限領域に対する制約は、組み合わせ問題を解決するために開発されました。しかし、それらを使用して可逆演算を取得することもできます。SWI と YAP での実装は、従来の非可逆コードと同等の効率であり(is)/2ながら、可逆コードにコンパイルされるほどまで進んでいます。

:- use_module(library(clpfd)).

tree_fdlen(n(_,leaf,leaf),1).
tree_fdlen(n(op,G,D),N) :-
   N #= TG+TD,
   TG #>= 1,
   TD #>= 1,
   tree_fdlen(G,TG),
   tree_fdlen(D,TD).

このプログラムは、元の定義により厳密に対応しています。それにもかかわらず、このプログラムの終了を確実にするために冗長な情報を追加した 2 つの目標に注意してTG #>= 1ください。TD #>= 1

次のように、特定の範囲のすべてのツリーを列挙できるようになりました。

?- Size in 0..4, tree_fdlen(T, Size).
Size = 1, T = n(_A,leaf,leaf) ;
Size = 2, T = n(op,n(_A,leaf,leaf),n(_B,leaf,leaf)) ;
Size = 3, T = n(op,n(_A,leaf,leaf),n(op,n(_B,leaf,leaf),n(_C,leaf,leaf))) ;
Size = 4, ... ;
Size = 4, ... ;
Size = 3, ... ;
Size = 4, ... ;
Size = 4, ... ;
Size = 4, ... ;
false.

解答置換の正確な順序に注意してください! 1、2、3、4 だけではありません。むしろ、答えはある順序で見つかります。すべてのソリューションを見つけることだけに関心がある限り、どれでもかまいません。

于 2012-12-31T02:18:43.723 に答える
1

興味深い問題です。

これが私がすることです。基本的に、 add/3 がそうでないので、あなたの関係は可逆ではありません。私が本質的に行ったことは、カウントを数字で置き換え、葉の数に対応するサイズのリストでカウントすることでした-これは可逆です（まあ、append / 3とlength / 2は可逆です）。

これはあなたが必要とするもののようなものですか？投稿されたコードは YAP で実行可能です。

PS：これは最も簡潔な解決策ではないかもしれませんが、私の頭の上からです。他にご不明な点がございましたら、お気軽にお問い合わせください。

:-  use_module(library(lists)).

do_tree_len(n(_,leaf,leaf), [X]).
do_tree_len(n(op,G,D), [X1,X2|T]) :-
    append(TG, TD, [X1,X2|T]),
    TG \= [X1,X2|T], % To prevent infinite loops, when TG or TD is []
    TD \= [X1,X2|T],
    do_tree_len(G, TG),
    do_tree_len(D, TD).

tree_len(Tree, N):-
    length(L, N),
    do_tree_len(Tree, L).
于 2012-12-31T00:44:46.003 に答える