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)。
目标是定义一个谓词便宜路径/3，这样如果有
是从 X 到 Y 的总成本小于 N 的路径。谓词应该用 X, Y 调用
并且 N 全部实例化，例如对于查询便宜路径(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),
    M is N-N1,
    M > 0,
    cheaperPath(Z,Y,M).

否则，您以生成和测试的方式实现它，首先生成整个路径，然后验证它确实是一条较短的路径。