prolog - 搜索路径是gprolog

Question

我正在尝试在 GProlog 中创建一个我认为相当简单的函数，但我在编写它时遇到了问题。

这个想法是假设一个加权 有向图通过以下方式描述 谓词edge/3，使得edge(X,Y,C) 为真，从顶点 X 到 存在一条边 成本 C 的顶点 Y。例如，向右 是一个图及其使用edge/3的描述: 边(a，c，1)。 边(a，d，3)。 边(b，d，2)。 边(c，e，5)。 边(e，c，2)。 边(e，f，2)。 边缘(d，f，10)。

目标是定义一个谓词 CheapPath/3，这样，如果存在，则 CheapPath(X,Y,N) 为 true 是从 X 到 Y 的总成本小于 N 的路径。谓词应该用 X, Y 调用 并且 N 全部实例化，例如对于查询 CheapPath(a,f,7) ，答案应该是“否”。

这是我现在在 Gprolog 中所做的，但循环似乎一直在持续:

edge(a, c,1).
edge(a,d,3).
edge(b,d,2).
edge(c,e,5).
edge(e, c,2).
edge(e,f,2).
edge(d,f,10).


cheaperPath(X,Y,N):-edge(X,Y,N1),N1@=<N.
cheaperPath(X,Y,N):-edge(X,Z,N1),cheaperPath(Z,Y,M),M is (N-N1).

知道为什么吗？

Answer 1

当你取得优势时，你应该减少界限，所以:

cheaperPath(X, Y, N) :-
    edge(X,Y,N1),
    N1 @=< N.
cheaperPath(X,Y,N):-
    edge(X,Z,N1),
    <b>M is N-N1</b>,
    <b>M > 0</b>,
    cheaperPath(Z,Y,M).

否则，您可以采用生成并测试的方式来实现此操作，首先生成整个路径，然后然后验证该路径这确实是一条更短的路径。