2

解决方案

ppath(X,Y,M,Path,[Y|Path]) :- edge(X,Y,M), 

\+ memberchk(Y,Path).
path(X,Y,P,SoFar,Path) :- edge(X,W,M), \+ 

memberchk(W,SoFar),
    path(W,Y,N,[W|SoFar],Path), P is M+N.


pravilo(X,Y,Z) :-
    aggregate(min(W), P^path(X,Y,W,[],P), 

Z).

之后，我尝试使用?- pravilo(a,z,M).获取结果。但它说的是假的。

我的版本 SWI-Prolog（多线程，64 位，版本 6.4.1）

谢谢你

4

1 回答 1

1

您应该尽可能避免断言/撤回。

您的图表在fand之间有一个循环g，那么您不能使用朴素的 path/4 谓词，否则您的程序将循环。

为避免循环，您应该反转路径构造（现在它是“自下而上”），以“自上而下”向 path/4 添加进一步的参数（累加器），并检查在递归之前尚未访问过节点。

您可以使用 memberchk 进行测试。

编辑：这是代码

path(X,Y,M,Path,[Y|Path]) :- edge(X,Y,M), \+ memberchk(Y,Path).
path(X,Y,P,SoFar,Path) :- edge(X,W,M), \+ memberchk(W,SoFar),
    path(W,Y,N,[W|SoFar],Path), P is M+N.

这产生

?- path(a,z,W,[],P).
W = 27,
P = [z, e, j, b] ;
W = 26,
P = [z, g, b] ;
...

让我们使用库（聚合）来完成分配：

pravilo(X,Y,Z) :-
    aggregate(min(W), P^path(X,Y,W,[],P), Z).

现在我明白了

?- pravilo(a,z,M).
M = 24.

编辑要获得（完整）有序路径，这些更改在递归基础中是必要的

path(X,Y,M,Path,FullPath) :-
   edge(X,Y,M), \+ memberchk(Y,Path), reverse([Y|Path], FullPath).

在顶级谓词中：

pravilo(X,Y,Z) :-
    aggregate(min(W), P^path(X,Y,W,[X],P), Z).
于 2013-09-26T11:26:24.427 回答