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

Question

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

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

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

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

但是我应该如何检查两条不同的路径呢？非常感谢您的帮助。

Answer 1

一个想法可能是创建一个谓词 path/3 returns 构造的路径，然后查询两条不同的路径。类似于：

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 等）。存在更有效的方法，因为在这里您将 "redo" 在第二次调用中完成工作。

一种更有效的方法可能是构造一个谓词 path_avoid/3（或 path_avoid/4），您将第一个构建的路径提供给谓词，从而强制您的程序至少在某个时候执行与提出的步骤不同。我把它留作一个潜在的练习。

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

Two different paths from X to Y in a graph

graph-theory

prolog

prolog-dif