2

そのため、再帰的な方法を使用して、2 人の間のパスを見つけようとしています。簡単な背景は次のとおりです。私はいくつかの事実を定義しますin(X,Y)。つまり、誰が関係しているかを示します。in(person1,project1)、in(person2,project1)など。現在、2 人が同じプロジェクトにいた場合、または 2 人の間に人のリンク パスがある場合、2 人は関連しています。たとえば、p1 は A で作業し、p2 は A と B で作業し、p3 は B で作業したため、p1 から p2 を経由して p3 へのパスが存在します。これらのパスの長さは任意です。

私はこれを再帰的に解決しようとしていますが（他の方法は見られません）、厄介な問題があります：

related(A,B) :-
        in(A,X),
        in(B,X),
        not(A=B).

chain(A,B) :-
        related(A,B).
chain(A,B) :-
        related(A,Y),       
        chain(Y,B).

問題は、パスが繰り返される可能性があることです。p1 から p2 に戻って p1 に無限に戻ることができます。人はパスに 1 回以上存在してはなりません。

追加するリストでこれを修正しようとしました。人が既にリストに含まれている場合、再度追加することはできません。

related(A,B,L) :-
        in(A,X),
        in(B,X),not(A=B).

chain(A,B,L) :-
        related(A,B,L).
chain(A,B,L) :-
        related(A,Y,L),
        not(member(Y,L)),
        append(L,[Y],Q),
        chain(Y,B,Q).

そして、それはある程度機能しましたが、大量のランダムなエラーが発生し、一部の人は複数回繰り返し、一部の人は1回だけ繰り返し、その後失敗しました. このアプローチは正しく見えますか? リストを完全に間違って使用していますか?

ありがとうございました。

4

3 に答える 3

0

私は完全に明確ではなかったと思いますが、私はこれを自分で解決することになりました。以下にコードを入れます。

本当に重要だったのは、効果的なnotchain述語であり、それから私が追加を正しく行ったことを確認しました。また、not（A = B）を置き換えるためにnotsame述語を作成しました。コードは以下のとおりです。答えのほとんどは、リストに追加されているものの周りに[]があることを確認することでした。追加されたものの周りに正しい[]がないと、エラーが発生しました。

notchain（X、L）：-

member（X、L）、！、fail。

notchain（X、L）。

その後：

チェーン（A、B、L）：-

related（A、B）、append（L、[A]、Q）、append（Q、[B]、Z）、write（final）、writeln（Z）。

chain（A、B、L）：-notchain（A、L）、append（L、[A]、Q）、related（A、Y）、chain（Y、B、Q）。

これは関連して使用されました：

notsame（A、B）：-（
A = B）、！、fail。

notsame（A、B）。

于 2012-11-03T20:39:03.973 に答える
0

これは、固定点計算に基づいた、効率は劣るかもしれませんが、むしろ一般的な代替方法です。

connected(Found, Connected) :-
    collect(Found, [], Ext),
    (   Ext == Found
    ->  Connected = Found
    ;   connected(Ext, Connected)
    ).

collect([], Set, Set).
collect([E|Es], Set, Fix) :-
    extend(E, Set, Ext),
    collect(Es, Ext, Fix).

extend(E, Set, Ext) :-
    directly(E, DirectConn),
    ord_union(DirectConn, Set, Ext).

directly(A, DirectConn) :-
    setof(B, P^(in(A, P), in(B, P)), DirectConn).

ソートされたリストで connected(Found, Connected) を呼び出す必要があり、セットが拡張できなくなるまでループします。たとえば、このテストデータでは

in(anna,  project1).
in(bob,   project1).
in(bob,   project2).
in(chris, project2).
in(dan,   project3).

?- connected([bob],L).
L = [anna, bob, chris].

?- connected([dan],L).
L = [dan].

意図的に直接許可する/2 ID を取得する、つまり

?- directly(X,Y).
X = anna,
Y = [anna, bob] ;
...
X = dan,
Y = [dan].
于 2012-11-02T23:38:07.470 に答える
0

最初の改善。関係のすべてのチェーンを探していますか、それとも関係のチェーンが 1 つあるかどうかを確認しますか? 最初のケースでは、カットを追加します。

chain(A,B) :-
        related(A,B), !.
chain(A,B) :-
        related(A,Y),       
        chain(Y,B).

2 番目のケースでは、Prolog は要求されたことを正確に実行します。つまり、すべての可能なチェーンを見つけます。

問題の原因となっているクエリを投稿してください。それについて一緒に推論し、解決策を改善することができます。

于 2012-11-02T16:40:06.023 に答える