序言 - 检查结果后写出结果 [英] prolog - write out result after checking result

问题描述

我一直在编写代码，以便能够搜索图中​​是否存在路径，并且如果有一个我想打印出路径，如果有的话我想打印出所有路径。我有一个条件，如果谓词是真的，但它永远不会打印，我应该怎么去做这件事呢？

 ％图
 edge（a，b）。 
边缘（a，c）。 
 edge（b，c）。 
边缘（c，d）。 
 edge（c，e）。 
 edge（d，e）。 
 edge（f，g）。 
 edge（g，h）。 
 
 
％条件
 
 allways（X，Y）： -  
 edge（X，Y）。 
 
 
％递归
 allways（X，Y）： -  
 edge（X，B），
 allways（B，Y）。 
 
 
 
％如果有打印出来的路径（它打算打印出它可以找到的所有路径）
 allways（P，Y）== true  - > writepath（X，Y）。 
 
 writepath（X，Y）： -  
 edge（X，Y）。 
 
 writepath（X，Y）： -  
 edge（X，B），
写入（B），
写入路径（B，Y）。 
  

解决方案

您是否考虑添加列表作为第三个参数来收集沿着路径的节点？不要使用写/ 1来输出每个节点，而是为每个解决方案提供一个从开始到目的地的所有节点的列表。请考虑对您的代码进行以下更改：

  allways（X，Y，[X，Y]）： -  
缘（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）。 
边缘（a，c）。 
 edge（b，c）。 
 edge（c，e）。 
边缘（c，d）。 
 edge（d，e）。 
 edge（f，g）。 
 edge（g，h）。 
 edge（c，a）。 ％< - 新的边缘
  

现在上面的查询会因为新添加的循环而循环：

 ？ -  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_path / 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，节点，[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谓词仍然类似于来自原始帖子的allways / 2以及两个附加参数（路径和访问节点列表）和一个额外目标（maplist / 2）。您可以在此和这个答案。您可能也会对此问题和相应的答案中建议的更通用的定义感兴趣。

i have been writing code so that im able to search if there is a path in a graph and if there is one i would want to print out the path, if there is one i would like to print out all of them. i have a condition that writes the path if the predicate is true but it never prints, how should i go about this?

%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).

解决方案

Have you considered adding a list as third argument to collect the nodes along the path? Instead of using write/1 to output every node, you'd have a list with all nodes from start to destination for every solution. Consider the following change to your code:

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

If there is an edge between X and Y it's the end of the path and both nodes are in the list. Otherwise there has to be an intermediary node B and only X is in the list. This predicate yields the desired result:

?- 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.

Now you get a list of nodes for every path from start to destination. However, this query only terminates because the graph you provided is acyclic. Consider adding an edge such that the graph contains a cycle:

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

Now the above query loops because of the newly added cycle:

?- 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] ;
.
.
.

If you do not want this behaviour, you can add a list of visited nodes as an additional argument. I would also suggest a more descriptive name, say start_dest_path/3 for the calling predicate and start_dest_path_visited/4 for the actual relation:

:- 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]).

The predicate start_dest_path/3 is calling start_dest_path_visited/4 with an empty accumulator. The goal maplist(dif(S),Vs) in start_dest_path_visited/4 makes sure the node S has not already been visited. Now the query terminates with the cycle as well:

?- 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.

Although the path cannot contain cycles this definition allows the path to be one big cycle. Consider the following query:

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

If you want to exclude such solutions, add a goal maplist(dif(D),Vs) to the non-recursive rule of start_dest_path_visited/4.

Note how the predicate start_dest_path_visited/4 still resembles the structure of allways/2 from your original post with two additional arguments (path and list of visited nodes) and an additional goal (maplist/2). You can see a slightly different definition for weighted paths in this and in this answer. You might also be interested in a more generic definition as suggested in this question and the corresponding answers.

这篇关于序言 - 检查结果后写出结果的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！