尝试获取给定路径的成本

您的谓词几乎有效.我只想解决两个问题和一些细节.首先，将具有不同ar的谓词分开将大大提高可读性.因此，让我们将path/5的一个规则放在path/6的两个规则之前，如下所示:

Your predicate almost works. There are only two issues and some details I'd like to address. Firstly it would aid readability greatly to separate predicates with different arities. So let's put the one rule of path/5 in front of the two rules of path/6 like so:

path(X,Y,[X|Cs], S, P) :-
    path(X,Y,[X],Cs, S, P),
    P is S+W.                          % <-(1)

path(X,X,_,[], S, P).
path(X,Y,Visited,[Z|Cs], S, P) :-
    connection(X,Z,W),
    notIn(Z,Visited),
    path(Z,Y,[Z|Visited],Cs, S+W, P).  % <-(2)

查看示例查询路径/5似乎是您要调用以查找路径的谓词.在其单个规则的第二个目标(标记为% <-(1))中，您将使用内置的is/2，表达式的右侧为S+W.变量W首次出现在此处，因此未绑定.如以下示例所示，这会导致实例化错误:

Looking at your example query path/5 seems to be the predicate you want to call to find paths. In the second goal of its single rule (marked as % <-(1)) you are using the built-in is/2 with the expression S+W on the right hand side. The variable W appears here for the first time and thus is unbound. This leads to an instantiation error as illustrated by the following example:

   ?- X is 1+W.
     ERROR!!
     INSTANTIATION ERROR- in arithmetic: expected bound value

但是，由于您仅使用路径/5来调用路径/6，因此不需要该目标.其次，在路径/6的第二条规则中，在最后一个目标中，您传递了S+W作为参数，而不是首先对其进行求值.要查看会发生什么，让我们从路径/5中删除标记为% <-(1)的目标，并将示例图添加到您的代码中:

However, since you are only using path/5 to call path/6 there is no need for that goal. Secondly, in the second rule of path/6, in the last goal you are passing S+W as argument instead of evaluating it first. To see what happens, let's remove the goal marked % <-(1) from path/5 and add an example graph to your code:

connection(ori,a,2).
connection(a,b,5).
connection(b,a,4).
connection(b,dest,1).

现在考虑具有附加目标的示例查询:

Now consider your example query with an additional goal:

   ?- path(ori, dest, X, 0, P), Weight is P.
P = 0+2+5+1,
Weight = 8,
X = [ori,a,b,dest] ? ;
no

如您所见，参数S+W导致最终权重是一个表达式而不是一个值.考虑在递归目标之前添加目标S1 is S+W并将S1作为参数传递.第三，您在断言notIn/2中使用内置(\ ==)/2.这种比较成功或失败而没有副作用或统一.只要两个参数都绑定到值上就可以了，但是在与未绑定变量一起使用时会出现问题.考虑以下查询:

As you see the argument S+W leads to the final weight being an expression rather than a value. Consider adding a goal S1 is S+W before the recursive goal and pass S1 as an argument. Thirdly you are using the built-in (\==)/2 in your predicate notIn/2. This comparison succeeds or fails without side effect or unification. This is fine as long as both arguments are bound to values but are problematic when used with unbound variables. Consider the following queries:

   ?- X=Y, X\==Y.
no

按预期失败，但是:

   ?- X\==Y, X=Y.
X = Y

成功，因为X\==Y对变量没有影响，因此可以将它们统一到下一个目标中.最好改用dif/2:

succeeds as X\==Y has no effect to the variables, so they can be unified in the next goal. It is a good idea to use dif/2 instead:

   ?- X=Y, dif(X,Y).
no
   ?- dif(X,Y), X=Y.
no

最后，有两个建议:首先，由于您使用path/5的第4个参数传递0作为权重的起始值，因此您最好在规则的单个目标中执行此操作，从而简化了到路径/4的接口.其次，最好为谓词使用一个更具描述性的名称，以反映其声明性，例如start_end_path_weight/4.因此，您的代码将如下所示:

Lastly, two minor suggestions: First, since you are using the 4th argument of path/5 to pass 0 as a start-value for the weight, you might as well do that in the single goal of the rule, thereby simplifying the interface to path/4. Second, it would be nice to have a more descriptive name for the predicate that reflects its declarative nature, say start_end_path_weight/4. So your code would then look something like this:

notIn(A,[]).
notIn(A,[H|T]):-
   dif(A,H),
   notIn(A,T).

start_end_path_weight(X,Y,[X|Cs], P) :-
   path(X,Y,[X],Cs, 0, P).

path(X,X,_,[], P, P).
path(X,Y,Visited,[Z|Cs], S, P) :-
    connection(X,Z,W),
    notIn(Z,Visited),
    S1 is S+W,
    path(Z,Y,[Z|Visited],Cs, S1, P).

通过这些修改，您的示例查询如下:

With these modifications your example query looks like this:

   ?- start_end_path_weight(ori,dest,X,W).
W = 8,
X = [ori,a,b,dest] ? ;
no