图中从X到Y的两条不同路径

我坚持以下Prolog问题:给定图形的边缘没有周期作为事实.例如:

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

我必须编写一个谓词来测试顶点X和Y之间是否有两条不同的路径.例如,two_paths(a, c).如果从节点a到节点c有两条不同的路径,则调用应该返回true.我知道如何检查两个顶点之间是否有路径:

path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

但是我该怎么做才能检查两条不同的路径呢？非常感谢您的帮助.

一个想法可能是创建一个path/3返回构造路径的谓词,然后查询两个不同的路径.就像是:

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

现在path(a,c,T)将向您展示路径:

?- path(a,c,L).
L = [a, b, c] ;
false.

现在你可以构造一个谓词:

two_paths(X,Y) :-
    path(X,Y,La),
    path(X,Y,Lb),
    dif(La,Lb).

换句话说,你要求Prolog为你La构造一个路径Lb,然后为你构造一个路径,然后检查它们是否不相等(dif(La,Lb)).第一个构造Lb将等同于La,但由于Prologs回溯机制,它将尝试构建条件可能成功的另一条路径.这是一个相当纯粹的Prolog实现(没有cut(!)once/1等).存在更有效的方法,因为在这里您将在第二次调用中"重做"工作.

一种更有效的方法可能是构造一个谓词path_avoid/3(或path_avoid/4),其中您将第一个构造的路径提供给谓词,从而迫使您的程序至少在某个时刻执行与呈现的步骤不同的步骤.我将此作为一项潜在的练习.