prolog -检查结果后写出结果

Question

我一直在写代码，以便我能够搜索图形中是否有路径，如果有，我想打印出路径，如果有，我想打印出所有的路径。我有一个条件，如果谓词为真，则写入路径，但它从不打印，我应该如何处理？

%graph
edge(a,b).
edge(a,c).
edge(b,c).
edge(c,d).
edge(c,e).
edge(d,e).
edge(f,g).
edge(g,h).


% condition

allways(X,Y) :-
edge(X,Y).


% recursion
allways(X,Y) :-
edge(X,B),
allways(B,Y).



%print out path if there is one (its meant to print out all paths it can find)
allways(P,Y) == true -> writepath(X,Y).

writepath(X,Y):-
edge(X,Y).

writepath(X,Y) :-
edge(X,B),
write(B),
writepath(B,Y).

Answer 1

您是否考虑过添加一个列表作为第三个参数来收集路径上的节点？不是使用write/1输出每个节点，而是有一个列表，其中包含每个解决方案从开始到目标的所有节点。考虑对您的代码进行以下更改：

allways(X,Y,[X,Y]) :-
   edge(X,Y).
allways(X,Y,[X|Nodes]) :-
   edge(X,B),
   allways(B,Y,Nodes).

如果在X和Y之间有一条边，那么它就是路径的末端，两个节点都在列表中。否则，必须有一个中间节点B，并且列表中只有X。此谓词产生所需的结果：

?- allways(a,e,P).
P = [a, b, c, e] ;
P = [a, b, c, d, e] ;
P = [a, c, e] ;
P = [a, c, d, e] ;
false.

现在，您将获得从开始到目的地的每条路径的节点列表。但是，这个查询只会终止，因为您提供的图是非循环的。考虑添加一条边，使图形包含一个圈：

edge(a,b).
edge(a,c).
edge(b,c).
edge(c,e).
edge(c,d).
edge(d,e).
edge(f,g).
edge(g,h).
edge(c,a). % <- new edge

现在，由于新添加的循环，上面的查询循环：

?- allways(a,e,P).
P = [a, b, c, e] ;
P = [a, b, c, d, e] ;
P = [a, b, c, a, b, c, e] ;
P = [a, b, c, a, b, c, d, e] ;
P = [a, b, c, a, b, c, a, b, c, e] ;
P = [a, b, c, a, b, c, a, b, c, d, e] ;
P = [a, b, c, a, b, c, a, b, c, a, b, c, e] ;
.
.
.

如果您不想要此行为，可以添加一个已访问节点的列表作为附加参数。我还建议使用一个更具描述性的名称，比如调用谓词为start_dest/3，实际关系为start_dest_path_visited/4：

:- use_module(library(apply)).

start_dest_path(S,D,P) :-
   start_dest_path_visited(S,D,P,[]).

start_dest_path_visited(S,D,[S,D],Vs) :-
   maplist(dif(S),Vs),
   edge(S,D).
start_dest_path_visited(S,D,[S|Nodes],Vs) :-
   maplist(dif(S),Vs),
   edge(S,X),
   start_dest_path_visited(X,D,Nodes,[S|Vs]).

谓词start_dest_path/3正在调用具有空累加器的start_dest_path_visited/4。start_dest_path_ visited /4中的目标maplist(dif(S),Vs)确保节点S尚未被访问。现在，查询也随着这个循环而终止：

?- start_dest_path(a,e,P).
P = [a, b, c, e] ;
P = [a, b, c, d, e] ;
P = [a, c, e] ;
P = [a, c, d, e] ;
false.

尽管路径不能包含周期，但这个定义允许路径是一个大周期。考虑以下查询：

?- start_dest_path(a,a,P).
P = [a, b, c, a] ;
P = [a, c, a] ;
false.

如果您想排除此类解决方案，请将目标maplist(dif(D),Vs)添加到start_dest_path_visited/4的非递归规则中。

注意谓词start_dest_path_ visited /4仍然与原始post中的allways/2的结构相似，带有两个额外的参数(路径和访问节点的列表)和一个额外的目标(maplist/2)。在this和this answer中，您可以看到加权路径的定义略有不同。您可能还会对this question中建议的更通用的定义和相应的答案感兴趣。