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

Question

我被以下Prolog问题卡住了： 给定了一个没有周期的图的边作为事实。 e.g：

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

我必须写一个测试是否有顶点X和之间的两条不同的路径谓词Y. e.g呼叫如果有两个不同的路径从节点到节点c two_paths(a, c).应返回true。我知道如何检查是否有两个顶点之间的路径：

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），您进给第一构造路径谓词，从而迫使你的程序至少在一些点执行从所呈现的一个不同的步骤。我把这个做为潜在的练习。