2

我被以下 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).

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

4

1 回答 1

5

一个想法可能是创建一个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），在其中将第一个构造的路径提供给谓词，从而强制您的程序至少在某个时候执行与所提供的步骤不同的步骤。我将其保留为一个潜在的练习。

于 2017-01-22T22:40:32.853 回答