algorithm - prolog中的路径查找

Question

我需要在 prolog 中编写一个程序来查找路径，例如，对于图形：

edge(a, b). 
edge(a, c). 
edge(c, b).

测试用例是：

/* test case 1 */
?- path(a, b, P). 
P = [a, b] ;
P = [a, c, b] ; 
false. 

/* test case 2 */
?- path(c,b,[c,b]).
true.

我的代码是

path(X,Y,[X,Y]):-
    edge(X,Y).
path(X,Z,[X|P]):-
    edge(X,Y),
    path(Y,Z,P).

但是，对于测试用例 2，我的代码将显示

?- path(c,b,[c,b]).
true;
false.

我知道我应该在我的代码中添加一个剪切以删除案例 2 中的错误，但它也会删除案例 1 中的错误。我怎么解决这个问题？

score 1 · Accepted Answer

这是因为你的两个函数都是相同的，我认为 prolog 会检查这两个......在第一种情况下它失败了，因为只有一个函数满足它，即 path(c,b,P) 但在第二种情况下 path(c,b, [c,b]

它检查两个功能

path(X,Y,[X|P] here X = c and P = b
and
path(X,Y,[X,Y]) here also X=c and Y = b

因此，在第二种情况下，这两个功能的作用相同，因此您需要修改其中一种情况。例如：对于 2 个顶点，您只能使用

path(X,Y,[X|Y|[]]):- edge(X,Y).

代替

path(X,Y,[X,Y]):-
edge(X,Y).

它只需要两个变量，我认为这应该可以解决您的问题。

1 回答 1