在Prolog中定义图形：边和路径，查找两个顶点之间是否存在路径 [英] Define graph in Prolog: edge and path, finding if there is a path between two vertices

问题描述

我对Prolog很陌生。我在 graph.pl 中定义了下图： .imgur.com / JP9Yi.pngalt =graph>

这里是我的Prolog代码：

 缘（A，E）。 
 edge（e，d）。 
 edge（d，c）。 
边缘（c，b）。 
边缘（b，a）。 
 edge（d，a）。 
 edge（e，c）。 
 edge（f，b）。 
路径（X，X）。 
 path（X，Y）： -  edge（X，Z）;路径（Z，Y）。 
  

我理解如下：顶点 X 和顶点 Y 仅当顶点 X 和顶点 Z 并且顶点 Z 和顶点 Y （某种递归）。

这个图表对吗？当我向Prolog询问顶点 A 和顶点 F 之间的路径时，它给了我 true ...这甚至都不对！这段代码中可能有什么错误？

解决方案

图中的循环。你需要跟踪你正在访问的节点，并检查它们。试试这个，使用带累加器的辅助谓词来跟踪访问节点：

  path（A，B）： - ％two节点连接，如果
走（A，B，[]）％ - 如果我们可以从一个走到另一个
。 （A，B，V）： - ％我们可以从A走到B ... 
 edge（A，X），％ ％ - 如果A连接到X，
不是（member（X，V）），％ - 我们还没有访问X，
（％ -  
 B = X ％ -  X是所需的目的地
;％OR 
 walk（X，B，[A | V]）％ - 我们可以从X 
）％
得到它。 ％ 简单！ 
 
 edge（a，e）。 
 edge（e，d）。 
 edge（d，c）。 
边缘（c，b）。 
边缘（b，a）。 
 edge（d，a）。 
 edge（e，c）。 
 edge（f，b）。 
  

I'm very new to Prolog. I defined in graph.pl the following graph:

And here's my Prolog code:

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).
path(X,X).
path(X,Y):- edge(X,Z) ; path(Z,Y).

I understand it like this: there is a path between vertex X and vertex Y only if there is an edge between vertex X and vertex Z AND there is a path between vertex Z and vertex Y (some kind of recursion).

Is that right for the presented graph? When I ask Prolog about the path between vertex A and vertex F it gives me true ... which isn't even right! What might be wrong in this code?

解决方案

Cycles in the graph. You need to track what nodes you're visiting, and check them. Try this, using a helper predicate with an accumulator to track the visited nodes:

path(A,B) :-   % two nodes are connected, if
  walk(A,B,[]) % - if we can walk from one to the other,
  .            % first seeding the visited list with the empty list

walk(A,B,V) :-       % we can walk from A to B...
  edge(A,X) ,        % - if A is connected to X, and
  not(member(X,V)) , % - we haven't yet visited X, and
  (                  % - either
    B = X            %   - X is the desired destination
  ;                  %   OR
    walk(X,B,[A|V])  %   - we can get to it from X
  )                  %
  .                  % Easy!

edge(a,e).
edge(e,d).
edge(d,c).
edge(c,b).
edge(b,a).
edge(d,a).
edge(e,c).
edge(f,b).

这篇关于在Prolog中定义图形：边和路径，查找两个顶点之间是否存在路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！