1

次の述語があるとしましょう。

father(aaron, chloe).
father(aaron, dan).
father(aaron, emily).
father(frank, george).
mother(beth, chloe).
mother(beth, dan).
mother(beth, emily).
mother(emily, george).
sibling(X,Y) :-...
parents(X,Y) :-...

家系図の 2 つのメンバー間の最短ルート(距離)を見つけたいです。たとえば、両親間の距離は 2 で、兄弟 (兄弟) 間の距離は 1 です。私は次のことを試しました（しかし、うまくいきませんでした）：

 parent(X,Y) :- 
    father(X,Y);  
    mother(X,Y). 

sibling(X,Y):- 
    parent(Z,X), !, parent(Z,Y),
    not(X=Y).

not_in_list(_,[]).
not_in_list(X,[Y|L]):- 
    not(X=Y), 
    not_in_list(X,L).

edge(X,Y):- 
    (parent(X,Y);
    parent(Y,X);
    sibling(X,Y)).

list_length(0,[]).
list_length(N,[_|Ys]):- 
    list_length(N1,Ys), 
    N is N1+1.

travel_graph(X,X,_).
travel_graph(From,To,[From|Path]):- 
    edge(From,Next), 
    not_in_list(Next,Path), 
    travel_graph(Next,To,Path).

degree(X,Y,N):- 
    travel_graph(X,Y,L), 
    list_length(N,L).
4

1 に答える 1

1

一般に、最短パスが必要な場合は、幅優先検索が必要です。ここにいくつかの議論があります:プロローグの幅優先

Prolog は最初に解決策の深さを見つけようとします。そのため、特定の推論の行がどこまで到達できるかを確認します。最短経路が必要な場合は、Prolog で最初のすべてのオプションを試してから、解決策が見つかるまで、それらのそれぞれから外側に向かって繰り返します。このようにして、最初に見つけた解が最短になります。解決策が無限にある可能性がある場合は、これが唯一の方法です (たとえば、迷路を歩いて戻ったり戻ったりすることができます)。

残念ながら、幅優先検索を行うために切り替えられる魔法のスイッチはありません。そのため、それを実装する必要があります。O'Keefe はThe Craft of Prologでこれを非常に明快に説明しています。最初に、通常の Prolog 検索を、まだ試行されていないものの「オープン セット」を使用した明示的な深さ優先検索に変換する方法を説明し、次にどのように開集合を表すリストの順序を変更して、代わりに幅優先の動作を取得します。

于 2013-01-25T19:03:49.863 に答える