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，兄弟（兄弟姐妹）之间的距离是 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 将首先尝试找到解决方案的深度，因此它将查看特定推理线可以走多远。当您想要最短路径时，您宁愿 Prolog 尝试所有第一个选项，然后从每个选项向外迭代，直到找到解决方案。这样，您找到的第一个解决方案将是最短的。如果您可能有无限的解决方案（例如走迷宫，您可以备份和追溯您的步骤），这是唯一的方法。

不幸的是，没有可以翻转来获得广度优先搜索的神奇开关，所以你必须实现它。O'Keefe 在The Craft of Prolog中非常清楚地解释了这一点，首先解释了如何将普通的 Prolog 搜索转换为具有“开放集”尚未尝试的事物的显式深度优先搜索，然后解释如何更改表示开放集的列表的顺序以获得广度优先行为。

于 2013-01-25T19:03:49.863 回答