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

Question

我遇到了以下 Prolog 问题:给定没有环的图的边作为事实。例如:

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

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

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

但是我应该如何执行此操作来检查两条不同的路径？非常感谢您的帮助。

Answer 1

一个想法可能是创建一个谓词 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 实现(没有剪切 (!)、once/1 等)。存在更有效的方法，因为您将在第二次调用中“重做”工作。

更有效的方法可能是构造一个谓词 path_avoid/3 (或 path_avoid/4)，您可以将第一个构造的路径提供给谓词，从而强制您的程序至少在某个时刻执行与所呈现的步骤不同的步骤。我将其保留为一个潜在的练习。